Query answering techniques on uncertain and probabilistic data: tutorial summary

ABSTRACT

Uncertain data are inherent in some important applications, such as environmental surveillance, market analysis, and quantitative economics research. Due to the importance of those applications and the rapidly increasing amount of uncertain data collected and accumulated, analyzing large collections of uncertain data has become an important task and has attracted more and more interest from the database community. Recently, uncertain data management has become an emerging hot area in database research and development. In this tutorial, we systematically review some representative studies on answering various queries on uncertain and probabilistic data.

REFERENCES

• 1: Serge Abiteboul , Paris Kanellakis , Gosta Grahne, On the representation and querying of sets of possible worlds, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.34-48, May 27-29, 1987, San Francisco, California, United States
• 2: Parag Agrawal , Omar Benjelloun , Anish Das Sarma , Chris Hayworth , Shubha Nabar , Tomoe Sugihara , Jennifer Widom, Trio: a system for data, uncertainty, and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: P. Agrawal and J. Widom. Confidence-aware joins in large uncertain databases. Technical report, Stanford University CA, USA.
• 4: Dana Angluin , Leslie G. Valiant, Fast probabilistic algorithms for hamiltonian circuits and matchings, Proceedings of the ninth annual ACM symposium on Theory of computing, p.30-41, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803393]
• 5: 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]
• 6: 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
• 7: Doug Burdick , Prasad M. Deshpande , T. S. Jayram , Raghu Ramakrishnan , Shivakumar Vaithyanathan, OLAP over uncertain and imprecise data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 8: Doug Burdick , Prasad M. Deshpande , T. S. Jayram , Raghu Ramakrishnan , Shivakumar Vaithyanathan, Efficient allocation algorithms for OLAP over imprecise data, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 9: Doug Burdick , AnHai Doan , Raghu Ramakrishnan , Shivakumar Vaithyanathan, OLAP over imprecise data with domain constraints, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 10: Roger Cavallo , Michael Pittarelli, The Theory of Probabilistic Databases, Proceedings of the 13th International Conference on Very Large Data Bases, p.71-81, September 01-04, 1987
• 11: 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]
• 12: Reynold Cheng , Sarvjeet Singh , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter , Yuni Xia, Efficient join processing over uncertain data, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183719]
• 13: 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
• 14: X. Dai, M. L. Yiu, N. Mamoulis, Y. Tao, and M. Vaitis. Probabilistic spatial queries on existentially uncertain data. In Advances in Spatial and Temporal Databases, Proceedings of the 9th International Symposium (SSTD'05), volume 3633 of Lecture Notes in Computer Science, pages 400--417, Angra dos Reis, Brazil, August 2005. Springer.
• 15: Nilesh Dalvi , Dan Suciu, The dichotomy of conjunctive queries on probabilistic structures, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265571]
• 16: Nilesh Dalvi , Dan Suciu, Management of probabilistic data: foundations and challenges, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-12, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265531]
• 17: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 18: Nilesh Dalvi , Dan Suciu, Answering queries from statistics and probabilistic views, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 19: Debabrata Dey , Sumit Sarkar, A probabilistic relational model and algebra, ACM Transactions on Database Systems (TODS), v.21 n.3, p.339-369, Sept. 1996 [doi>10.1145/232753.232796]
• 20: Xin Dong , Alon Y. Halevy , Cong Yu, Data integration with uncertainty, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 21: T. J. Green and V. Tannen. Models for incomplete and probabilistic information. IEEE Data Eng. Bull., 29(1):17--24, 2006.
• 22: M. Hua, J. Pei, W. Zhang, and X. Lin. Efficiently answering probabilistic threshold top-k queries on uncertain data (extended abstract). In Proc. International Conference on Data Engineering (ICDE'08), Cancun, Mexico, April 2008.
• 23: 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]
• 24: 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]
• 25: Benny Kimelfeld , Yehoshua Sagiv, Maximally joining probabilistic data, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265572]
• 26: K. Lange. Numerical analysis for statisticians. Statistics and computing. 1999.
• 27: 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]
• 28: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 29: 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
• 30: 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
• 31: C. Ré, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In Proceedings of the 23nd International Conference on Data Engineering (ICDE'07), Istanbul, Turkey, April 2007. IEEE.
• 32: Christopher Ré , Dan Suciu, Materialized views in probabilistic databases: for information exchange and query optimization, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 33: 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]
• 34: David B. Shmoys , Chaitanya Swamy, Stochastic Optimization is (Almost) as easy as Deterministic Optimization, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.228-237, October 17-19, 2004 [doi>10.1109/FOCS.2004.62]
• 35: 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]
• 36: M. A. Soliman, I. F. Ilyas, and K. C.-C. Chang. Top-k query processing in uncertain databases. In Proceedings of the 23nd International Conference on Data Engineering (ICDE'07), Istanbul, Turkey, April 2007. IEEE.
• 37: 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
• 38: Yufei Tao , Xiaokui Xiao , Reynold Cheng, Range search on multidimensional uncertain data, ACM Transactions on Database Systems (TODS), v.32 n.3, p.15-es, August 2007 [doi>10.1145/1272743.1272745]
• 39: K. Yi, F. Li, D. Srivastava, and G. Kollios. Efficient processing of top-k queries in uncertain databases. In Proc. 2008 International Conference on Data Engineering (ICDE'08), April 2008.
• 40: X. Zhang and J. Chomicki. On the semantics and evaluation of topk queries in probabilistic databases. In Proc. the Second International Workshop on Ranking in Databases (DBRank'08), April 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
probabilistic data, query processing, uncertain data