Paper Info
Title
Distributed Structural Relaxation of XPath Queries
Abstract
Due to the structural heterogeneity of XML, queries are often interpreted approximately. This is achieved by relaxing the query and ranking the results based on their relevance to the original query. Query relaxation over distributed XML repositories may incur large communication costs, since partial result lists from different sites need to be gathered and ranked to assembly the overall top-k results. To process such queries efficiently, we propose using a distributed clustered index to group documents based on their structural similarity. The clustered index proves to be very effective in reducing the sizes of the partial lists that need to be combined. Furthermore, it can be used as the basis of a pay-as-you-go approach, where clusters of documents are accessed gradually providing the user with increasingly improving results. To reduce the cost of constructing and maintaining the clustered index, we use a compact data structure that trades-off accuracy for storage and communication efficiency. The index is also used for selectivity estimation so that query relaxation is geared towards the most promising structural transformations. Our experimental results show that our approach significantly reduces the communication cost for retrieving the top-k results, while maintaining a low construction cost for the clustered index.
Year
DOI
Venue
2009
10.1109/ICDE.2009.110
ICDE
Keywords
DocType
ISSN
large communication cost,communication cost,structural similarity,xml repository,structural heterogeneity,communication efficiency,query relaxation,original query,xpath queries,promising structural transformation,structural relaxation,low construction cost,indexes,distributed databases,estimation,data structure,xml,dynamic programming,indexation
Conference
1084-4627
Citations 
PageRank 
References 
4
0.40
13
Authors
2
Name
Order
Citations
PageRank
Georgia Koloniari122016.49
evaggelia pitoura21968321.56