Route Searching using Modified k-Nearest Neighbor with Hill Climbing over Trajectories

Vineet Kumar Gupta, Sriram Yadav


Optimal planning for public transportation is one of the keys to sustainable development and better quality of life in urban areas. Based on mobility patterns, propose a localized transportation mode choice model, with which we can dynamically predict the bus travel demand for different bus routing. This model is then used for bus routing optimization which aims to convert as many people from private transportation to public transportation as possible given budget constraints on the bus route modification. It also leverages the model to identify region pairs with flawed bus routes, which are effectively optimized using our approach. To validate the effectiveness of the proposed methods, extensive studies are performed on real world data collected in Beijing which contains 19 million taxi trips and 10 million bus trips. GPS enables mobile devices to continuously provide new opportunities to improve our daily lives. For example, the data collected in applications created by Ola, Uber or Public Transport Authorities can be used to plan transportation routes, estimate capacities, and proactively identify low coverage areas. Now, study a new kind of query – Modified k-Nearest Neighbor Search with Hill Climbing (MkNNHC), which can be used for route planning and capacity estimation. Given a set of existing routes DR, a set of passenger transitions DT, and a query route Q, an MkNNHC query returns all transitions that take Q as one of its k nearest travel routes. To solve the problem, we first develop an index to handle dynamic trajectory updates, so that the most up-to-date transition data are available for answering an RkNNT query. Then introduce a filter refinement framework for processing MkNNHC queries using the proposed indexes. Experiments on real datasets demonstrate the efficiency and scalability of our approaches.

Full Text:



Sheng Wang, Zhifeng Bao, J. Shane Culpepper, Timos Sellis, Gao Cong, “ Reverse k Nearest Neighbor Search over Trajectories”, IEEE Transaction on Data Engineering, 2017.

Yanchi Liu, Chuanren Liu, Nicholas Jing Yuan, Lian Duan, Yanjie Fu, Hui Xiong, Songhua Xu and Junjie Wu, “Exploiting Heterogeneous Human Mobility Patterns for Intelligent Bus Routing”, IJAPTA 2015.

Tahira Mahboob, Fatima Akhtar, Moquaddus Asif, Nitasha Siddique, Bushra Sikandar, “Survey and Analysis of Searching Algorithms”, IJCSI International Journal of Computer Science Issues, Volume 12, Issue 3, May 2015.

Shiyu Yang, Muhammad Aamir Cheema, Xuemin Lin, Wei Wang, “Reverse k Nearest Neighbors Query Processing: Experiments and Analysis”, VLDB Endowment, Vol. 8, No. 5, 2015.

Yunjun Gao, Baihua Zheng, Gencai Chen, Wang-Chien Lee, Ken C. K. Lee, Qing Li, “Visible Reverse k-Nearest Neighbor Queries”, ACM Journal of Engineering, 2014.

Elio Masciari, Gao Shi, Carlo Zaniolo, “Sequential Pattern Mining from Trajectory Data”, ACM IDEAS ’13, October 09 – 11, 2013.

Kan Jun-man, Zhang Yi, “Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman Problem”, International Conference on Future Electrical Power and Energy Systems, 2012.

Ugur Demiryurek, Farnoush Banaei-Kashani, Cyrus Shahabi, “Efficient Continuous Nearest Neighbor Query in Spatial Networks using Euclidean Restriction”, National Science Foundation, 2011.

Dongming Zhao, Liang Luo, Kai Zhang, “An improved ant colony optimization for the communication network routing problem”, Elsivier Journal of Mathematical and Computer Modeling, 2010.

Hans-Peter Kriegel, Peer Kroger, Matthias Renz, Andreas Zufle, Alexander Katzdobler, “Reverse k-Nearest Neighbor Search based on Aggregate Point Access Methods”, Int. Conf. on Scientific and Statistical Database Management, 2009.

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

Reza Sherkat, Davood Rafiei, “On Efficiently Searching Trajectories and Archival Data for Historical Similarities”, VLDB Endowment, ACM, 2008.

Wei Wu, Fei Yang, CheeYong Chan, KianLee Tan, “FINCH: Evaluating Reverse kNearestNeighbor Queries on Location Data”, VLDB Endowment, ACM, 2008.

Elias Frentzos, Kostas Gratsias, Nikos Pelekis, Yannis Theodoridis, “Algorithms for Nearest Neighbor Search on Moving Object Trajectories*”, IEEE Tran. on Data Engineering, 2008.



  • There are currently no refbacks.

© International Journals of Advanced Research in Computer Science and Software Engineering (IJARCSSE)| All Rights Reserved | Powered by Advance Academic Publisher.