This thesis addresses the problem of monitoring the k path nearest neighbours with respect to a continuously moving user approaching his destination in context of a road network. Given a destination where a user is going to, a 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. This query is called as the k-Path Nearest Neighbour query (k-PNN). There is a need for continuous monitoring of the initial obtained k-NN solution since the user is continuously moving towards his destination and the previously obtained solution set could dynamically change with time. The challenge of monitoring the k-PNN for a moving user is to dynamically determine the update locations and then refresh the k-PNN efficiently. We follow a similar path as presented in [11] where a three-phase Best-first Network Expansion (BNE) algorithm is proposed. 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’ and exact distances to the query path. Finally, the monitoring phase deals with computing update locations as well as refreshing the k-PNN based on the user’s position. Since monitoring is an expensive and resource consuming process, our work predominantly focuses on making the entire monitoring process more efficient and resource efficient, while maintaining the same level of accuracy. We present a novel approach for managing the update locations which could not only make the monitoring efficient but also decrease the total process time. Finally, we conduct extensive experiments on real road networks and compare our methods with the existing similar work and show that our method achieve satisfactory performance across various parameters.

[1] N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proceedings of SIGMOD, pages 71–79, 1995.

[2] G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. ACM Trans. Database Syst., 24(2):265–318, 1999.

[3] Geng Zhao, Kefeng Xuan, Wenny Rahayu, David Taniar, Maytham Safar, , Marina L. Gavrilova, and Bala Srinivasan. Voronoi-Based Continuous k Nearest NeighborSearch in Mobile Navigation. IEEE Transactions on Industrial Electronics, Vol. 58, Number 6, June 2011

[4] M. Safar and D. Ebrahimi, “eDAR algorithm for continuous KNN queries based on pine,” Int. J. Inf. Technol.Web Eng., vol. 1, number 4, pp. 1–21, 2006.

[5] H. Samer, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial database, SIGMOD 2008

[6] D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases. In Proceedings of VLDB, pages 802–813, 2003.

[7] Man Lung Yiu, Nikos Mamoulis, and Dimitris Papadias. Aggregate Nearest Neighbor Queries in Road Networks. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 17, Number 6, June 2005

[8] Guohui Li, Yanhong Li, LihChyun Shu and Ping Fan. CkNN Query Proccessing over Moving Objects with Uncertain Speeds in Road Network. APWeb 2011,LNCS 6612, pp. 65-76,2011

[9] k. Mouratidis, M. L. Yiu, D. Papadias, and N. Mamoulis. Continuous nearest neighbour monitoring in road networks. In Proceedings of VLDB, pages 43–54, 2006.

[10] S. Shekhar and J. S. Yoo. Processing in-route nearest neighbor queries: a comparison of alternative approaches. In Proceedings of GIS, pages 9–16, 2003.

[11] Zaiben Chen＋, Heng Tao Shen＋, Xiaofang Zhou＋, Jeffrey Xu Yu‡. Monitoring Path Nearest Neighbor in Road Networks. SIGMOD’09, June 29–July 2, 2009

[12] 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.

[13] S. Nutanong, R. Zhang, E. Tanin, and L. Kulik. The v*-diagram: a query-dependent approach to moving knn queries. Proc. VLDB Endow., 1(1):1095–1106, 2008.

[14] Y. Tao, D. Papadias, and Q. Shen. Continuous nearest neighbour search. In Proceedings of VLDB, pages 287–298, 2002.

[15] T. A. J. Nicholson. Finding the shortest route between two points in a network. Computer Journal, 9(3):275–280, 1966.

[16] E. W. Dijkstra. A note on two problems in connection with graphs. Numerische Math, 1:269–271, 1959.

[17] C. S. Jensen, J. Kol′aˇrvr, T. B. Pedersen, and I. Timko. Nearest neighbor queries in road networks In Proceedings of GIS, pages 1–8, 2003.

[18] C. Shahabi, M. R. Kolahdouzan, and M. Sharifzadeh. A road network embedding technique for k-nearest neighbor search in moving object databases. In Proceedings of GIS, pages 94–100, 2002.