Evaluating probability threshold k-nearest-neighbor queries over uncertain data

ABSTRACT

In emerging applications such as location-based services, sensor monitoring and biological management systems, the values of the database items are naturally imprecise. For these uncertain databases, an important query is the Probabilistic k-Nearest-Neighbor Query (k-PNN), which computes the probabilities of sets of k objects for being the closest to a given query point. The evaluation of this query can be both computationally- and I/O-expensive, since there is an exponentially large number of k object-sets, and numerical integration is required. Often a user may not be concerned about the exact probability values. For example, he may only need answers that have sufficiently high confidence. We thus propose the Probabilistic Threshold k-Nearest-Neighbor Query (T-k-PNN), which returns sets of k objects that satisfy the query with probabilities higher than some threshold T. Three steps are proposed to handle this query efficiently. In the first stage, objects that cannot constitute an answer are filtered with the aid of a spatial index. The second step, called probabilistic candidate selection, significantly prunes a number of candidate sets to be examined. The remaining sets are sent for verification, which derives the lower and upper bounds of answer probabilities, so that a candidate set can be quickly decided on whether it should be included in the answer. We also examine spatially-efficient data structures that support these methods. Our solution can be applied to uncertain data with arbitrary probability density functions. We have also performed extensive experiments to examine the effectiveness of our methods.

REFERENCES

• 1: P. A. Sistla, O. Wolfson, S. Chamberlain, and S. Dao, "Querying the uncertain position of moving objects," in Temporal Databases: Research and Practice, 1998.
• 2: D. Pfoser and C. Jensen, "Capturing the uncertainty of moving-objects representations," in Proc. SSDBM, 1999.
• 3: Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
• 4: 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]
• 5: V. Ljosa and A. K. Singh, "APLA: Indexing arbitrary probability distributions," in Proc. ICDE, 2007.
• 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: J. Chen and R. Cheng, "Efficient evaluation of imprecise location-dependent queries," in Proc. ICDE, 2007.
• 8: 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
• 9: 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]
• 10: 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
• 11: 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
• 12: Glenn S. Iwerks , Hanan Samet , Ken Smith, Continuous K-nearest neighbor queries for continuously moving points with updates, Proceedings of the 29th international conference on Very large data bases, p.512-523, September 09-12, 2003, Berlin, Germany
• 13: Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi , Krishan Sabnani, Streaming Algorithms for Robust, Real-Time Detection of DDoS Attacks, Proceedings of the 27th International Conference on Distributed Computing Systems, p.4, June 25-27, 2007 [doi>10.1109/ICDCS.2007.142]
• 14: Usama M. Fayyad , Gregory Piatetsky-Shapiro , Padhraic Smyth , Ramasamy Uthurusamy, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 15: Nick Koudas , Beng Chin Ooi , Kian-Lee Tan , Rui Zhang, Approximate NN queries on streams with guaranteed error/performance bounds, Proceedings of the Thirtieth international conference on Very large data bases, p.804-815, August 31-September 03, 2004, Toronto, Canada
• 16: George Beskales , Mohamed A. Soliman , Ihab F. IIyas, Efficient search for the top-k probable nearest neighbors in uncertain databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453895]
• 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: 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
• 19: Lyublena Antova , Christoph Koch , Dan Olteanu, Query language support for incomplete information in the MayBMS system, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 20: Sarvjeet Singh , Chris Mayfield , Sagar Mittal , Sunil Prabhakar , Susanne Hambrusch , Rahul Shah, Orion 2.0: native support for uncertain data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376744]
• 21: Singh et al, "Database support for pdf attributes," in Proc. ICDE, 2008.
• 22: 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]
• 23: H. Kriegel, P. Kunath, and M. Renz, "Probabilistic nearest-neighbor query on uncertain objects," in DASFAA, 2007.
• 24: Y. Qi, S. Singh, R. Shah, and S. Prabhakar, "Indexing probabilistic nearest-neighbor threshold queries," in Proc. Workshop on Management of Uncertain Data, 2008.
• 25: Xiang Lian , Lei Chen, Probabilistic Group Nearest Neighbor Queries in Uncertain Databases, IEEE Transactions on Knowledge and Data Engineering, v.20 n.6, p.809-824, June 2008 [doi>10.1109/TKDE.2008.41]
• 26: R. Cheng, J. Chen, M. Mokbel, and C. Chow, "Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data," in Proc. ICDE, 2008.
• 27: 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
• 28: 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
• 29: 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]
• 30: M. Soliman, I. Ilyas, and K. Chang, "Top-k query processing in uncertain databases," in Proc. ICDE, 2007.
• 31: 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]
• 32: Vibhor Rastogi , Dan Suciu , Evan Welbourne, Access control over uncertain data, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453945]
• 33: Christoph Koch , Dan Olteanu, Conditioning probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453894]
• 34: Reynold Cheng , Jinchuan Chen , Xike Xie, Cleaning uncertain data with quality guarantees, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453935]
• 35: 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