Abstract   Reverse K#Nearest Neighbor (RKNN) queries in road n etworks have been studied extensively in recent years. However, at present, there is still a lack of algor ithms for moving queries in a road network. In this paper, we study how to efficiently process moving queries. Existing algori thms do not efficiently handle query movement. For instance, whenever a query changes its location, the result of the query has to be recomputed. To avoid this recomputation, we introduce a new technique that can efficiently compute the safe exi t points for continuous RKNNs. Within these safe ex it points, the query result remains unchanged and a request for recomputation o f the query does not have to be made to the server. This significantly reduces server processing costs and the communicati on costs between the server and moving clients. The results of extensive experiments conducted using real road network data indicate that our proposed algorithm significantly reduces communication and computation costs.

References

[1] Benetis R., Jensen C., Karciauskas G., and SaltenisS., Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects, in Proceedings of International Symposium on Database Engineering and Applications , pp. 44 53, 2002.

[2] Brinkhoff T., A Framework for Generating Network Based Moving Objects, GeoInformatica , vol. 6, no. 2, pp. 153 180, 2002.

[3] Cheema M., Brankovic L., Lin X., Zhang W., and Wang W., Continuous Monitoring of Distance Based Range Queries, IEEE Transaction on Knowledge and Data Engineering , vol. 23, no. 8, pp. 1182 1199, 2011.

[4] Cheema M., Lin X., Zhang W., and Zhang Y., Influence Zone: Efficiently Processing Reverse K Nearest Neighbors Queries, in Proceedings of the 27 th International Conference on Data Engineering , Hannover, Germany, pp. 577 588, 2011.

[5] Cheema M., Lin X., Zhang Y., Wang W., and Zhang W., Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN, the International Journal on Very Large Data Bases , vol. 2, no. 1, pp. 1138 1149, 2009.

[6] Cheema M., Lin X., Zhang Y., Zhang W., and Li X., Continuous Reverse K Nearest Neighbors Queries in Euclidean Space and in Spatial Networks, the International Journal on Very Large Data Bases , vol. 21, no. 1, pp. 69 95, 2012.

[7] Cho H. and Chung C., An Efficient and Scalable Approach to CNN Queries in a Road Network, in Proceedings of the 31 st International Conference on Very Large Data Bases , Trondheim, Norway, pp. 865 876, 2005.

[8] Cho H., Continuous Range K Nearest Neighbor Queries in Vehicular Ad Hoc Networks, the Journal of Systems and Software , vol. 86, no. 5, pp. 1323 1332, 2013.

[9] Cho H., Choe S., and Chung T., A Distributed Approach to Continuous Monitoring of Constrained K Nearest Neighbor Queries in Road Networks, Mobile Information Systems , vol. 8, no. 2, pp. 107 126, 2012.

[10] Cho H., Kwon S., and Chung T., A Safe Exit Algorithm for Continuous Nearest Neighbor Monitoring in Road Networks, Mobile Information Systems , vol. 9, no. 1, pp. 37 53, 2013.

[11] Gao Y., Zheng B., Chen G., Lee W., Lee K., and Li Q., Visible Reverse K Nearest Neighbor Queries, in Proceedings of the 25 th International Conference on Data Engineering , Shanghai, China, pp. 1203 1206, 2009.

[12] Kang J., Mokbel M., Shekhar S., Xia T., and Zhang D., Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest Neighbors, in Proceedings of the 23 rd International Conference on Data Engineering , Istanbul, Turkey, pp. 806 815, 2007.

[13] Kolahdouzan M. and Shahabi C., Voronoi Based K Nearest Neighbor Search for Spatial Network Databases, in Proceedings of the 30 st International Conference on Very Large Data Bases , Ontario, Canada, pp. 840 851, 2004.

[14] Korn F. and Muthukrishnan S., Influence Sets based on Reverse Nearest Neighbor Queries, ACM SIGMOD Record , vol. 29, vo. 2, pp. 201 212, 2000.

[15] Li G., Li Y., Li J., Shu L., and Yang F., Continuous Reverse K Nearest Neighbor Monitoring on Moving Objects in Road Networks, Information Systems , vol. 35, no. 8, pp. 860 883, 2010. Na ve CMRNN 548 The International Arab Journal of Information Tech nology, Vol. 12, No. 6, November 2015

[16] Li P., Fan Y., and Du J., An Efficient Technique for Continuous K Nearest Neighbor Query Processing on Moving Objects in a Road Network, in Proceedings of the 10 th International Conference on Computer and Information Technology , Bradford, UK, pp. 627 634, 2010.

[17] Real Datasets for Spatial Databases, available at: http://www.cs.fsu.edu/~lifeifei/SpatialDataset. htm, last visited 2013.

[18] Rizvi S. and Chung T., JAM: Justifiable Allocation of Memory with Efficient Mounting and Fast Crash Recovery for NAND Flash Memory File Systems, the International Arab Journal of Information Technolgy , vol. 7, no. 4, pp. 395 402, 2010.

[19] Safar M., Ebrahimi D., and Taniar D., Voronoi Based Reverse Nearest Neighbor Query Processing on Spatial Networks, Multimedia Systems , vol. 15, no. 5, pp. 295 308, 2009.

[20] Song Z. and Roussopoulos N., K Nearest Neighbor Search for Moving Query Point, in Proceedings of the 7 th International Symposium Advances in Spatial and Temporal Databases , California, USA, pp. 79 96, 2001.

[21] Stanoi I., Agrawal S., and Abbadi A., Reverse Nearest Neighbor Queries for Dynamic Databases, available at: http://infolab.usc.edu/ csci599/Fall2007/papers/b 2.pdf, last visited 2013.

[22] Sun H., Jiang C., Liu J., and Sun L., Continuous Reverse Nearest Neighbor Queries on Moving Objects in Road Networks, in Proceedings of the 9 th International Conference on Web#Age Information Management , Hunan, China, pp. 238 245, 2008.

[23] Tao Y., Papadias D., and Lian X., Reverse Knn Search in Arbitrary Dimensionality, in Proceedings of the 30 th International Conference on Very Large Data Bases , Ontario, Canada, pp. 744 755, 2004.

[24] Wang H. and Zimmermann R., Snapshot Location Based Query Processing on Moving Objects in Road Networks, in Proceedings of the 16 th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems , California, USA, 2008.

[25] Wu W., Yang F., Chan C., and Tan K., Continuous Reverse K Nearest Neighbor Monitoring, in Proceedings of the 9 th International Conference on Mobile Data Management , Beijing, China, pp. 132 139, 2008.

[26] Xia T. and Zhang D., Continuous Reverse Nearest Neighbor Monitoring, in Proceedings of the 22 nd International Conference on Data Engineering , Georgia, USA, 2006.

[27] Xuan K., Zhao G., Taniar D., and Srinivasan B., Continuous Range Search Query Processing in Mobile Navigation, in Proceedings of the 14 th International Conference on Parallel and Distributed Systems , Victoria, Australia, pp. 361 368, 2008.

[28] Yiu M., Mamoulis N., Papadias D., and Tao Y., Reverse Nearest Neighbor in Large Graphs, IEEE Transactions on Knowledge and Data Engineering , vol. 18, no. 4, pp. 540 553, 2006.

[29] Yung D., Yiu M., and Lo E., A Safe Exit Approach for Efficient Network Based Moving Range Queries, Data Knowledge Engineering , vol. 72, pp. 126 147, 2012.

[30] Zhang J., Zhu M., Papadias D., Tao Y., and Lee D., Location Based Spatial Queries, available at: http://infolab.usc.edu/csci599/Fall2007/papers /c 4.pdf, last visited 2013. Muhammad Attique received the BCs degree in information and communication systems engineering from National University of Science and Technology, Pakistan, in 2008. He is currently doing MS degree in computer engineering from Ajou University, South Korea. His research interests inc lude location based services, spatial queries in road network, moving objects and moving query processing in mobile networks. Yared Hailu received the BCs degree in electrical engineering from Arba Minch University, Ethiopia in 2008; received Ms degree in computer engineering from Ajou University, South Korea 2013. His current research interest includes flash memory storages, embedded system, energy efficient computing and location based services. Sololia GudetaAyele received BCs degree in electrical engineering from Haramaya University, Dire Dawa, Ethiopia in 2011. She is currently perusing MSC degree in Computer engineering in Ajou University, South Korea. Her research interest includes flash memory performance enhancement, location based services, spatial queries in road network, moving objects and moving query processing in mobile networks. A Safe Exit Approach for Continuous Monitoring of Reverse K#Nearest 549 Hyung-Ju Cho received his BCs and MS degrees in computer engineering from Seoul National University in 1997 and 1999, respectively and his PhD degree in computer science from KAIST in 2005. He is currently a research assistant professor at the department of informatio n and computer engineering, Ajou University, South Korea. His current research interests include movin g object databases and query processing in mobile pee r to peer networks. Tae-Sun Chung received the BCs degree in computer science from KAIST, in 1995 and the MS and PhD degree in computer science from Seoul National University, in 1997 and 2002, respectively. He is currently an associate professor at school of information and computer engineering at Ajou University. His current research interests inc lude flash memory storages, XML databases and database systems.