Top-k dominating queries in uncertain databases

ABSTRACT

Due to the existence of uncertain data in a wide spectrum of real applications, uncertain query processing has become increasingly important, which dramatically differs from handling certain data in a traditional database. In this paper, we formulate and tackle an important query, namely probabilistic top-k dominating (PTD) query, in the uncertain database. In particular, a PTD query retrieves k uncertain objects that are expected to dynamically dominate the largest number of uncertain objects. We propose an effective pruning approach to reduce the PTD search space, and present an efficient query procedure to answer PTD queries. Furthermore, approximate PTD query processing and the case where the PTD query is issued from an uncertain query object are also discussed. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed PTD query processing approaches.

REFERENCES

• 1: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 2: Christian Bohm , Alexey Pryakhin , Matthias Schubert, The Gauss-Tree: Efficient Object Identification in Databases of Probabilistic Feature Vectors, Proceedings of the 22nd International Conference on Data Engineering, p.9, April 03-07, 2006 [doi>10.1109/ICDE.2006.159]
• 3: J. Chen and R. Cheng. Efficient evaluation of imprecise location-dependent queries. In Proc. 23th Int. Conf. on Data Engineering, 2007.
• 4: Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066213]
• 5: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Querying Imprecise Data in Moving Object Environments, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1112-1127, September 2004 [doi>10.1109/TKDE.2004.46]
• 6: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 7: Reynold Cheng , Sarvjeet Singh , Sunil Prabhakar, U-DBMS: a database system for managing constantly-evolving data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 8: Graham Cormode , Minos Garofalakis, Sketching probabilistic data streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247513]
• 9: Evangelos Dellis , Bernhard Seeger, Efficient computation of reverse skyline queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 10: Anton Faradjian, GADT: A Probability Space ADT for Representing and Querying the Physical World, Proceedings of the 18th International Conference on Data Engineering, p.201, February 26-March 01, 2002
• 11: Ming Hua , Jian Pei , Wenjie Zhang , Xuemin Lin, Ranking queries on uncertain data: a probabilistic threshold approach, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376685]
• 12: G. Kollios, K. Yi, F. Li, and D. Srivastava. Efficient processing of top-k queries in uncertain databases. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 13: H.-P. Kriegel, P. Kunath, M. Pfeifle, and M. Renz. Probabilistic similarity join on uncertain data. In Proc. Int. Conf. on Database Systems for Advanced Applications, 2006.
• 14: H.-P. Kriegel, P. Kunath, and M. Renz. Probabilistic nearest-neighbor query on uncertain objects. In Proc. Int. Conf. on Database Systems for Advanced Applications, 2007.
• 15: Iosif Lazaridis , Sharad Mehrotra, Progressive approximate aggregate queries with a multi-resolution tree structure, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.401-412, May 21-24, 2001, Santa Barbara, California, United States
• 16: M. Li and Y. Liu. Underground coal mine monitoring with wireless sensor networks. In ACM Transactions on Sensor Networks, 2009.
• 17: Xiang Lian , Lei Chen, Monochromatic and bichromatic reverse skyline search over uncertain databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376641]
• 18: Xiang Lian , Lei Chen, Probabilistic ranked queries in uncertain databases, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353406]
• 19: V. Ljosa and A. K. Singh. APLA: indexing arbitrary probability distributions. In Proc. 23th Int. Conf. on Data Engineering, 2007.
• 20: V. Ljosa and A. K. Singh. Top-k spatial joins of probabilistic objects. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 21: Mohamed F. Mokbel , Chi-Yin Chow , Walid G. Aref, The new Casper: query processing for location services without compromising privacy, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 22: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872814]
• 23: Jian Pei , Bin Jiang , Xuemin Lin , Yidong Yuan, Probabilistic skylines on uncertain data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 24: J. Pei, X. Lin, M. Hua, and W. Zhang. Efficiently answering probabilistic threshold top-k queries on uncertain data. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 25: C. Re, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. 23th Int. Conf. on Data Engineering, 2007.
• 26: A. D. Sarma, M. Theobald, and J. Widom. Exploiting lineage for confidence computation in uncertain and probabilistic databases. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 27: S. Singh, C. Mayfield, R. Shah, S. Prabhakar, S. Hambrusch, J. Neville, and R. Cheng. Database support for probabilistic attributes and tuples. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 28: M. A. Soliman, I. F. Ilyas, and K. C. Chang. Top-k query processing in uncertain databases. In Proc. 23th Int. Conf. on Data Engineering, 2007.
• 29: Yufei Tao , Reynold Cheng , Xiaokui Xiao , Wang Kay Ngai , Ben Kao , Sunil Prabhakar, Indexing multi-dimensional uncertain data with arbitrary probability density functions, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 30: Yufei Tao , Dimitris Papadias , Xiang Lian, Reverse kNN search in arbitrary dimensionality, Proceedings of the Thirtieth international conference on Very large data bases, p.744-755, August 31-September 03, 2004, Toronto, Canada
• 31: Yufei Tao , Dimitris Papadias , Xiang Lian , Xiaokui Xiao, Multidimensional reverse kNN search, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.3, p.293-316, July 2007 [doi>10.1007/s00778-005-0168-2]
• 32: Yannis Theodoridis , Timos Sellis, A model for the prediction of R-tree performance, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237705]
• 33: Wenwei Xue , Qiong Luo , Lei Chen , Yunhao Liu, Contour map matching for event detection in sensor networks, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142491]
• 34: Man Lung Yiu , Nikos Mamoulis, Efficient processing of top-k dominating queries on multi-dimensional data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria