Computer Science ›› 2017, Vol. 44 ›› Issue (3): 16-19, 41.doi: 10.11896/j.issn.1002-137X.2017.03.004

Previous Articles     Next Articles

Throughput Oriented Real-time Query Processing Algorithm for Moving Objects in Road Network

XUE Zhong-bin, BAI Li-guang, HE Ning, ZHOU Xuan, ZHOU Xin and WANG Shan   

  • Online:2018-11-13 Published:2018-11-13

Abstract: With the rapid development of wireless communication technology,space positioning technology and mobile computing technology,location based queries have become an important research issue in the area of database.In this paper,we studied the problem of moving object KNN query in road network.A series of algorithms have been proposed to process KNN queries of moving objects.However,these algorithms are either designed for fast response time or high update performance.With the increasing of moving objects,when both queries and updates arrive at a very high rate,the throughput becomes more important.For the query stream and object update stream,we proposed a high throughput main memory algorithm——dual stream road network KNN (DSRNKNN) algorithm,which is used for moving object KNN query in road network.DSRNKNN uses a snapshot approach.In each snapshot,DSRNKNN builds a new index structure based on the update of the moving objects,which avoids complex index maintenance operations and gives full play to the performance of the hardware.DSRNKNN executes a batch queries at each run,making full use of inner-and inter-parallel,which increases the data locality and improves the efficiency of the algorithm.We conducted a comprehensive performance study of the proposed techniques by using the real network generated data.The results show that DSRNKNN is highly efficient.

Key words: Spatial temporal database,Moving object,KNN query,Main memory

[1] CHO H J,CHUNG C W.An efficient and scalable approach to CNN queries in a road network[C]∥Proceedings of the 31st International Conference on Very Large Data Bases.VLDB Endowment,2005:865-876.
[2] MOURATIDIS K,YIU M L,PAPADIAS D,et al.Continuousnearest neighbor monitoring in road networks[C]∥Proceedings of the 32nd International Conference on Very large Data Bases.VLDB Endowment,2006:43-54.
[3] LEE K C K,LEE W C,ZHENG B,et al.ROAD:a new spatial object search framework for road networks[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(3):547-560.
[4] CHEN Y J,CHUANG K T,CHEN M S.Coupling or decoupling for KNN search on road networks?:a hybrid framework on user query patterns[C]∥Proceedings of the 20th ACM International Conference on Information and Knowledge Management.ACM,2011:795-804.
[5] CHEN Y J,CHUANG K T,CHEN M S.Spatial-temporal query homogeneity for KNN object search on road networks[C]∥ Proceedings of the 22nd ACM International Conference on Conference on Information & Knowledge Management.ACM,2013:1019-1028.
[6] BALKESEN C,TEUBNER J,ALONSO G,et al.Main-Memory Hash Joins on Modern Processor Architectures[J].IEEE Transactions on Knowledge & Data Engineering,2015,27(7):1754-1766.
[7] TEUBNER J,ALONSO G,BALKESEN C,et al.Main-memory hash joins on multi-core CPUs:Tuning to the underlying hardware[C]∥ 2013 IEEE 29th International Conference on Data Engineering (ICDE).IEEE,2013:362-373.
[8] KIM C,KALDEWEY T,LEE V W,et al.Sort vs.Hash revisited:fast join implementation on modern multi-core CPUs[J].Proceedings of the Vldb Endowment,2009,2(2):1378-1389.
[9] SIDLAUSKAS D,SALTENIS S,JENSEN C S.Processing ofextreme moving-object update and query workloads in main memory[J].The Vldb Journal,2014,23(5):817-841.
[10] LI F,CHENG D,HADJIELEFTHERIOU M,et al.On tripplanning queries in spatial databases[M]∥Advances in Spatial and Temporal Databases.Springer Berlin Heidelberg,2005:273-290.
[11] LI F.Real Datasets for Spatial Databases:Road Networks and Points of Interest. lifeifei/SpatialDataset.htm.2004
[12] LEE K C K,LEE W C,ZHENG B.Fast object search on road networks[C]∥Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology.ACM,2009:1018-1029.
[13] DITTRICH J,BLUNSCHI L,SALLES M A V.Indexing mo-ving objects using short-lived throwaway indexes[M]∥Advances in Spatial and Temporal Databases.Springer Berlin Heidelberg,2009:189-207.
[14] BRINKHOFF T.A framework for generating network-basedmoving objects[J].GeoInformatica,2002,6(2):153-180

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .