Computer Science ›› 2020, Vol. 47 ›› Issue (1): 79-86.doi: 10.11896/jsjkx.181102231

Special Issue: Database Technology

• Database & Big Data & Data Science • Previous Articles     Next Articles

K Nearest Neighbors Queries of Moving Objects in Time-dependent Road Networks

ZHANG Tong,QIN Xiao-lin   

  1. (College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)
  • Received:2018-11-30 Published:2020-01-19
  • About author:ZHANG Tong,born in 1996,postgra-duate,is student member of China Computer Federation (CCF).Her main research interests include spatial database query technology;QIN Xiao-lin,born in 1953,Ph.D,professor,Ph.D supervisor,is member of China Computer Federation (CCF).His main reasearch interests include spatial and spatio-temporal databases,data management and security in distributed environment,etc.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61373015,61728204).

Abstract: With the wide application of location-based services,object-based query on time-dependent road network has gradually become a research hotspot.In the past,most of the researches only focused on static objects on time-dependent road networks (such as gas stations,restaurants,etc.),and did not take into account the situation of mobile objects (such as taxis).The query of mobile objects has a very wide range of applications in daily life.Therefore,the K nearest neighbor query algorithm TD-MOKNN of moving object is proposed for time-dependent road network.The algorithm is divided into pre-processing stage and query stage.In the pre-processing stage,the road network and grid index are established,and a new mapping method of moving objects to the road network is proposed,which removes the limitation of previous researches that moving objects happen to be on the intersection of the road networks.In the query stage,a new efficient heuristic value is calculated by using inverted grid index,and an efficient k-nearest neighbor query algorithm is designed by using pre-processing information and heuristic value.Experiments verify the effectiveness of the algorithm.Compared with existing algorithm,TD_MOKNN algorithm reduces the number of traversing vertices and response time by 55.91% and 54.57% respectively,and improves the query efficiency by 55.2% on average.

Key words: A* algorithm, Grid index, K nearest neighbors query, Moving object, Time-dependent road network

CLC Number: 

  • TP311
[1]YANG H M,WANG H Z,WU Y B.Observation and Characteri- stics Analysis of Traffic Flow in Nanjing [J].Environmental Science and Technology,2011,24(a02):98-101.
[2]CHO H J,CHUNG C W.An Efficient and Scalable Approach to CNN Queries in a Road Network [C]∥International Conference on Very Large Data Bases.Trondheim,Norway:DBLP,2005:865-876.
[3]PAPADIAS D,ZHANG J,MAMOULISM N,et al.Query Processing in Spatial Network Databases [J].Proc Vldb,2003,29:802-813.
[4]GOLDBERG A V,HARRELSON C.Computing the Shortest Path:A* Search Meets Graph Theory:Technical Report MSR-TR-2004-24[R].Philadelphia,PA,USA:Society for Industrial and Applied Mathematics,2005:156-165.
[5]GEISBERGER R,VETTER C.Efficient Routing in Road Networks with Turn Costs [C]∥International Conference on Experimental Algorithms.Berlin:Springer-Verlag,2011:100-111.
[6]ABEYWICKRAMA T,CHEEMA M A.Efficient Landmark- Based Candidate Generation for kNN Queries on Road Networks[C]∥Proceedings of the 22nd International Conference on Database Systems for Advanced Applications.Berlin:Springer,2017:425-440.
[7]XUAN K,ZHAO G,TANIAR D,et al.Constrained Range Search Query Processing on Road Networks [J].Concurrency and Computation:Practice and Experience,2011,23(5):491-504.
[8]DIJKSTRA E W.A Note on Two Problems in Connection with Graphs [J].Numerische Mathematics,1959,1(1):269-271.
[9]ERWING M.The Graph Voronoi Diagram with Applications
[10]KOLAHDOUZAN M,SHAHABI C.The Graph Voronoi Dia- gram with Applications [C]∥Proceedings of the Thirtieth International Conference on Very Large Data Bases.San Francisco,CA:Morgan Kaufmann,2004:840-851.
[11]HUANG X,JENSEN C S,ŠALTENIS S.The Islands Approach to Nearest Neighbor Querying in Spatial Networks [C]∥Proceedings of the 2005 International Symposium on Spatial and Temporal Databases(SSTD 2005).Berlin:Springer,2005:73-90.
[12]COOKE K L,HALSEY E.The Shortest Route Through a Network with Time-Dependent Internodal Transit Times [J].Journal of Mathematical Analysis & Applications,1966,14(3):493-498.
[13]GEORGE B,KIM S,SHEKHAR S.Spatio-temporal Network Databases and Routing Algorithms:a Summary of Results [C]∥International Conference on Advances in Spatial and Temporal Databases.Berlin:Springer-Verlag,2007:460-477.
[14]DEMIRYUREK U,BANAEIKASHANI F,SHAHABI C.To- wards K-Nearest Neighbor Search in Time-Dependent Spatial Network Databases [C]∥International Conference on Databa-ses in Networked Information Systems.Berlin:Springer-Verlag,2010:296-310.
[15]CRUZ L A,NASCIMENTO M A,MACÊDO J A F.K-nearest Neighbors Queries in Time-Dependent Road Networks [J].Journal of Information & Data Management,2012,3(3):211-216.
[16]KOMAI Y,NGUYEN D H,HARA T,et al.kNN Search Utilizing Index of the Minimum Road Travel Time in Time-Depen-dent Road Networks [J].Information Sciences,2014,255(1):135-154.
[17]CHUCRE M,NASCIMENTO S,MACEDO J A,et al.Taxi,Please! A Nearest Neighbor Query in Time-Dependent Road Networks [C]∥IEEE International Conference on Mobile Data Management.Piscataway,NJ:IEEE,2016:180-185.
[18]NIEVERGELT J,HINTERBERGER H,SEVCIKK C.The Grid File:An Adaptable,Symmetric Multi-Key File Structure [J].ACM TODS,1981,9(1):38-71.
[19]MENG N N,ZHOU X D.Realization on Spatial Index with Grids of Fixed Size [J].Beijing Surveying and Mapping,2003(1):7-11.
[20]ORDA A,ROM R.Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length [J].Journal of the Acm,1990,37(3):607-625.
[1] XIN Yuan-xue, SHI Peng-fei, XUE Rui-yang. Moving Object Detection Based on Region Extraction and Improved LBP Features [J]. Computer Science, 2021, 48(7): 233-237.
[2] LI Bing-rong, PI De-chang, HOU Meng-ru. Destination Prediction of Moving Objects Based on Convolutional Neural Networks and Long-Short Term Memory [J]. Computer Science, 2021, 48(4): 70-77.
[3] CAO Bo, CHEN Feng, CHENG Jing, LI Hua, LI Yong-le. Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search [J]. Computer Science, 2021, 48(11A): 77-80.
[4] CHEN Ji-qing, TAN Cheng-zhi, MO Rong-xian, WANG Zhi-kui, WU Jia-hua, ZHAO Chao-yang. Path Planning of Mobile Robot with A* Algorithm Based on Artificial Potential Field [J]. Computer Science, 2021, 48(11): 327-333.
[5] HAN Jing-yu, XU Meng-jie, ZHU Man. Detecting Group-and-individual Movements of Moving Objects Based on Spatial-Temporal Anchors of Road-network [J]. Computer Science, 2020, 47(11): 294-303.
[6] ZHU Xuan, WANG Lei, ZHANG Chao, MEI Dong-feng, XUE Jia-ping, CAO Qing-wen. Moving Object Detection Based on Continuous Constraint Background Model Deduction [J]. Computer Science, 2019, 46(6): 311-315.
[7] ZHANG Huai-feng, PI De-chang, DONG Yu-lan. iBTC:A Trajectory Clustering Algorithm Based on Isolation Forest [J]. Computer Science, 2019, 46(1): 251-259.
[8] WANG Bo-tao,LIANG Wei,ZHAO Kai-li,ZHONG Han-hui,ZHANG Yu-qi. R-tree for Frequent Updates and Multi-user Concurrent Accesses Based on HBase [J]. Computer Science, 2018, 45(7): 42-52.
[9] GONG Hai-yan,GENG Sheng-ling. Prediction of Uncertain Trajectory Based on Moving Object Motion in Complex Obstacle Space [J]. Computer Science, 2018, 45(6A): 130-134.
[10] GONG Fa-ming,LI Xiao-ran. Research on Ontology Data Storage of Massive Oil Field Based on Neo4j [J]. Computer Science, 2018, 45(6A): 549-554.
[11] DONG Tian-yang, SHANG Yue-hui, CHENG Qiang. Direction-aware Moving Object Range Query Algorithm in Road Network [J]. Computer Science, 2018, 45(11): 210-219.
[12] LIU Kai-yang. AP-I:An Index to Quickly Answer Predictive Queries for Moving Objects [J]. Computer Science, 2017, 44(Z6): 314-318.
[13] ZHANG Wen-ya, XU Hua-zhong and LUO Jie. Moving Objects Detection under Complex Background Based on ViBe [J]. Computer Science, 2017, 44(9): 304-307.
[14] XUE Zhong-bin, BAI Li-guang, HE Ning, ZHOU Xuan, ZHOU Xin and WANG Shan. Throughput Oriented Real-time Query Processing Algorithm for Moving Objects in Road Network [J]. Computer Science, 2017, 44(3): 16-19.
[15] YANG Biao, NI Rong-rong and JANG Da-Peng. Robust Moving Object Foreground Extraction Approach to Illumination Change [J]. Computer Science, 2016, 43(Z11): 186-189.
Full text



No Suggested Reading articles found!