Adaptive processing of top-k queries in XML

Amélie Marian, Sihem Amer-Yahia, Nick Koudas, Divesh Srivastava

Research output: Chapter in Book/Report/Conference proceedingConference contribution

68 Scopus citations

Abstract

The ability to compute top-k matches to XML queries is gaining importance due to the increasing number of large XML repositories. The efficiency of top-k query evaluation relies on using scores to prune irrelevant answers as early as possible in the evaluation process. In this context, evaluating the same query plan for all answers might be too rigid because, at any time in the evaluation, answers have gone through the same number and sequence of operations, which limits the speed at which scores grow. Therefore, adaptive query processing that permits different plans for different partial matches and maximizes the best scores is more appropriate. In this paper, we propose an architecture and adaptive algorithms for efficiently computing top-k matches to XML queries. Our techniques can be used to evaluate both exact and approximate matches where approximation is defined by relaxing XPath axes. In order to compute the scores of query answers, we extend the traditional tf*idf measure to account for document structure. We conduct extensive experiments on a variety of benchmark data and queries, and demonstrate the usefulness of the adaptive approach for computing top-k queries in XML

Original languageEnglish (US)
Title of host publicationProceedings - 21st International Conference on Data Engineering, ICDE 2005
Pages162-173
Number of pages12
DOIs
StatePublished - 2005
Externally publishedYes
Event21st International Conference on Data Engineering, ICDE 2005 - Tokyo, Japan
Duration: Apr 5 2005Apr 8 2005

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Other

Other21st International Conference on Data Engineering, ICDE 2005
Country/TerritoryJapan
CityTokyo
Period4/5/054/8/05

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'Adaptive processing of top-k queries in XML'. Together they form a unique fingerprint.

Cite this