Abstract

Many applications involving large databases with uncertain data require various techniques to rank queries. Ranking queries (often called as top-k) are useful in answering most important query answers in various domains such as web search, managing sensor data, location tracking, data mining tasks and multimedia. In this survey paper, we describe and classify different top-k processing techniques in probabilistic databases and their implications.

References

• Lukasz Golab, M. Tamer Ozsu, M. Tamer Özsu . "Data Stream Management. " Canada: Morgan & Claypool publishers, 2010.
• Chonghai Wang, Li Yan Yuan, Jia Huai You, Osmar R. Zaiane, "On Pruning for Top-K Ranking in Uncertain Databases," in Proc. 37th International Conference on Very Large Data Bases, August 29th -September 3rd , 2011
• Xiang Lian, Lei Chen, "Probabilistic Ranked Queries in Uncertain Databases," in Proc. Extending Database Technology Conference, March 25-30, 2008.
• Graham Cormode , Feifei Li and KeYi, "Semantics of Ranking Queries for Probabilistic Data and Expected Ranks," in Proc. ICDE IEEE 25th International Conference, 2009
• Yuan-Chi Chang, Lawrence Bergman, Vittorio Castelli, Chung-Sheng Li, Ming-Ling Lo, John R. Smith, "The onion technique: indexing for linear optimization queries," in Proc. ACM SIGMOD international conference on Management of data, Vol 29, pp 391-402, June 2000.
• Gang Luo , Kun-Lung Wu, Philip S. Yu, "SAO: A Stream Index for Answering Linear Optimization Queries," ICDE, pp 1302–1306, 2007
• Guo, L. , Shao, F. , Botev, C. ,Shanmugasundaram, J, "Xrank: Ranked keyword search over xml documents," SIGMOD 16–27 (2003)
• Mohamed A. Soliman, Ihab F. Ilyas, "Ranking with Uncertain Scores," in Proc. IEEE International Conference on Data Engineering , 2009
• Ihab F. Ilyas, George Beskales, Mohamed A. Soliman. "A Survey of Top-k Query Processing Techniques in Relational Database Systems. " ACM Computing Surveys(CSUR). Vol 40, Oct. 2008.
• Jeffrey Jestes, Graham Cormode, Feifei Li, and KeYi, "Semantics of Ranking Queries for Probabilistic Data", IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERIN. Oct. 2010.
• Xi Zhang, Jan Chomicki, "On the Semantics and Evaluation of Top-k Queries in Probabilistic Databases," Department of Computer Science and Engineering, University at Buffalo, SUNY, U. S. A.
• Charu C. Aggarwal and Philip S. Yu, "A Survey of Uncertain Data Algorithms and Applications," IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERIN. vol. 21 pp. 609-623, May. 2009.
• Tao Chen, Lei Chen, Member ,IEEE, M. Tamer Ozsu, Fellow ,IEEE, and Nong Xiao, "Optimizing multi-top-k queries over uncertain data streams," IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERIN. vol. 25 no. 8, pp. 1814-1829, Aug. 2013.
• Chen, Jianjun, David J. DeWitt, Feng Tian, Yuan Wang, "NiagaraCQ: A scalable continuous query system for internet databases. " ACM SIGMOD Record. Vol. 29. No. 2. ACM, 2000.
• Robert Kajic, "Evaluation of the Stream Query Language CQL," Thesis, Uppasala Universiy, May 2010.
• Arvind Arasu , Shivnath babu, jenifer widom, "The CQL continuous query language: semantic foundations and query execution" , VLDB Journal 2006.
• Shivnath Babu and Jennifer Widom, " Continuous Queries over Data Stream," Stanford University
• Jin Li ,David Maier, Kristin Tufte, Vassilis Papadimos, Peter A. Tucker, "Semantics and Evaluation Techniques for Window Aggregates in Data Streams," in Proc. ACM SIGMOD International Conference on Management of data, 2005.
• Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani, "MAINTAINING STREAM STATISTICS OVER SLIDING WINDOWS. " Society for Industrial and Applied Mathematics. Vol. 31, No. 6, pp. 1794–1813, 2002
• Krämer, Jürgen, and Bernhard Seeger. "Semantics and implementation of continuous sliding window queries over data streams. " ACM Transactions on Database Systems (TODS) 34. 1 (2009)
• Nilesh Dalvi, Dan Suciu, "Efficient Query Evaluation on Probabilistic Databases", in Proc. 30th VLDB Conference, 2004.