Exploiting a page-level upper bound for multi-type nearest neighbor queries

ABSTRACT

Given a query point and a collection of spatial features, a multi-type nearest neighbor (MTNN) query finds the shortest tour for the query point such that only one instance of each feature is visited during the tour. For example, a tourist may be interested in finding the shortest tour which starts at a hotel and passes through a post office, a gas station, and a grocery store. The MTNN query problem is different from the traditional nearest neighbor query problem in that there are many objects for each feature type and the shortest tour should pass through only one object from each feature type. In this paper, we propose an R-tree based algorithm that exploits a page-level upper bound for efficient computation in clustered data sets and finds optimal query results. We compare our method with a recently proposed method, RLORD, which was developed to solve the optimal sequenced route (OSR) query. In our view, OSR represents a spatially constrained version of MTNN. Experimental results are provided to show the strength of our algorithm and design decisions related to performance tuning.

REFERENCES

• 1: 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]
• 2: 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]
• 3: K. Clarkson. Fast Algorithms for the All-Nearest-Neighbors Problem. In FOCS, 1983.
• 4: John Gerald Cleary, Analysis of an Algorithm for Finding Nearest Neighbors in Euclidean Space, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.183-192, June 1979 [doi>10.1145/355826.355832]
• 5: 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
• 6: A. Corral , Y. Manolopoulos , Y. Theodoridis , M. Vassilakopoulos, Algorithms for processing K-closest-pair queries in spatial databases, Data & Knowledge Engineering, v.49 n.1, p.67-104, 1 April 2004 [doi>10.1016/j.datak.2003.08.007]
• 7: Antonio Corral , Michael Vassilakopoulos , Yannis Manolopoulos, The Impact of Buffering on Closest Pairs Queries Using R-Trees, Proceedings of the 5th East European Conference on Advances in Databases and Information Systems, p.41-54, September 25-28, 2001
• 8: Congjun Yang , King-Ip Lin, An Index Structure for Efficient Reverse Nearest Neighbor Queries, Proceedings of the 17th International Conference on Data Engineering, p.485-492, April 02-06, 2001
• 9: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 10: Hakan Ferhatosmanoglu , Ioana Stanoi , Divyakant Agrawal , Amr El Abbadi, Constrained Nearest Neighbor Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.257-278, July 12-15, 2001
• 11: 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
• 12: 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]
• 13: Flip Korn , S. Muthukrishnan, Influence sets based on reverse nearest neighbor queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.201-212, May 15-18, 2000, Dallas, Texas, United States
• 14: F. Korn, S. Muthukrishnan, and D. Srivastava. Reverse nearest neighbor aggregates over data stream. In VLDB, 2002.
• 15: F. Li, D. Chen, M. Hadjieleftherious, G. Kollios, and S. Teng. On trip planning queries in spatial databases. In SSTD, 2005.
• 16: X. Ma, S. Shekhar, H. Xiong, and P. Zhang. Exploiting a page-level upper bound for multi-type nearest neighbor queries. In TR 05-008, CS, UMN, 2005.
• 17: 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
• 18: 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
• 19: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 20: 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
• 21: M. Sharifzadeh, M. Kolahdouzan, and C. Shahabi. The optimal sequenced route query. In TR 05-840, CS, USC, January 2005.
• 22: I. Stanoi, D. Agrawal, and A. E. Abbadi. Reverse nearest neighbor queries for dynamic databases. In SIGMOD workshop on Research Issues in data mining and knowledge discovery, 2000.
• 23: 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
• 24: Y. Tao, D. Papadias, and Q. Shen. Continuous Nearest Neighbor Search. In VLDB, 2002.
• 25: J. Zhang, N. Mamoulis, D. Papadias, and Y. Tao. All-Nearest-Neighbors Queries in Spatial Databases. In SSDBM, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms

Keywords:
GIS, MTNN query, location-based service