Adaptive nearest neighbor queries in travel time networks

ABSTRACT

Nearest neighbor (NN) searches represent an important class of queries in geographic information systems (GIS). Most nearest neighbor algorithms rely on static distance information to compute NN queries (e.g., Euclidean distance or spatial network distance). However, the final goal of a user when performing an NN search is often to travel to one of the points of the search result. In this case, finding the nearest neighbors in terms of travel time is more important than the actual distance. In the existing NN algorithms dynamic real-time events (e.g., traffic congestions, detours, etc.) are usually not considered and hence the pre-computed nearest neighbor objects may not accurately reflect the shortest travel time. In this paper we propose a novel travel time network that integrates both spatial networks and real-time traffic event information. Based on this foundation of the travel time network, we develop a local-based greedy nearest neighbor algorithm and a global-based adaptive nearest neighbor algorithm that both utilize real-time traffic information to provide adaptive nearest neighbor search results. We have performed a theoretical analysis and simulations to verify our methods. The results indicate that our algorithms remarkably reduce the travel time compared with previous nearest neighbor solutions.

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: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 3: Albert M.K. Cheng and Koushik Rajan. A Digital Map/GPS Based Routing and Addressing Scheme for Wireless Ad-hoc Networks. In Proceedings of the IEEE Intelligent Vehicle Symposium (IV'03), 2003.
• 4: Zhiming Ding and Ralf Hartmut Güting. Modeling temporally variable transportation networks. In Database Systems for Advances Applications, 9th International Conference, DASFAA 2004, Jeju Island, Korea, Proceedings, pages 154--168, 2004.
• 5: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 6: 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
• 7: 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]
• 8: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Integrated Query Processing Strategies for Spatial Path Queries, Proceedings of the Thirteenth International Conference on Data Engineering, p.477-486, April 07-11, 1997
• 9: Mohammad R. Kolahdouzan and Cyrus Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, pages 840--851, 2004.
• 10: Duke Lee, Roberto Attias, Anuj Puri, Raja Sengupta, Stavros Tripakis, and Pravin Varaiya. A wireless token ring protocol for intelligent transportation systems. In Proceedings of the 4th International IEEE Conference on Intelligent Transportation Systems, 2001.
• 11: Jun Luo and Jean-Pierre Hubaux. A Survey of Inter-Vehicle Communication. Technical Report IC/2004/24, School of Computer and Communication Sciences, EPFL, 2004.
• 12: Jörg Ott and Dirk Kutscher. Drive-thru internet: Ieee 802.11b for "automobile" users. In INFOCOM, 2004.
• 13: Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao. Query Processing in Spatial Network Databases. In Proceedings of the International Conference on Very Large Databases (VLDB), pages 790--801, 2003.
• 14: 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
• 15: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 16: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 17: Cyrus Shahabi , Mohammad R. Kolahdouzan , Mehdi Sharifzadeh, A road network embedding technique for k-nearest neighbor search in moving object databases, Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09, 2002, McLean, Virginia, USA [doi>10.1145/585147.585167]
• 18: Shashi Shekhar , Jin Soung Yoo, Processing in-route nearest neighbor queries: a comparison of alternative approaches, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.9-16, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956678]
• 19: Jing Tian, Lu Han, and Kurt Rothermel. Spatially Aware Packet Routing for Mobile Ad Hoc Inter-Vehicle Radio Networks. In Proceedings of the IEEE Intelligent Transportation System Conference (ITSC'03), 2003.

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
advanced traveler information systems, location-based services, nearest neighbor query, travel time network