Review on Moving Objects Query Techniques in Road Network Environment
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61370091, 61602151); National Key Technology Research and Development Program of the Ministry of Science and Technology of China (2015BAB07B01); Key Research and Development Plan of Jiangsu Province, China (BE2015707)

  • Article
  • | |
  • Metrics
  • |
  • Reference [89]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    Currently, LBS (location-based service) is widely employed in many mobile devices, making the technology for processing moving object data underlying the road network to become a research hotspot in the community of spatio-temporal processing techniques. This paper intends to survey the previous work from three aspects including index structures, query approaches and privacy protection. First, the various index structures are classified into three groups:hierarchical, distributed and broadcast, and comparisons are made based on in-depth analysis. Second, the query approaches are divided into four categories by their purposes:single-object continuous query, multi-object parallel query, shortest path query and road-network keyword query. For each category, its basic strategies are introduced. In addition, methods on moving object privacy protection are also studied. The challenges on these technologies are projected in the end.

    Reference
    [1] Qiao SJ, Han N, Wang C, Zhu F, Tang CJ. A two-tiered dynamicindex structure of moving objects based on constrained networks. Chinese Journal of Computers, 2014,(9):1947-1958(in Chinese with English abstract).
    [2] Feng J, Zhu YL, Mukai N, Watanabe T. Search on transportation networks for location-based service. Applied Intelligence, 2007, 26(1):69-79.[doi:10.1007/s10489-006-0004-4]
    [3] Frentzos E. Indexing objects moving on fixed networks. In:Proc. of the Int'l Symp. 2003. 289-305.[doi:10.1007/978-3-540- 45072-6_17]
    [4] Güting RH, Almeida VTD, Ding Z. Modeling and querying moving objects in networks. VLDB Journal, 2006,15(2):165-190.[doi:10.1007/s00778-005-0152-x]
    [5] Almeida VTD. Indexing the trajectories of moving objects in networks*. In:Proc. of the IEEE Scientific and Statistical Database Management Int'l Conf. 2004. 115-115.[doi:10.1109/SSDM.2004.1311200]
    [6] Gong Z, Lakshminarasimhan S, Jenkins J, Kolla H, Ethier S, Chen J, Ross R, Klasky S, Samatova NF. Multi-Level layout optimization for efficient spatio-temporal queries on ISABELA-compressed data. In:Proc. of the IEEE Parallel & Distributed Processing Symp. (IPDPS). 2012. 873-884.[doi:10.1109/IPDPS.2012.83]
    [7] Fox A, Eichelberger C, Hughes J, Lyon S. Spatio-Temporal indexing in non-relational distributed databases. In:Proc. of the IEEE Int'l Conf. on Big Data. 2013. 291-299.[doi:10.1109/BigData.2013.6691586]
    [8] Kilimci P, Kalipsiz O. Indexing of spatio-temporal data:A comparison between sweep and z-order space filling curves. In:Proc. of the Int'l Conf. on Information Society. London, 2011. 450-456.
    [9] Xu HB, Hao ZX. An approximate k-closest pair query algorithm based on Z curve. Journal of Computer Rearch and Development, 2008,45(2):310-317(in Chinese with English abstract).
    [10] Nishimura S, Das S, Agrawal D, Abbadi AE. MD-HBase:A scalable multi-dimensional data infrastructure for location aware services. In:Proc. of the IEEE Int'l Conf. on Mobile Data Management. 2011. 7-16.[doi:10.1109/MDM.2011.41]
    [11] Pfoser D, Jensen CS. Indexing of network constrained moving objects. In:Proc. of the 11th ACM Int'l Symp. on Advances in Geographic Information Systems. New Orleans, 2003. 25-32.[doi:10.1145/956676.956680]
    [12] Feng J, Watanabe T. MOR-Tree:An access structure for multi-levels of road networks on distributed environment. Trans. of the Institute of Systems Control & Information Engineers, 2003,16:655-661.[doi:10.5687/iscie.16.655]
    [13] Zhang JM, Wang PC, Lu FJ. Research on moving objects index in road network. Computer Engineering& Applications, 2009, 45(12):144-146(in Chinese with English abstract). 1622
    [14] Lee DW, Baek SH, Bae HY. aCN-RB-Tree:Update method for spatio-temporal aggregation of moving object trajectory in ubiquitous environment. In:Proc. of the IEEE Int'l Conf. on Computational Science and Its Applications. 2009. 177-182.[doi:10.1109/ICCSA.2009.30]
    [15] Ding ZM, Li XN, Yu B. Indexing the historical, current, and future locations of network-constrained moving objects. Ruan Jian Xue Bao/Journal of Software, 2009,20(12):3193-3204(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3400. htm[doi:10.3724/SP. J.1001.2009.03400]
    [16] Chang JW, Song MS, Um JH. TMN-Tree:New trajectory index structure for moving objects in spatial networks. In:Proc. of the IEEE Int'l Conf. on Computer and Information Technology. 2010. 1633-1638.[doi:10.1109/CIT.2010.289]
    [17] Qiao S, Han N, Zhu W, Gutierrez LA. TraPlan:An effective three-in-one trajectory-prediction model in transportation networks. IEEE Trans. on Intelligent Transportation Systems, 2015,16(3):1188-1198.[doi:10.1109/TITS.2014.2353302]
    [18] Chen J, Meng X. Update-Efficient indexing of moving objects in road networks. Geoinformatica, 2009,13(13):397-424.[doi:10.1007/s10707-008-0052-5]
    [19] Singh M, Zhu Q, Jagadish HV. SWST:A disk based index for sliding window spatio-temporal data. In:Proc. of the IEEE Int'l Conf. on Data Engineering. 2012. 342-353.[doi:10.1109/ICDE.2012.98]
    [20] Le J, Liu L, Guo Y, Ying M. Supported high-update method on road network. In:Proc. of the 4th Int'l Conf. on Wireless Communications, Networking and Mobile Computing. 2008. 1-4.[doi:10.1109/WiCom.2008.1198]
    [21] He K, Liu L. Efficiently indexing moving objects on road network. In:Proc. of the IEEE Computational Intelligence and Software Engineering. 2009. 1-4.[doi:10.1109/CISE.2009.5366045]
    [22] Liu L, Li W, Guo Y, Le J. Supporting high updates disk-based index in road network. In:Proc. of the IEEE Int'l Conf. on E-business Engineering. 2008. 517-522.[doi:10.1109/ICEBE.2008.39]
    [23] Dittrich J, Blunschi L, Salles MAV. MOVIES:Indexing moving objects by shooting index images. Geoinformatica, 2011,15(4):727-767.[doi:10.1007/s10707-011-0122-y]
    [24] Feng J, Lu J, Zhu Y, Watanabe T. Index method for tracking network-constrained moving objects. In:Proc. of the KnowledgeBased Intelligent Information and Engineering Systems. Berlin, Heidelberg:Springer-Verlag, 2008. 551-558.[doi:10.1007/978-3- 540-85565-1_68]
    [25] Ding ZM. An index structure for frequently updated network-constrained moving object trajectories. Chinese Journal of Computers, 2012,35(7):1448-1461(in Chinese with English abstract).[doi:10.3724/SP.J.1016.2012.01448]
    [26] Feng J, Lu C, Xu S. DynSketch:A spatio-temporal aggregate index for moving objects in road networks. Int'l Journal of Intelligent Defence Support Systems, 2009,2(2).[doi:10.1504/IJIDSS.2009.028646]
    [27] Feng J, Shi YQ, Tang ZX, Rui CH. Aggragation index technique of moving objexts in road networks. Journal of Jilin University (Engineering and Technology Edition), 2014,44(6):1799-1805(in Chinese with English abstract).
    [28] Wang H, Zimmermann R. Snapshot location-based query processing on moving objects in road networks. In:Proc. of the ACM Sigspatial Int'l Conf. on Advances in Geographic Information Systems. 2008. 1-4.[doi:10.1145/1463434.1463495]
    [29] Wang H, Zimmermann R. Processing of continuous location-based range queries on moving objects in road networks. IEEE Trans. on Knowledge & Data Engineering, 2011,23(7):1065-1078.[doi:10.1109/TKDE.2010.171]
    [30] Xu L, Zhang T. Reverse nearest neighbors query for moving objects in road network. In:Proc. of the IEEE Computational Intelligence and Software Engineering. 2009. 1-4.[doi:10.1109/CISE.2009.5364547]
    [31] Wang Q, Yu J, Zhang Q. A comprehensive index mechanism based on road network. In:Proc. of the IEEE Consumer Electronics, Communications and Networks (CECNet). 2012. 1505-1508.[doi:10.1109/CECNet.2012.6201951]
    [32] Komai Y, Nguyen DH, Hara T, Nishio S. kNN search utilizing index of the minimum road travel time in time-dependent road networks. In:Proc. of the IEEE Reliable Distributed Systems Workshops (SRDSW). 2014. 131-137.[doi:10.1109/SRDSW.2014. 17]
    [33] Ke S, Gong J, Li S,Zhu Q, Liu X, Zhang Y. A hybrid spatio-temporal data indexing method for trajectory databases. Sensors, 2014, 14(7):12990-13005.[doi:10.3390/s140712990]
    [34] Toplak W, Koller H, Dragaschnig M, Bauer D, Asamer J. Novel road classifications for large scale traffic networks. In:Proc. of the IEEE Intelligent Transportation Systems (ITSC). 2010. 1264-1270.[doi:10.1109/ITSC.2010.5625182]
    [35] Jeung H, Man LY, Zhou X, Jensen CS. Path prediction and predictive range querying in road network databases. Vldb Journal, 2010,19(4):585-602.[doi:10.1007/s00778-010-0181-y]
    [36] Guo LM, Ding ZM, Hu ZL, Chen C. Uncertain path prediction of moving objects on road netowrk. Journal of Computer Rearch and Development, 2010,47(1):104-112(in Chinese with English abstract).
    [37] Sasikala I, Ganesan M, John A. Uncertain data prediction on dynamic road network. In:Proc. of the IEEE Information Communication and Embedded Systems (ICICES). 2015.[doi:10.1109/ICICES.2014.7033972]
    [38] Xue AY, Qi J, Xie X, Zhang R, Li Y. Solving the data sparsity problem in destination prediction. Vldb Journal, 2014,24(2):1-25.[doi:10.1007/s00778-014-0369-7]
    [39] Heendaliya L, Wisely M, Lin D, Sarvestani SS, Hurson A. Influence-Aware predictive density queries under road-network constraints. In:Proc. of the Advances in Spatial and Temporal Databases. Springer Int'l Publishing, 2015. 80-97.[doi:10. 1007/978-3-319-22363-6_5]
    [40] Chen L, Tang Y, Lv M, Chen G. Partition-Based range query for uncertain trajectories in road networks. Geoinformatica, 2014, 19(1):61-84.[doi:10.1007/s10707-014-0206-6]
    [41] Moulitsas I, Karypis G. Architecture aware partitioning algorithms. In:Proc. of the 8th Int'l Conf. on Algorithms and Architectures for Parallel Processing. 2008. 42-53.[doi:10.1007/978-3-540-69501-1_6]
    [42] Hendawi AM, Bao J, Mokbel MF, Ali M. Predictive tree:An efficient index for predictive queries on road networks. In:Proc. of the IEEE Int'l Conf. on Data Engineering. 2015. 1215-1226.[doi:10.1109/ICDE.2015.7113369]
    [43] Qiao SJ, Li TR, Han N, Gao YJ, Yuan CA, Wang XT, Tang CJ. Self-Adaptive trajectory prediction model for moving objects in big data environment. Ruan Jian Xue Bao/Journal of Software, 2015,26(11):2869-2883(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/26/2869.htm[doi:10.13328/j.cnki.jos.004889]
    [44] Zhong Y, Fang J, Zhao X. VegaIndexer:A distributed composite index scheme for big spatio-temporal sensor data on cloud. In:Proc. of the IEEE Int'l Geoscience and Remote Sensing Symp. 2013. 1713-1716.[doi:10.1109/IGARSS.2013.6723126]
    [45] Zhang N, Zheng G, Chen H, Chen J, Chen X. HBaseSpatial:A scalable spatial data storage based on HBase. In:Proc. of the IEEE Int'l Conf. on Trust, Security and Privacy in Computing and Communications (TrustCom). 2014. 644-651.[doi:10.1109/TrustCom. 2014.83]
    [46] Wang L, Zheng Y, Xie X, Ma W. A flexible spatio-temporal indexing scheme for large-scale GPS track retrieval. In:Proc. of the IEEE Int'l Conf. on Mobile Data Management. 2008. 1-8.[doi:10.1109/MDM.2008.24]
    [47] Eldawy A, Mokbel MF. SpatialHadoop:A MapReduce framework for spatial data. In:Proc. of the IEEE Int'l Conf. on Data Engineering. 2015. 1352-1363.[doi:10.1109/ICDE.2015.7113382]
    [48] Feng J, Tang Z, Wei M, Xu L. HQ-Tree:A distributed spatial index based on hadoop. Wireless Communication over Zigbee for Automotive Inclination Measurement China Communications, 2014,11(7):128-141.[doi:10.1109/CC.2014.6895392]
    [49] Yu Z, Liu Y, Yu X, Pu KQ. Scalable distributed processing of K nearest neighbor queries over moving objects. IEEE Trans. on Knowledge & Data Engineering, 2015,27(5):1383-1396.[doi:10.1109/TKDE.2014.2364046]
    [50] Xu X, Feng J, Lu JM, Tang ZX, Zhang LX. HINMO:A hadoop-based index for network-constrained moving objects. Journal of Computer Research and Development, 2015(S1) (in Chinese with English abstract).
    [51] Dittrich J, Quian-Ruiz JA, Jindal A, Kargin Y, Setty V, Schad J. Hadoop++:Making a yellow elephant run like a cheetah (without it even noticing). Proc. of the Vldb Endowment, 2010,3(12):518-529.
    [52] Van Le H, Takasu A. A scalable spatio-temporal data storage for intelligent transportation systems based on HBase. IEEE Int'l Conf. on Intelligent Transportation Systems, 2015,18:2733-2738.[doi:10.1109/ITSC.2015.439]
    [53] Du N, Zhan J, Zhao M, Xiao D, Xie Y. Spatio-Temporal data index model of moving objects on fixed networks using HBase. In:Proc. of the IEEE Int'l Conf. on Computational Intelligence & Communication Technology. 2015. 247-251.[doi:10.1109/CICT. 2015.32]
    [54] Wang Y, Xu C, Gu Y, Chen M, Yu G. Spatial query processing in road networks for wireless data broadcast. Wireless Networks, 2013,19(4):477-494.[doi:10.1007/s11276-012-0479-3]
    [55] Li Y, Li J, Shu LC, Li Q, Li G, Yang F. Searching continuous nearest neighbors in road networks on the air. Information Systems, 2014,42(3):177-194.[doi:10.1016/j.is.2014.01.003]
    [56] Song D, Lee KH, Park K. Bitmap lattice index in road networks. Journal of Central South University, 2014,21(10):3856-3863.[doi:10.1007/s11771-014-2372-y]
    [57] Sun W, Chen C, Zheng B, Chen C, Liu P. An air index for spatial query processing in road networks. IEEE Trans. on Knowledge & Data Engineering, 2015,27(2):382-395.[doi:10.1109/TKDE.2014.2330836]
    [58] Liu J, Yue X. Peer-to-Peer cooperative caching for data dissemination in urban vehicular communications. IEEE Systems Journal, 2014,8(4):1136-1144.[doi:10.1109/JSYST.2013.2285611]
    [59] Guo W, Guo J, Hu ZY. Spatial Database Index Technology. Shanghai:Shanghai Jiao Tong University, 2006(in Chinese). 1624
    [60] Altenis S, Jensen CS, Leutenegger ST, Lopez MA. Indexing the Positions of Continuously Moving Objects. ACM Sigmod Int'l Conf. on Management of Data, 2000,29(2):331-342.[doi:10.1007/978-0-387-35973-1_618]
    [61] Ma YZ, Meng XF. Research on indexing for cloud data management. Ruan Jian Xue Bao/Journal of Software, 2015,26(1):145-166(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4688.htm[doi:10.13328/j.cnki.jos.004688]
    [62] Wongdeethai S, Siripongwutikorn P. Multipath query spreading over vehicular ad-hoc networks. In:Proc. of the Computer Science and Engineering Conf. 2013. 255-260.[doi:10.1109/ICSEC.2013.6694789]
    [63] Lee EY, Cho HJ, Chung TS, Ryu KY. Moving range k nearest neighbor queries with quality guarantee over uncertain moving objects. Information Sciences, 2015,325:324-341.[doi:10.1016/j.ins.2015.07.034]
    [64] Alamri S, Taniar D, Safar M. A taxonomy for moving object queries in spatial databases. Future Generation Computer Systems, 2014,37(7):232-242.[doi:10.1016/j.future.2014.02.007]
    [65] Cho HJ, Kwon SJ, Chung TS. A safe exit algorithm for continuous nearest neighbor monitoring in road networks. Mobile Information Systems, 2013,9(1):37-53.[doi:10.1155/2013/426294]
    [66] Zhao G, Xuan K, Rahayu W, Taniar D, Safar M, Gavrilova ML, Srinivasan B. Voronoi-Based continuous nearest neighbor search in mobile navigation. IEEE Trans. on Industrial Electronics, 2011,58(6):2247-2257.[doi:10.1109/TIE.2009.2026372]
    [67] Xuan K, Zhao G, Taniar D, Safar M, Srinivasan B. Constrained range search query processing on road networks. Concurrency & Computation Practice & Experience, 2011,23(5):491-504.[doi:10.1002/cpe.1651]
    [68] Jing Y, Hu L, Ku WS, Shahabi C. Authentication of k nearest neighbor query on road networks. IEEE Trans. on Knowledge & Data Engineering, 2014,26(6):1-1.[doi:10.1109/TKDE.2013.174]
    [69] Feng J, Mukai N, Watanabe T. Incremental maintenance of all-nearest neighbors based on road network. In:Proc. of the Innovations in Applied Artificial Intelligence. Berlin, Heidelberg:Springer-Verlag, 2004. 164-169.[doi:10.1007/978-3-540- 24677-0_18]
    [70] Al-Khalidi H, Abbas Z, Safar M. Approximate range query processing in spatial network databases. Multimedia Systems, 2013, 19(2):151-161.[doi:10.1007/s00530-012-0286-9]
    [71] Wang S, Cheema MA, Lin X. Efficiently monitoring reverse k-nearest neighbors in spatial networks. Computer Journal, 2013,58(1):40-56.[doi:10.1093/comjnl/bxt115]
    [72] Fu Q, Sun G, Zhang Z. An efficient pre-computation technique for approximation distance query in road networks. In:Proc. of the IEEE Mobile Data Management (MDM). 2013. 131-135.[doi:10.1109/MDM.2013.82]
    [73] Hua Y, Feng D. A correlation-aware partial materialization scheme for near real-time automotive queries. In:Proc. of the IEEE Smart Computing (SMARTCOMP). 2014. 237-244.[doi:10.1109/SMARTCOMP.2014.7043864]
    [74] Xu J, Gao Y, Liu C, Zhao L, Ding Z. Efficient route search on hierarchical dynamic road networks. Distributed & Parallel Databases, 2014,33(2):227-252.[doi:10.1007/s10619-014-7146-x]
    [75] Delling D, Werneck RF. Customizable point-of-interest queries in road networks. IEEE Trans. on Knowledge & Data Engineering, 2015,27(3):686-698.[doi:10.1109/TKDE.2014.2345386]
    [76] Chen L. Trip planner over probabilistic time-dependent road networks. IEEE Trans. on Knowledge & Data Engineering, 2014,26(8):2058-2071.[doi:10.1109/TKDE.2013.159]
    [77] Liao B, Leong HU, Man LY, Gong Z. Beyond millisecond latency kNN search on commodity machine. IEEE Trans. on Knowledge & Data Engineering, 2015,27(10):2618-2631.[doi:10.1109/TKDE.2015.2426702]
    [78] Yuan Y, Lian X, Chen L, Sun Y, Wang G. RSkNN:kNN search on road networks by incorporating social influence. IEEE Trans. on Knowledge & Data Engineering, 2016,28(6):1575-1588.[doi:10.1109/TKDE.2016.2518692]
    [79] Zeberga K, Cho HJ, Chung TS. A safe-region approach to k-RNN queries in directed road network. In:Proc. of the IEEE Int'l Conf. on Computational Science and Engineering (CSE). 2014. 818-824.[doi:10.1109/CSE.2014.167]
    [80] Cho HJ, Jin R, Chung TS. A collaborative approach to moving k-nearest neighbor queries in directed and dynamic road networks. Pervasive & Mobile Computing, 2014,17:139-156.[doi:10.1016/j.pmcj.2014.07.002]
    [81] Cho HJ, Ryu K, Chung TS. An efficient algorithm for computing safe exit points of moving range queries in directed road networks. Information Systems, 2014,41(3):1-19.[doi:10.1016/j.is.2013.10.008]
    [82] Attique M, Hailu Y, Gudetaayele S, Cho HJ, Chung TS. A safe exit approach for continuous monitoring of reverse K-nearest neighbors in road networks. British Dental Journal, 2015,217(11):617-617.
    [83] Yung D, Man LY, Lo E. A safe-exit approach for efficient network-based moving range queries. Data & Knowledge Engineering, 2012,72(1):126-147. 冯钧等:路网环境下的移动对象查询技术研究综述1625
    [84] Jang S, Yoo J. Processing continuous skyline queries in road networks. In:Proc. of the Int'l Symp. on Computer Science and ITS Applications. 2008. e3594.[doi:10.1109/CSA.2008.30]
    [85] Huang YK, Chang CH, Lee C. Continuous distance-based skyline queries in road networks. Information Systems, 2012,37(7):611-633.[doi:10.1016/j.is.2012.02.003]
    [86] Qamar R, Attique M, Chung TS. A pruning algorithm for reverse nearest neighbors in directed road networks. In:Proc. of the IEEE Computer and Information Science (ICIS). 2015. 279-284.[doi:10.1109/ICIS.2015.7166606]
    [87] Feng J, Watanabe T. A fast search method of nearest target object in road networks. Trans. of the Institute of Systems Control & Information Engineers, 2003,16(9):484-491.[doi:10.5687/iscie.16.484]
    [88] Feng J, Mukai N, Watanabe T. Representation of transportation network and continuous nearest neighbor search. Dbsj Letters, 2003, 2:1-4.
    [89] Zhang D, Chow CY, Li Q, Zhang X, Xu Y. SMashQ:Spatial mashup framework for k-NN queries in time-dependent road networks. Distributed & Parallel Databases, 2013,31(2):259-287.[doi:10.1007/s10619-012-7110-6]
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

冯钧,张立霞,陆佳民,王冲.路网环境下的移动对象查询技术研究综述.软件学报,2017,28(6):1606-1628

Copy
Share
Article Metrics
  • Abstract:5534
  • PDF: 7832
  • HTML: 3469
  • Cited by: 0
History
  • Received:August 26,2016
  • Revised:October 21,2016
  • Online: January 22,2017
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063