Computer Science ›› 2018, Vol. 45 ›› Issue (11): 210-219.doi: 10.11896/j.issn.1002-137X.2018.11.033

• Software & Database Technology • Previous Articles     Next Articles

Direction-aware Moving Object Range Query Algorithm in Road Network

DONG Tian-yang, SHANG Yue-hui, CHENG Qiang   

  1. (School of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)
  • Received:2017-11-22 Published:2019-02-25

Abstract: The range query on moving objects in road network is one of the classical query methods in spatial query processing,which has been widely used in many fields.However,there are still some shortcomings in the existing moving object range query methods in road networks.On the one hand,most of them only consider the network distance,but pay less attention to the movement direction of moving objects in road networks.On the other hand,a few query me-thods considering the movement direction are based on Euclidean space and can’t not be applied to large-scale road network to determine whether moving objects move toward query point.Aiming at the problem of accurately and efficiently finding moving objects toward the query point in large and complex road network,this paper proposed a direction-aware moving object range query algorithm in road network.In this method,R-tree and simple grid are taking as underlying index support,and an efficient determination method of moving object toward query point in road network is exploited,so as to efficiently query the moving object toward query point.At last,this paper designed experiments in terms of the query range,the number of moving object and the number of grid partition to evaluate the performance of the proposed algorithm.The experimental results show that the algorithm can achieve good query performance even in the case of large-scale complex road network under the condition that the index configuration is reasonable.

Key words: Direction-aware, Moving object, Range query, Road network

CLC Number: 

  • TP392
[1]GUTTMAN A.R-trees:a dynamic index structure for spatial searching[C]∥International Conference on Management of Data.1984:47-57.
[2]SELLIS T,ROUSSOPOULOS N,FALOUTSOS C,et al.The R+-Tree:A Dynamic Index for Multi-Dimensional Objects[C]∥International Conference on Very Large Data Bases.1987:507-518.
[3]BECKMANN N,KRIEGEL H,SCHNEIDER R,et al.The R*-tree:an efficient and robust access method for points and rectangles[J].ACM Sigimod Record,1990,19(2):322-331.
[4]KAMEL I,FALOUTSOS C.Hilbert R-tree:An Improved R-tree using Fractals[C]∥International Conference onVery Large Data Bases.1994:500-509.
[5]ARGE L,DE BERG M,HAVERKORT H J,et al.The Priority R-Tree:A Practically Efficient and Worst-Case-Optimal R-Tree[C]∥Proceedings of SIGMOD International Conference on Management of Data.2004:347-358.
[6]KORN F,SIDIROPOULOS N,FALOUTSOS C,et al.Fast Nearest Neighbor Search in Medical Image Databases[C]∥International Conference on Very Large Data Bases.1996:215-226.
[7]BERCHTOLD S,ERTL B,KEIM D A,et al.Fast nearest neighbor search in high-dimensional space[C]∥InternationalConfe-rence on Data Engineering.1998:209-218.
[8]ZHENG B,LEE D L.Semantic Caching in Location-Dependent Query Processing[C]∥Symposium on Large Spatial Databases.2001:97-113.
[9]SHARIFZADEH M,SHAHABI C.VoR-Tree:R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries[C]∥Proceedings of the Vldb Endowment.2010:1231-1242.
[10]JENSEN C S,LIN D,OOI B C.Query and update efficient B+-tree based indexing of moving objects[C]∥Proceedings of the Thirtieth International Conference on Very Large Data.2004:768-779.
[11]PAPADIAS D,ZHANG J,MAMOULIS N,et al.Query Pro- cessing in Spatial Network Databases[J].Vldb,2003,29:802--813.
[12]KOLAHDOUZAN M,SHAHABI C.Voronoi-based k nearest neighbor search for spatial network databases[C]∥Proceedings of the ThirtiethInternational Conference on Very Large Data Bases.2004:840-851.
[13]HUANG X,JENSEN C S,šALTENIS S.The Islands Approach to Nearest Neighbor Querying in Spatial Networks[C]∥International Conference on Lecture Notes in Computer Science.2006,3633:73-90.
[14]HUANG X,JENSEN C S,LU H,et al.S-GRID:A versatile approach to efficient query processing in spatial networks[M]∥Advances in Spatial and Temporal Databases.Springer Berlin Heidelberg,2007:93-111.
[15]HONG S,CHANG J.A new k-NN query processing algorithm based on multicasting-based cell expansion in location-based services[J].Journal of Convergence,2013,4(4):1-6.
[16]WANG H,ZIMMERMANN R.Location-based query processing on moving objects in road networks[C]∥Proceedings ofInternational Conference on Very Large Data Bases (VLDB 2007).2007:321-332.
[17]PATROUMPAS K,SELLIS T.Monitoring Orientation of Mo- ving Objects around Focal Points[C]∥Symposium on Large Spatial Databases.2009:228-246.
[18]LI G,FENG J,XU J.Desks:Direction-aware spatial keyword search[C]∥IEEE 28th International Conference on Data Engineering (ICDE).2012:474-485.
[19]YI S,RYU H,SON J,et al.View field nearest neighbor:A novel type of spatial queries[J].Information Sciences,2014,275(3):68-82.
[20]LEE M J,CHOI D W,KIM S Y,et al.The direction-constrained k nearest neighbor query[J].GeoInformatica,2016,20(3):471-502.
[21]LU B L,CUI X Y,LIU N.Bichromatic Reverse Nearest k Neighbor Query Processing on Road Network[J].Journal of Chinese Mini-Micro Computer Systems,2015,36(2):266-270.(in Chinese)
卢秉亮,崔晓玉,刘娜.路网中双色反向k近邻查询处理[J].小型微型计算机系统,2015,36(2):266-270.
[22]LEE K W,CHOI D W,CHUNG C W.Dart:An efficient method for direction-aware bichromatic reverse k nearest neighbor queries[M]∥Advances in Spatial and Temporal Databases.Sprin-ger Berlin Heidelberg,2013:295-311.
[23]LI G L,FENG J H,XU J.DESKS:Direction-aware spatial keyword search[C]∥2012 IEEE 28th International Conference on Data Engineering.Washington:IEEE,2012:474-485.
[24]BRINKHOFF T.A framework for generating network-based moving objects[J].GeoInformatica,2002,6(2):153-180.
[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] ZHU Run-ze, QIN Xiao-lin, LIU Jia-chen. Study on Why-not Problem in Skyline Query of Road Network Based on Query Object [J]. Computer Science, 2021, 48(6): 57-62.
[3] 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.
[4] LIU Ze-bang, CHEN Luo, YANG An-ran, LI Si-jie. Space Retrieval Method to Retrieve Straight Line for Vector Line Data [J]. Computer Science, 2021, 48(11A): 117-123.
[5] XIONG Ting, QI Yong, ZHANG Wei-bin. Short-term Traffic Flow Prediction Based on DCGRU-RF Model for Road Network [J]. Computer Science, 2020, 47(5): 84-89.
[6] 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.
[7] RUAN Zi-rui,RUAN Zhong-yuan,SHEN Guo-jiang. Study of TASEP Model Based on Road Networks [J]. Computer Science, 2020, 47(1): 265-269.
[8] ZHANG Tong,QIN Xiao-lin. K Nearest Neighbors Queries of Moving Objects in Time-dependent Road Networks [J]. Computer Science, 2020, 47(1): 79-86.
[9] ZHOU Jian-gang, QIN Xiao-lin, ZHANG Ke-heng, XU Jian-qiu. Dynamic Skyline Query for Multiple Mobile Users Based on Road Network [J]. Computer Science, 2019, 46(9): 73-78.
[10] XU Zhe, LIU Liang, QIN Xiao-lin, QIN Wei-meng. Distributed Spatial Keyword Query Processing Algorithm with Relational Attributes [J]. Computer Science, 2019, 46(6A): 402-406.
[11] 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.
[12] LI Jia-jia, SHEN Pan-pan, XIA Xiu-feng, LIU Xiang-yu. Reverse k Nearest Neighbor Queries in Time-dependent Road Networks [J]. Computer Science, 2019, 46(1): 232-237.
[13] 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.
[14] 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.
[15] 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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!