Monitoring path nearest neighbor in road networks

ABSTRACT

This paper addresses the problem of monitoring the k nearest neighbors to a dynamically changing path in road networks. Given a destination where a user is going to, this new query returns the k-NN with respect to the shortest path connecting the destination and the user's current location, and thus provides a list of nearest candidates for reference by considering the whole coming journey. We name this query the k-Path Nearest Neighbor query (k-PNN). As the user is moving and may not always follow the shortest path, the query path keeps changing. The challenge of monitoring the k-PNN for an arbitrarily moving user is to dynamically determine the update locations and then refresh the k-PNN efficiently. We propose a three-phase Best-first Network Expansion (BNE) algorithm for monitoring the k-PNN and the corresponding shortest path. In the searching phase, the BNE finds the shortest path to the destination, during which a candidate set that guarantees to include the k-PNN is generated at the same time. Then in the verification phase, a heuristic algorithm runs for examining candidates' exact distances to the query path, and it achieves significant reduction in the number of visited nodes. The monitoring phase deals with computing update locations as well as refreshing the k-PNN in different user movements. Since determining the network distance is a costly process, an expansion tree and the candidate set are carefully maintained by the BNE algorithm, which can provide efficient update on the shortest path and the k-PNN results. Finally, we conduct extensive experiments on real road networks and show that our methods achieve satisfactory performance.

REFERENCES

• 1: 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
• 2: 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
• 3: E. W. Dijkstra. A note on two problems in connection with graphs. Numerische Math, 1:269--271, 1959.
• 4: Andrew V. Goldberg , Chris Harrelson, Computing the shortest path: A search meets graph theory, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100--107, July 1968.
• 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: Christian S. Jensen , Jan Kolářvr , Torben Bach Pedersen , Igor Timko, Nearest neighbor queries in road networks, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.1-8, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956677]
• 8: Mohammad Kolahdouzan , Cyrus Shahabi, Voronoi-based K nearest neighbor search for spatial network databases, Proceedings of the Thirtieth international conference on Very large data bases, p.840-851, August 31-September 03, 2004, Toronto, Canada
• 9: F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng. On trip planning queries in spatial databases. In Proceedings of SSTD pages 273--290, 2005.
• 10: Kyriakos Mouratidis , Dimitris Papadias , Marios Hadjieleftheriou, Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066230]
• 11: Kyriakos Mouratidis , Man Lung Yiu , Dimitris Papadias , Nikos Mamoulis, Continuous nearest neighbor monitoring in road networks, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 12: T. A. J. Nicholson. Finding the shortest route between two points in a network. Computer Journal 9(3):275--280, 1966.
• 13: Sarana Nutanong , Rui Zhang , Egemen Tanin , Lars Kulik, The V*-Diagram: a query-dependent approach to moving KNN queries, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453973]
• 14: 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
• 15: Dimitris Papadias , Jun Zhang , Nikos Mamoulis , Yufei Tao, Query processing in spatial network databases, Proceedings of the 29th international conference on Very large data bases, p.802-813, September 09-12, 2003, Berlin, Germany
• 16: Lu Qin , Jeffrey Xu Yu , Bolin Ding , Yoshiharu Ishikawa, Monitoring Aggregate k-NN Objects in Road Networks, Proceedings of the 20th international conference on Scientific and Statistical Database Management, July 09-11, 2008, Hong Kong, China [doi>10.1007/978-3-540-69497-7_13]
• 17: 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
• 18: Hanan Samet , Jagan Sankaranarayanan , Houman Alborzi, Scalable network distance browsing in spatial databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376623]
• 19: 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]
• 20: 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]
• 21: Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
• 22: Man Lung Yiu , Nikos Mamoulis , Dimitris Papadias, Aggregate Nearest Neighbor Queries in Road Networks, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.820-833, June 2005 [doi>10.1109/TKDE.2005.87]
• 23: Jin Soung Yoo , Shashi Shekhar, In-Route Nearest Neighbor Queries, Geoinformatica, v.9 n.2, p.117-137, June 2005 [doi>10.1007/s10707-005-6671-1]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
path nearest neighbor, road networks, spatial databases