Adaptive processing of top-k queries in XML

Amelie Marian, Sihem Amer-Yahia, Nick Koudas, Divesh Srivastava

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

63 Citations (Scopus)

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 - Dec 12 2005
Event21st International Conference on Data Engineering, ICDE 2005 - Tokyo, Japan
Duration: Apr 5 2005Apr 8 2005

Publication series

NameProceedings - International Conference on Data Engineering

Other

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

Fingerprint

XML
Processing
Query processing
Adaptive algorithms
Experiments

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Signal Processing

Cite this

Marian, A., Amer-Yahia, S., Koudas, N., & Srivastava, D. (2005). Adaptive processing of top-k queries in XML. In Proceedings - 21st International Conference on Data Engineering, ICDE 2005 (pp. 162-173). (Proceedings - International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2005.18
Marian, Amelie ; Amer-Yahia, Sihem ; Koudas, Nick ; Srivastava, Divesh. / Adaptive processing of top-k queries in XML. Proceedings - 21st International Conference on Data Engineering, ICDE 2005. 2005. pp. 162-173 (Proceedings - International Conference on Data Engineering).
@inproceedings{ce581913fe68456baacbe627408d955e,
title = "Adaptive processing of top-k queries in XML",
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",
author = "Amelie Marian and Sihem Amer-Yahia and Nick Koudas and Divesh Srivastava",
year = "2005",
month = "12",
day = "12",
doi = "https://doi.org/10.1109/ICDE.2005.18",
language = "English (US)",
isbn = "0769522858",
series = "Proceedings - International Conference on Data Engineering",
pages = "162--173",
booktitle = "Proceedings - 21st International Conference on Data Engineering, ICDE 2005",

}

Marian, A, Amer-Yahia, S, Koudas, N & Srivastava, D 2005, Adaptive processing of top-k queries in XML. in Proceedings - 21st International Conference on Data Engineering, ICDE 2005. Proceedings - International Conference on Data Engineering, pp. 162-173, 21st International Conference on Data Engineering, ICDE 2005, Tokyo, Japan, 4/5/05. https://doi.org/10.1109/ICDE.2005.18

Adaptive processing of top-k queries in XML. / Marian, Amelie; Amer-Yahia, Sihem; Koudas, Nick; Srivastava, Divesh.

Proceedings - 21st International Conference on Data Engineering, ICDE 2005. 2005. p. 162-173 (Proceedings - International Conference on Data Engineering).

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

TY - GEN

T1 - Adaptive processing of top-k queries in XML

AU - Marian, Amelie

AU - Amer-Yahia, Sihem

AU - Koudas, Nick

AU - Srivastava, Divesh

PY - 2005/12/12

Y1 - 2005/12/12

N2 - 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

AB - 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

UR - http://www.scopus.com/inward/record.url?scp=28444472733&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=28444472733&partnerID=8YFLogxK

U2 - https://doi.org/10.1109/ICDE.2005.18

DO - https://doi.org/10.1109/ICDE.2005.18

M3 - Conference contribution

SN - 0769522858

T3 - Proceedings - International Conference on Data Engineering

SP - 162

EP - 173

BT - Proceedings - 21st International Conference on Data Engineering, ICDE 2005

ER -

Marian A, Amer-Yahia S, Koudas N, Srivastava D. Adaptive processing of top-k queries in XML. In Proceedings - 21st International Conference on Data Engineering, ICDE 2005. 2005. p. 162-173. (Proceedings - International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2005.18