Using Dijkstra's algorithm to incrementally find the k-Nearest Neighbors in spatial network databases

ABSTRACT

One of the most important kinds of queries in Spatial Network Databases (SNDB) to support Location-Based Services (LBS) is the k-Nearest Neighbors (k-NN) query. Given a point in a network, e.g. a location of a car on a road network, and a set of points of interests, e.g. hotels, gas stations, etc., the k-NN query returns the k points of interest closest to the query point. The network distance is used in such a query instead of the Euclidean distance. Dijkstra's algorithm is a well known solution to this problem. In this paper, we propose a storage schema with a set of index structures to support an efficient execution of a slightly modified version of the Dijkstra's algorithm. We show in an experimental evaluation with generated data sets that our proposal is more efficient than the state-of-the-art solution to this problem.

REFERENCES

• 1: Victor Teixeira De Almeida , Ralf Hartmut Güting, Indexing the Trajectories of Moving Objects in Networks*, Geoinformatica, v.9 n.1, p.33-60, March 2005 [doi>10.1007/s10707-004-5621-7]
• 2: J. Boyer. Algorithm alley. Dr. Dobb's, (9701), 1997.
• 3: Hyung-Ju Cho , Chin-Wan Chung, An efficient and scalable approach to CNN queries in a road network, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 4: E. W. Dijkstra. A note on two problems in connection with graphs. Numerische Mathematik, 1:269--271, 1959.
• 5: Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
• 6: 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]
• 7: X. Huang, C. S. Jensen, and S. Saltenis. The islands approach to nearest neighbor querying in spatial networks. In Proc. of the 9th Intl. Symp. on Spatial and Temporal Databases (SSTD), pages 73--90, 2005.
• 8: 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.
• 9: M. R. Kolahdouzan and C. Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In Proc. of 30th Intl. Conf. on Very Large Data Bases (VLDB), pages 840--851, 2004.
• 10: D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases. In Proc. of 29th Intl. Conf. on Very Large Data Bases (VLDB), pages 802--813, 2003.
• 11: 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
• 12: Shashi Shekhar , Duen-Ren Liu, CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.102-119, January 1997 [doi>10.1109/69.567054]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
index structures, location-based services, nearest neighbors, spatial databases