ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Evaluating Top-k Selection Queries.

Surajit Chaudhuri, Luis Gravano: Evaluating Top-k Selection Queries. VLDB 1999: 397-410
@inproceedings{DBLP:conf/vldb/ChaudhuriG99,
  author    = {Surajit Chaudhuri and
               Luis Gravano},
  editor    = {Malcolm P. Atkinson and
               Maria E. Orlowska and
               Patrick Valduriez and
               Stanley B. Zdonik and
               Michael L. Brodie},
  title     = {Evaluating Top-{\it k} Selection Queries},
  booktitle = {VLDB'99, Proceedings of 25th International Conference on Very
               Large Data Bases, September 7-10, 1999, Edinburgh, Scotland,
               UK},
  publisher = {Morgan Kaufmann},
  year      = {1999},
  isbn      = {1-55860-615-7},
  pages     = {397-410},
  ee        = {db/conf/vldb/ChaudhuriG99.html},
  crossref  = {DBLP:conf/vldb/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In many applications, users specify target values for certain attributes, without requiring exact matches to these values in return. Instead, the result to such queries is typically a rank of the "top k" tuples that best match the given attribute values. In this paper, we study the advantages and limitations of processing a top-k query by translating it into a single range query that traditional relational DBMSs can process efficiently. In particular, we study how to determine a range query to evaluate a top-k query by exploiting the statistics available to a relational DBMS, and the impact of the quality of these statistics on the retrieval efficiency of the resulting scheme.

Copyright © 1999 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Malcolm P. Atkinson, Maria E. Orlowska, Patrick Valduriez, Stanley B. Zdonik, Michael L. Brodie (Eds.): VLDB'99, Proceedings of 25th International Conference on Very Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK. Morgan Kaufmann 1999, ISBN 1-55860-615-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Michael J. Carey, Donald Kossmann: On Saying "Enough Already!" in SQL. SIGMOD Conference 1997: 219-230 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Michael J. Carey, Donald Kossmann: Reducing the Braking Distance of an SQL Query Engine. VLDB 1998: 158-169 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Surajit Chaudhuri, Luis Gravano: Optimizing Queries over Multimedia Repositories. SIGMOD Conference 1996: 91-102 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Ronald Fagin: Combining Fuzzy Information from Multiple Systems. PODS 1996: 216-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Ronald Fagin: Fuzzy Queries in Multimedia Database Systems. PODS 1998: 1-10 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Luis Gravano, Hector Garcia-Molina: Merging Ranks from Heterogeneous Internet Sources. VLDB 1997: 196-205 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996: 215-226 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Weiyi Meng, King-Lup Liu, Clement T. Yu, Xiaodong Wang, Yuhsi Chang, Naphtali Rishe: Determining Text Databases to Search in the Internet. VLDB 1998: 14-25 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Amihai Motro: VAGUE: A User Interface to Relational Databases that Permits Vague Queries. ACM Trans. Inf. Syst. 6(3): 187-214(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
M. Muralikrishna, David J. DeWitt: Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference 1988: 28-36 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Viswanath Poosala, Yannis E. Ioannidis: Selectivity Estimation Without the Attribute Value Independence Assumption. VLDB 1997: 486-495 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, Eugene J. Shekita: Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conference 1996: 294-305 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Gerard Salton, Michael McGill: Introduction to Modern Information Retrieval. McGraw-Hill Book Company 1984, ISBN 0-07-054484-0
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Thomas Seidl, Hans-Peter Kriegel: Optimal Multi-Step k-Nearest Neighbor Search. SIGMOD Conference 1998: 154-165 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:22:57 2010 by Michael Ley (ley@uni-trier.de)