Digital Symposium Collection 2000

Evaluating Top-k Selection Queries Surajit Chaudhuri and Luis Gravano   View Paper (PDF)   Return to Partial Query Evaluation 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. References Note: References link to DBLP on the Web. [1] Michael J. Carey , Donald Kossmann : On Saying "Enough Already!" in SQL. SIGMOD Conference 1997 : 219-230 [2] Michael J. Carey , Donald Kossmann : Reducing the Braking Distance of an SQL Query Engine. VLDB 1998 : 158-169 [3] Surajit Chaudhuri , Luis Gravano : Optimizing Queries over Multimedia Repositories. SIGMOD Conf. 1996 : 91-102 [4] Ronald Fagin : Combining Fuzzy Information from Multiple Systems. PODS 1996 : 216-226 [5] Ronald Fagin : Fuzzy Queries in Multimedia Database Systems. PODS 1998 : 1-10 [6] Luis Gravano , Hector Garcia-Molina : Merging Ranks from Heterogeneous Internet Sources. VLDB 1997 : 196-205 [7] Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas : Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996 : 215-226 [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 [9] Amihai Motro : VAGUE: A User Interface to Relational Databases that Permits Vague Queries. TOIS 6(3) : 187-214(1988) [10] M. Muralikrishna , David J. DeWitt : Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference 1988 : 28-36 [11] Viswanath Poosala , Yannis E. Ioannidis : Selectivity Estimation Without the Attribute Value Independence Assumption. VLDB 1997 : 486-495 [12] Viswanath Poosala , Yannis E. Ioannidis , Peter J. Haas , Eugene J. Shekita : Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conf. 1996 : 294-305 [13] Gerard Salton , Michael McGill : Introduction to Modern Information Retrieval. McGraw-Hill Book Company 1984, ISBN 0-07-054484-0 [14] Thomas Seidl , Hans-Peter Kriegel : Optimal Multi-Step k-Nearest Neighbor Search. SIGMOD Conference 1998 : 154-165 [15] George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949 BIBTEX @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-5},    pages     = {397-410},    crossref  = {DBLP:conf/vldb/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM