Efficient search for the top-k probable nearest neighbors in uncertain databases

ABSTRACT

Uncertainty pervades many domains in our lives. Current real-life applications, e.g., location tracking using GPS devices or cell phones, multimedia feature extraction, and sensor data management, deal with different kinds of uncertainty. Finding the nearest neighbor objects to a given query point is an important query type in these applications.

In this paper, we study the problem of finding objects with the highest marginal probability of being the nearest neighbors to a query object. We adopt a general uncertainty model allowing for data and query uncertainty. Under this model, we define new query semantics, and provide several efficient evaluation algorithms. We analyze the cost factors involved in query evaluation, and present novel techniques to address the trade-offs among these factors. We give multiple extensions to our techniques including handling dependencies among data objects, and answering threshold queries. We conduct an extensive experimental study to evaluate our techniques on both real and synthetic data.

REFERENCES

• 1: Topologically integrated geographic encoding and referencing (tiger) system, http://www.census.gov/geo/www/tiger/.
• 2: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 3: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 4: Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564731]
• 5: J. Chen and R. Cheng. Efficient evaluation of imprecise location-dependent queries. In ICDE, 2007.
• 6: R. Cheng, J. Chen, M. Mokbel, and C. Chow. Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data. In ICDE, 2008.
• 7: 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]
• 8: X. Dai, M. L. Yiu, N. Mamoulis, Y. Tao, and M. Vaitis. Probabilistic spatial queries on existentially uncertain data. In SSTD, 2005.
• 9: Victor Teixeira de Almeida , Ralf Hartmut Güting, Supporting uncertainty in moving objects in network databases, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany [doi>10.1145/1097064.1097070]
• 10: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 11: H. Franco-Lopez, A. R. Ek, and M. E. Bauer. Estimation and mapping of forest stand density, volume, and cover type using the k-nearest neighbors method. Remote Sensing of Environment 2001.
• 12: J. Geweke. Efficient simulation from the multivariate normal and student---t distributions subject to linear constraints and the evaluation of constraint probabilities. In Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface, 1991.
• 13: M. Hadjieleftheriou. Spatial index library, http://research.att.com/~marioh/spatialindex/.
• 14: G. R. Hjaltason and H. Samet. Ranking in spatial databases. In SSD, 1995.
• 15: Dmitri V. Kalashnikov , Yiming Ma , Sharad Mehrotra , Ramaswamy Hariharan, Index for fast retrieval of uncertain spatial point data, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183471.1183504]
• 16: H.-P. Kriegel, P. Kunath, and M. Renz. Probabilistic nearest-neighbor query on uncertain objects. In DASFAA, 2007.
• 17: 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
• 18: E. Li, D. Boos, and M. Gumpertz. Simulation study in statistics. Journal of Interconnection Networks, 2001.
• 19: Qingshan Liu , Wang Yan , Hanqing Lu , Songde Ma, Occlusion Robust Face Recognition with Dynamic Similarity Features, Proceedings of the 18th International Conference on Pattern Recognition, p.544-547, August 20-24, 2006 [doi>10.1109/ICPR.2006.890]
• 20: V. Ljosa and A. K. Singh. Apla: Indexing arbitrary probability distributions. In ICDE, 2007.
• 21: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 22: Nikos Mamoulis , Man Lung Yiu , Kit Hung Cheng , David W. Cheung, Efficient top-k aggregation of ranked inputs, ACM Transactions on Database Systems (TODS), v.32 n.3, p.19-es, August 2007 [doi>10.1145/1272743.1272749]
• 23: K. Munagala, S. Babu, R. Motwani, and J. Widomy. The pipelined set cover problem. In ICDT, 2005.
• 24: C. Re, N. Dalvi, and D. Suciu. Efficient top-k query evaluation on probabilistic data. In ICDE, 2007.
• 25: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, ACM SIGMOD Record, v.24 n.2, p.71-79, May 1995
• 26: 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]
• 27: M. A. Soliman, I. F. Ilyas, and K. C. Chang. Top-k query processing in uncertain databases. In ICDE, 2007.
• 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 , Jun Zhang, Aggregate Processing of Planar Points, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.682-700, March 25-27, 2002
• 30: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 31: R. Yamamoto, H. Matsutani, H. Matsuki, T. Oono, and H. Ohtsuka. Position location technologies using signal strengths in cellular system. In VTC-Spring, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

General Terms:
Algorithms, Design, Management, Performance