A survey of top-k query processing techniques in relational database systems

ABSTRACT

Efficient processing of top-k queries is a crucial requirement in many interactive environments that involve massive amounts of data. In particular, efficient top-k processing in domains such as the Web, multimedia search, and distributed systems has shown a great impact on performance. In this survey, we describe and classify top-k processing techniques in relational databases. We discuss different design dimensions in the current techniques including query models, data access methods, implementation levels, data and query certainty, and supported scoring functions. We show the implications of each dimension on the design of the underlying techniques. We also discuss top-k queries in XML domain, and show their connections to relational approaches.

REFERENCES

• 1: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala, Congressional samples for approximate answering of group-by queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.487-498, May 15-18, 2000, Dallas, Texas, United States
• 2: Giuseppe Amato , Fausto Rabitti , Pasquale Savino , Pavel Zezula, Region proximity in metric spaces and its use for approximate similarity search, ACM Transactions on Information Systems (TOIS), v.21 n.2, p.192-227, April 2003 [doi>10.1145/763693.763696]
• 3: Sihem Amer-Yahia , Nick Koudas , Amélie Marian , Divesh Srivastava , David Toman, Structure and content scoring for XML, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 4: Aref, W. G., Catlin, A. C., Elmagarmid, A. K., Fan, J., Hammad, M. A., Ilyas, I. F., Marzouk, M., Prabhakar, S., and Zhu, X. 2004. VDBMS: A testbed facility for research in video database benchmarking. ACM Multimed. Syst. J. (Special Issue on Multimedia Document Management Systems) 9, 6, 575--585.
• 5: Arrow, K. 1951. Social Choice and Individual Values. Wiley, New York, NY.
• 6: Brian Babcock , Surajit Chaudhuri , Gautam Das, Dynamic sample selection for approximate query processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872822]
• 7: D. Barbará , H. Garcia-Molina , D. Porter, The Management of Probabilistic Data, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.487-502, October 1992 [doi>10.1109/69.166990]
• 8: Black, D. 1958. The Theory of Committees and Elections. Cambridge University Press, London, U.K.
• 9: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 10: Brams, S. J. and Fishburn, P. C. 1983. Approval Voting. Birkhauser, Boston, MA.
• 11: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, Top-k selection queries over relational databases: Mapping strategies and performance evaluation, ACM Transactions on Database Systems (TODS), v.27 n.2, p.153-187, June 2002 [doi>10.1145/568518.568519]
• 12: Amelie Marian, Evaluating Top-k Queries over Web-Accessible Databases, Proceedings of the 18th International Conference on Data Engineering, p.369, February 26-March 01, 2002
• 13: Kaushik Chakrabarti , Minos Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate query processing using wavelets, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.199-223, September 2001
• 14: Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564731]
• 15: Yuan-Chi Chang , Lawrence Bergman , Vittorio Castelli , Chung-Sheng Li , Ming-Ling Lo , John R. Smith, The onion technique: indexing for linear optimization queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.391-402, May 15-18, 2000, Dallas, Texas, United States
• 16: Surajit Chaudhuri , Gautam Das , Mayur Datar , Rajeev Motwani , Vivek R. Narasayya, Overcoming Limitations of Sampling for Aggregation Queries, Proceedings of the 17th International Conference on Data Engineering, p.534-542, April 02-06, 2001
• 17: Surajit Chaudhuri , Gautam Das , Vivek Narasayya, A robust, optimization-based approach for approximate answering of aggregate queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.295-306, May 21-24, 2001, Santa Barbara, California, United States
• 18: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.436-447, June 01-04, 1998, Seattle, Washington, United States
• 19: Copeland, A. H. 1951. A reasonable social welfare function. Mimeo. University of Michigan, Ann Arbor, MI.
• 20: Lorrie Faith Cranor , Ron K. Cytron, Declared-strategy voting: an instrument for group decision-making, Washington University, St. Louis, MO, 1996
• 21: Gautam Das , Dimitrios Gunopulos , Nick Koudas , Dimitris Tsirogiannis, Answering top-k queries using views, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 22: Diaconis, P. 1998. Group Representation in Probability and Statistics. Institute of Mathematical Statistics. Web site: www.imstat.org.
• 23: Diaconis, P. and Graham, R. 1977. Spearman's footrule as a measure of disarray. J. Roy. Statist. Soc. Series B 39, 2, 262--268.
• 24: Donko Donjerkovic , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
• 25: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 26: Ronald Fagin , Ravi Kumar , Mohammad Mahdian , D. Sivakumar , Erik Vee, Comparing and aggregating rankings with ties, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055568]
• 27: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 28: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 29: Norbert Fuhr, A Probabilistic Framework for Vague Queries and Imprecise Information in Databases, Proceedings of the 16th International Conference on Very Large Data Bases, p.696-707, August 13-16, 1990
• 30: Venkatesh Ganti , Mong-Li Lee , Raghu Ramakrishnan, ICICLES: Self-Tuning Samples for Approximate Query Answering, Proceedings of the 26th International Conference on Very Large Data Bases, p.176-187, September 10-14, 2000
• 31: Lise Getoor , Christopher P. Diehl, Link mining: a survey, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.3-12, December 2005 [doi>10.1145/1117454.1117456]
• 32: Ulrich Güntzer , Wolf-Tilo Balke , Werner Kießling, Optimizing Multi-Feature Queries for Image Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.419-428, September 10-14, 2000
• 33: Towards Efficient Multi-Feature Queries in Heterogeneous Environments, Proceedings of the International Conference on Information Technology: Coding and Computing, p.622, April 02-04, 2001
• 34: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 35: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 36: Hoeffding, W. 1963. Probability inequalities for sums of bounded random variables. American Statistical Association Journal, 13--30.
• 37: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou, PREFER: a system for the efficient execution of multi-parametric ranked queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.259-270, May 21-24, 2001, Santa Barbara, California, United States
• 38: Vagelis Hristidis , Yannis Papakonstantinou, Algorithms and applications for answering ranked queries using ranked views, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.1, p.49-70, January 2004 [doi>10.1007/s00778-003-0099-8]
• 39: Seung-won Hwang , Kevin Chen-chuan Chang, Optimizing top-k queries for middleware access: A unified cost-based approach, ACM Transactions on Database Systems (TODS), v.32 n.1, p.5-es, March 2007 [doi>10.1145/1206049.1206054]
• 40: Seung-won Hwang , Kevin Chen-Chuan Chang, Probe Minimization by Schedule Optimization: Supporting Top-K Queries with Expensive Predicates, IEEE Transactions on Knowledge and Data Engineering, v.19 n.5, p.646-662, May 2007 [doi>10.1109/TKDE.2007.1007]
• 41: Ihab F. Ilyas , Walid G. Aref , Ahmed K. Elmagarmid, Joining ranked inputs in practice, Proceedings of the 28th international conference on Very Large Data Bases, p.950-961, August 20-23, 2002, Hong Kong, China
• 42: F. Ilyas , G. Aref , K. Elmagarmid, Supporting top-k join queries in relational databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.3, p.207-221, September 2004 [doi>10.1007/s00778-004-0128-2]
• 43: Ihab F. Ilyas , Walid G. Aref , Ahmed K. Elmagarmid , Hicham G. Elmongui , Rahul Shah , Jeffrey Scott Vitter, Adaptive rank-aware query optimization in relational databases, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1257-1304, December 2006 [doi>10.1145/1189769.1189772]
• 44: Ihab F. Ilyas , Rahul Shah , Walid G. Aref , Jeffrey Scott Vitter , Ahmed K. Elmagarmid, Rank-aware query optimization, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007593]
• 45: Ihab F. Ilyas , Walid G. Aref , Ahmed K. Elmagarmid, Supporting top-K join queries in relational databases, Proceedings of the 29th international conference on Very large data bases, p.754-765, September 09-12, 2003, Berlin, Germany
• 46: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 47: Kendall, M. G. 1945. The treatment of ties in ranking problems. Biometrika 33, 3, 239--251.
• 48: Klamler, C. 2003. A comparison of the dodgson method and the copeland rule. Econ. Bull. 4, 8, 1--7.
• 49: Chengkai Li , Kevin Chen-Chuan Chang , Ihab F. Ilyas, Supporting ad-hoc ranking aggregates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142481]
• 50: Chengkai Li , Kevin Chen-Chuan Chang , Ihab F. Ilyas , Sumin Song, RankSQL: query algebra and optimization for relational top-k queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066173]
• 51: Nikos Mamoulis , Kit Hung Cheng , Man Lung Yiu , David W. Cheung, Efficient Aggregation of Ranked Inputs, Proceedings of the 22nd International Conference on Data Engineering, p.72, April 03-07, 2006 [doi>10.1109/ICDE.2006.54]
• 52: Amélie Marian , Nicolas Bruno , Luis Gravano, Evaluating top-k queries over web-accessible databases, ACM Transactions on Database Systems (TODS), v.29 n.2, p.319-362, June 2004 [doi>10.1145/1005566.1005569]
• 53: Sebastian Michel , Peter Triantafillou , Gerhard Weikum, KLEE: a framework for distributed top-k query algorithms, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 54: Apostol Natsev , Yuan-Chi Chang , John R. Smith , Chung-Sheng Li , Jeffrey Scott Vitter, Supporting Incremental Join Queries on Ranked Inputs, Proceedings of the 27th International Conference on Very Large Data Bases, p.281-290, September 11-14, 2001
• 55: Nurmi, H. 1987. Comparing Voting Systems. D. Reidel Publishing Company, Dordrecht, Germany.
• 56: Ré, C., Dalvi, N. N., and Suciu, D. 2007. Efficient top-k query evaluation on probabilistic data. In Proceedings of the 23rd International Conference on Data Engineering. 886--895.
• 57: S. E. Robertson , S. Walker, Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.232-241, July 03-06, 1994, Dublin, Ireland
• 58: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 59: Adam Silberstein Silberstein , Rebecca Braynard , Carla Ellis , Kamesh Munagala , Jun Yang, A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks, Proceedings of the 22nd International Conference on Data Engineering, p.68, April 03-07, 2006 [doi>10.1109/ICDE.2006.10]
• 60: Soliman, M. A., Ilyas, I. F., and Chang, K. C.-C. 2007. Top-k query processing in uncertain databases. In Proceedings of the 23rd International Conference on Data Engineering. 896--905.
• 61: Martin Theobald , Ralf Schenkel , Gerhard Weikum, An efficient and versatile query engine for TopX search, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 62: Martin Theobald , Gerhard Weikum , Ralf Schenkel, Top-k query evaluation with probabilistic guarantees, Proceedings of the Thirtieth international conference on Very large data bases, p.648-659, August 31-September 03, 2004, Toronto, Canada
• 63: Truchon, M. 1998. An extension of the Condorcet criterion and Kemeny orders. Cahier 98-15. Centre de Recherche en Economie et Finance Appliquees, Université Laval, Québec, Canada.
• 64: Tsaparas, P., Palpanas, T., Kotidis, Y., Koudas, N., and Srivastava, D. 2003. Ranked join indices. In Proceedings of the 19th International Conference on Data Engineering. 277.
• 65: S. V. Vrbsky , J. W. S. Liu, APPROXIMATE: A Query Processor that Produces Monotonically Improving Approximate Answers, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.1056-1068, December 1993 [doi>10.1109/69.250091]
• 66: Dong Xin , Chen Chen , Jiawei Han, Towards robust indexing for ranked queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 67: Dong Xin , Jiawei Han , Kevin C. Chang, Progressive and selective merge: computing top-k with ad-hoc ranking functions, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247494]
• 68: Young, H. P. and Levenglick, A. 1978. A consistent extension of condorcet's election principle. SIAM J. Appl. Math. 35, 2, 285--300.
• 69: Yidong Yuan , Xuemin Lin , Qing Liu , Wei Wang , Jeffrey Xu Yu , Qing Zhang, Efficient computation of the skyline cube, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 70: Zhen Zhang , Seung-won Hwang , Kevin Chen-Chuan Chang , Min Wang , Christian A. Lang , Yuan-chi Chang, Boolean + ranking: querying a database by k-constrained optimization, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142515]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Top-k, rank aggregation, rank-aware processing, voting