Processing in-route nearest neighbor queries: a comparison of alternative approaches

ABSTRACT

Nearest neighbor query is one of the most important operations in spatial databases and their application domains, e.g., location-based services, advanced traveler information systems, etc. This paper addresses the problem of finding the in-route nearest neighbor (IRNN) for a query object tuple which consists of a given route with a destination and a current location on it. The IRNN is a facility instance via which the detour from the original route on the way to the destination is smallest. This paper addresses four alternative solution methods. Comparisons among them are presented using an experimental framework. Several experiments using real road map datasets are conducted to examine the behavior of the solutions in terms of three parameters affecting the performance. Our experiments show that the computation costs for all methods except the precomputed zone-based method increase with increases in the road map size and the query route length but decreases with increase in the facility density. The precomputed zone-based method shows the most efficiency when there are no updates on the road map.

REFERENCES

• 1: 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
• 2: C. Shahabi, M. R. Kolahdouzan, M Sharifzadeh, A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases, SSTD, 2001.
• 3: GITA and OGC's Emerging Technology Summit Series -Location-Based Services. http://www.openls.org/dvd1/ets1/index.htm.
• 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: 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
• 6: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 7: J. H. Rillings and R. J. Betsold. Advanced Driver Information Systems. IEEE Trans. on Vehicular Technology, 1991.
• 8: J. L. Wright, R. Starr, S.Gargaro, GENESIS-Information on the Move, In Proc. of Annual IVHS American Conference, 1993.
• 9: J. Zhang, N. Mamoulis, D. Papadias, Y. Tao, All-Nearest-Neighbors Queries in Spatial Databses, 2002.
• 10: J. Feng, T. Watanbe, Fast Search of Nearest Target Object in Urban District Road Networks, PYIWIT, 2002.
• 11: Michael Worboys , Matt Duckham, GIS: A Computing Perspective, 2nd Edition, CRC Press, Inc., Boca Raton, FL, 2004
• 12: 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
• 13: S. Shekhar, R. R. Vatsava, X. Ma, J. Yoo, Navigation Systems: A Spatial Database Perspective, In chapter 3 of the book, Location-Based Services, 2003.
• 14: S. Shekhar, S.Chawla, Spatial Databases: A Tour, Prentice Hall, 2003.
• 15: S. Shekhar, M. Coyle, A. Kohli, Path Computation Algorithms for Advanced Traveller Information Systems, IEEE Computer Society, 1993.
• 16: S. Shekhar, A. Fetterer, D. Liu, Genesis: An Approach to Data Dissemination in in Advanced Travel Information Systems, Bulletin of the Technical Committee on Data Engineering: Special Issue on Data Dissemination, 1996.
• 17: Shashi Shekhar , Andrew Fetterer , Bjajesh Goyal, Materialization Trade-Offs in Hierarchical Shortest Path Algorithms, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.94-111, July 15-18, 1997
• 18: Sergei Bespamyatnikh , Jack Snoeyink, Queries with segments in Voronoi diagrams, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.122-129, January 17-19, 1999, Baltimore, Maryland, United States
• 19: S. Hakimi, M. Labbe, and E. Schmeichel, The Voronoi Partition of a Network and its Implications Location Theory ORSA, 1992.
• 20: Stefan Berchtold , Bernhard Ertl , Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl, Fast Nearest Neighbor Search in High-Dimensional Space, Proceedings of the Fourteenth International Conference on Data Engineering, p.209-218, February 23-27, 1998
• 21: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 22: W. Clay Collier , Richard J. Weiland, Smart cars, smart highways, IEEE Spectrum, v.31 n.4, p.27-33, April 1994 [doi>10.1109/6.272224]
• 23: Y. Tao, D. Papdias, Q. Shen, Continuous Nearest Neighbor Search, VLDB, 2002.
• 24: 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

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
advanced traveler information systems, location-based services, nearest neighborhood query, road network, route