Monochromatic and bichromatic reverse skyline search over uncertain databases

ABSTRACT

Reverse skyline queries over uncertain databases have many important applications such as sensor data monitoring and business planning. Due to the existence of uncertainty in many real-world data, answering reverse skyline queries accurately and efficiently over uncertain data has become increasingly important. In this paper, we model the probabilistic reverse skyline query on uncertain data, in both monochromatic and bichromatic cases, and propose effective pruning methods to reduce the search space of query processing. Moreover, efficient query procedures have been presented seamlessly integrating the proposed pruning methods. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed approach with various experimental settings.

REFERENCES

• 1: 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]
• 2: 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
• 3: J. Chen and R. Cheng. Efficient evaluation of imprecise location-dependent queries. In Proc. 23rd Int. Conf. on Data Engineering, pages 586--595, 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: R. Cheng and J. Chen. Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 6: 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]
• 7: 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]
• 8: Reynold Cheng , Yuni Xia , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter, Efficient indexing methods for probabilistic threshold queries over uncertain data, Proceedings of the Thirtieth international conference on Very large data bases, p.876-887, August 31-September 03, 2004, Toronto, Canada
• 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: K. Deng, X. Zhou, and H. T. Shen. Multi-source skyline query processing in road networks. In Proc. 23rd Int. Conf. on Data Engineering, pages 796--805, 2007.
• 11: 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
• 12: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 13: J. M. Kang, M. F. Mokbel, S. Shekhar, T. Xia, and D. Zhang. Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors. In Proc. 23rd Int. Conf. on Data Engineering, pages 806--815, 2007.
• 14: C. Koch, D. Olteanu, L. Antova, and T. Jansen. Fast and simple relational processing of uncertain data. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 15: 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.
• 16: H.-P. Kriegel, P. Kunath, M. Pfeifle, and M. Renz. Probabilistic similarity join on uncertain data. In Proc. 11th Int. Conf. on Database Systems for Advanced Applications, 2006.
• 17: H.-P. Kriegel, P. Kunath, and M. Renz. Probabilistic nearest-neighbor query on uncertain objects. In Proc. 12th Int. Conf. on Database Systems for Advanced Applications, 2007.
• 18: V. Ljosa and A. K. Singh. APLA: indexing arbitrary probability distributions. In Proc. 23rd Int. Conf. on Data Engineering, pages 247--258, 2007.
• 19: V. Ljosa and A. K. Singh. Top-k spatial joins of probabilistic objects. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 20: 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]
• 21: 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
• 22: S. Prabhakar, C. Mayfield, R. Cheng, S. Singh, R. Shah, J. Neville, and S. Hambrusch. Database support for pdf attributes. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 23: C. Re, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proc. 23rd Int. Conf. on Data Engineering, 2007.
• 24: Anish Das Sarma , Omar Benjelloun , Alon Halevy , Jennifer Widom, Working Models for Uncertain Data, Proceedings of the 22nd International Conference on Data Engineering, p.7, April 03-07, 2006 [doi>10.1109/ICDE.2006.174]
• 25: S. Singh, C. Mayfield, R. Shah, S. Prabhakar, S. Hambrusch, J. Neville, and R. Cheng. Database support for pdf attributes. In Proc. 24th Int. Conf. on Data Engineering, 2008.
• 26: M. A. Soliman, I. F. Ilyas, and K. C. Chang. Top-k query processing in uncertain databases. In Proc. 23rd Int. Conf. on Data Engineering, 2007.
• 27: Ioana Stanoi , Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, Discovery of Influence Sets in Frequently Updated Databases, Proceedings of the 27th International Conference on Very Large Data Bases, p.99-108, September 11-14, 2001
• 28: 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
• 29: 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
• 30: Y. Tao, D. Papadias, X. Lian, and X. Xiao. Multidimensional reverse kNN search. In The VLDB Journal, 2005.
• 31: 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]
• 32: P. S. Yu and C. Aggarwal. On high dimensional indexing of uncertain data. In Proc. 24th Int. Conf. on Data Engineering, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
bichromatic reverse skyline, monochromatic reverse skyline, uncertain database