Towards optimal continuous nearest neighbor queries in spatial databases

ABSTRACT

One of the most important kind of queries in spatial data-bases to support location-based services (LBS) is the continuous nearest neighbors (CNN) query. Given a spatial data set of points of interest and a moving query point q, the CNN query partitions q into a set of adjacent disjoint intervals associated with their nearest points of interest. Existing solutions to this problem are known to be sub-optimal in terms of disk accesses. In this paper, we present an algorithm to compute the CNN query that is I/O optimal. With an experimental evaluation, we show that not only the number of disk accesses is reduced with the optimal algorithm, but also the CPU performance is improved, in some cases.

REFERENCES

• 1: 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
• 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: 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
• 4: 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]
• 5: C. S. Jensen, A. Friis-Christensen, T. B. Pedersen, D. Pfoser, S. Saltenis, and N. Tryfona. Location-based services: A database perspective. In Proc. of the 8th Scandinavian Research Conference on Geographical Information Science (ScanGIS), pages 59--68, 2001.
• 6: 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
• 7: K. Raptopoulou , A. N. Papadopoulos , Y. Manolopoulos, Fast Nearest-Neighbor Query Processing in Moving-Object Databases, Geoinformatica, v.7 n.2, p.113-137, June 2003 [doi>10.1023/A:1023403908170]
• 8: 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
• 9: 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
• 10: Yufei Tao , Dimitris Papadias, Time-parameterized queries in spatio-temporal databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564730]
• 11: Y. Tao, D. Papadias, and Q. Shen. Continuous nearest neighbor search. In Proc. of 28th Intl. Conf. on Very Large Data Bases (VLDB), pages 287--298, 2002.
• 12: Baihua Zheng , Dik Lun Lee, Semantic Caching in Location-Dependent Query Processing, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.97-116, July 12-15, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Experimentation, Performance

Keywords:
continuous nearest neighbors, location based services, spatial databases