Aggregate nearest neighbor queries in spatial databases

ABSTRACT

Given two spatial datasets P (e.g., facilities) and Q (queries), an aggregate nearest neighbor (ANN) query retrieves the point(s) of P with the smallest aggregate distance(s) to points in Q. Assuming, for example, n users at locations q1,…qn, an ANN query outputs the facility p ∈ P that minimizes the sum of distances |pqi| for 1 ≤ i ≤ n that the users have to travel in order to meet there. Similarly, another ANN query may report the point p ∈ P that minimizes the maximum distance that any user has to travel, or the minimum distance from some user to his/her closest facility. If Q fits in memory and P is indexed by an R-tree, we develop algorithms for aggregate nearest neighbors that capture several versions of the problem, including weighted queries and incremental reporting of results. Then, we analyze their performance and propose cost models for query optimization. Finally, we extend our techniques for disk-resident queries and approximate ANN retrieval. The efficiency of the algorithms and the accuracy of the cost models are evaluated through extensive experiments with real and synthetic datasets.

REFERENCES

• 1: Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Charu C. Aggarwal , Philip S. Yu, Outlier detection for high dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.37-46, May 21-24, 2001, Santa Barbara, California, United States
• 3: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 4: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 5: Rimantas Benetis , Christian S. Jensen , Gytis Karciauskas , Simonas Saltenis, Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects, Proceedings of the 2002 International Symposium on Database Engineering & Applications, p.44-53, July 17-19, 2002
• 6: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263671]
• 7: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 8: Christian Böhm, A cost model for query processing in high dimensional data spaces, ACM Transactions on Database Systems (TODS), v.25 n.2, p.129-178, June 2000 [doi>10.1145/357775.357776]
• 9: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, Top-k selection queries over relational databases: Mapping strategies and performance evaluation, ACM Transactions on Database Systems (TODS), v.27 n.2, p.153-187, June 2002 [doi>10.1145/568518.568519]
• 10: Yuan-Chi Chang , Lawrence Bergman , Vittorio Castelli , Chung-Sheng Li , Ming-Ling Lo , John R. Smith, The onion technique: indexing for linear optimization queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.391-402, May 15-18, 2000, Dallas, Texas, United States
• 11: King Lum Cheung , Ada Wai-Chee Fu, Enhanced nearest neighbour search on the R-tree, ACM SIGMOD Record, v.27 n.3, p.16-21, Sept. 1, 1998 [doi>10.1145/290593.290596]
• 12: Antonio Corral , Yannis Manolopoulos , Yannis Theodoridis , Michael Vassilakopoulos, Closest pair queries in spatial databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.189-200, May 15-18, 2000, Dallas, Texas, United States
• 13: Ronald Fagin, Combining fuzzy information: an overview, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565143]
• 14: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 15: 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
• 16: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 17: Henrich, A. 1994. A distance scan algorithm for spatial access structures. In Proceedings of ACM Workshop on Geographic Information Systems (ACM GIS) (Gaithersburg, Md., Dec.). ACM, New York, 136--143.
• 18: Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.237-248, June 01-04, 1998, Seattle, Washington, United States
• 19: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 20: Sepp Hochreiter , A. Steven Younger , Peter R. Conwell, Learning to Learn Using Gradient Descent, Proceedings of the International Conference on Artificial Neural Networks, p.87-94, August 21-25, 2001
• 21: Vagelis Hristidis , Yannis Papakonstantinou, Algorithms and applications for answering ranked queries using ranked views, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.1, p.49-70, January 2004 [doi>10.1007/s00778-003-0099-8]
• 22: Kolahdouzan, M. and Shahabi, C. 2004. Voronoi-based K nearest neighbor search for spatial network databases. In Proceedings of Very Large Data Bases Conference (VLDB) (Toronto, Ont., Canada, Aug.). 840--851.
• 23: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, Nearest Neighbor Queries in a Mobile Environment, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.119-134, September 10-11, 1999
• 24: Flip Korn , Bernd-Uwe Pagel , Christos Faloutsos, On the 'Dimensionality Curse' and the 'Self-Similarity Blessing', IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.96-111, January 2001 [doi>10.1109/69.908983]
• 25: Liu, X. and Ferhatosmanoglu, H. 2003. Efficient k-NN search on streaming data series. In Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD) (Santorini Island, Greece, July). 83--101.
• 26: Koji Nakano , Stephen Olariu, An Optimal Algorithm for the Angle-Restricted All Nearest Neighbor Problem on the Reconfigurable Mesh, with Applications, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.983-990, September 1997 [doi>10.1109/71.615443]
• 27: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 28: Dimitris Papadias , Qiongmao Shen , Yufei Tao , Kyriakos Mouratidis, Group Nearest Neighbor Queries, Proceedings of the 20th International Conference on Data Engineering, p.301, March 30-April 02, 2004
• 29: Papadias, D., Zhang, J., Mamoulis, N., and Tao, Y. 2003. Query processing in spatial network databases. In Proceedings of Very Large Data Bases Conference (VLDB) (Berlin, Germany, Sept.). 802--813.
• 30: Apostolos Papadopoulos , Yannis Manolopoulos, Performance of Nearest Neighbor Queries in R-Trees, Proceedings of the 6th International Conference on Database Theory, p.394-408, January 08-10, 1997
• 31: Press, W., Flannery, B., Teukolsky, S., and Vetterling, W. 2002. Numerical recipes in C++ (second edition). Cambridge University Press, ISBN 0-521-75034-2.
• 32: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 33: Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation, Proceedings of the 26th International Conference on Very Large Data Bases, p.516-526, September 10-14, 2000
• 34: Shan, J., Zhang, D., and Salzberg, B. 2003. On spatial-range closest-pair query. In Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD) (Santorini Island, Greece, July). 252--269.
• 35: Zhexuan Song , Nick Roussopoulos, K-Nearest Neighbor Search for Moving Query Point, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.79-96, July 12-15, 2001
• 36: Sproull, R. 1991. Refinements to nearest neighbor searching in K-dimensional trees. Algorithmica 6, 4, 579--589.
• 37: Yufei Tao , Dimitris Papadias, Spatial queries in dynamic environments, ACM Transactions on Database Systems (TODS), v.28 n.2, p.101-139, June 2003 [doi>10.1145/777943.777944]
• 38: Yufei Tao , Jun Zhang , Dimitris Papadias , Nikos Mamoulis, An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1169-1184, October 2004 [doi>10.1109/TKDE.2004.48]
• 39: Yannis Theodoridis , Emmanuel Stefanakis , Timos Sellis, Efficient Cost Models for Spatial Queries Using R-Trees, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.19-32, January 2000 [doi>10.1109/69.842247]
• 40: 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
• 41: Welzl, E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science. Springer-Verlag, Lecture Notes in Computer Science, vol. 555. New York, 359--370.
• 42: Wesolowsky, G. 1993. The Weber problem: History and perspectives. Loc. Sci. 1, 1, 5--23.
• 43: Xiaopeng Xiong , Mohamed F. Mokbel , Walid G. Aref, SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.643-654, April 05-08, 2005 [doi>10.1109/ICDE.2005.128]
• 44: Cui Yu , Beng Chin Ooi , Kian-Lee Tan , H. V. Jagadish, Indexing the Distance: An Efficient Method to KNN Processing, Proceedings of the 27th International Conference on Very Large Data Bases, p.421-430, September 11-14, 2001
• 45: Xiaohui Yu , Ken Q. Pu , Nick Koudas, Monitoring k-Nearest Neighbor Queries over Moving Objects, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.631-642, April 05-08, 2005 [doi>10.1109/ICDE.2005.92]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

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

General Terms:
Algorithms, Experimentation

Keywords:
Spatial database, aggregation, nearest neighbor queries