A Hybrid Spatio-Temporal Data Indexing Method for Trajectory Databases

Sensors - Tập 14 Số 7 - Trang 12990-13005
Shengnan Ke1, Jun Gong2,1, Songnian Li2, Qing Zhu3, Xintao Liu2, Yeting Zhang4
1School of Software, Jiangxi Normal University, Nanchang, 330022, China
2Department of Civil Engineering, Ryerson University, Toronto, Ontario M5B 2K3, Canada
3Faculty of Geosciences and Environmental Engineering, Southwest Jiaotong University, Chengdu 611756, China
4State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China

Tóm tắt

In recent years, there has been tremendous growth in the field of indoor and outdoor positioning sensors continuously producing huge volumes of trajectory data that has been used in many fields such as location-based services or location intelligence. Trajectory data is massively increased and semantically complicated, which poses a great challenge on spatio-temporal data indexing. This paper proposes a spatio-temporal data indexing method, named HBSTR-tree, which is a hybrid index structure comprising spatio-temporal R-tree, B*-tree and Hash table. To improve the index generation efficiency, rather than directly inserting trajectory points, we group consecutive trajectory points as nodes according to their spatio-temporal semantics and then insert them into spatio-temporal R-tree as leaf nodes. Hash table is used to manage the latest leaf nodes to reduce the frequency of insertion. A new spatio-temporal interval criterion and a new node-choosing sub-algorithm are also proposed to optimize spatio-temporal R-tree structures. In addition, a B*-tree sub-index of leaf nodes is built to query the trajectories of targeted objects efficiently. Furthermore, a database storage scheme based on a NoSQL-type DBMS is also proposed for the purpose of cloud storage. Experimental results prove that HBSTR-tree outperforms TB*-tree in some aspects such as generation efficiency, query performance and query type.

Từ khóa


Tài liệu tham khảo

Wang, 2010, GPS-free localization algorithm for wireless sensor networks, Sensors, 10, 5899, 10.3390/s100605899

2009, Sensing human activity: GPS tracking, Sensors, 9, 3033, 10.3390/s90403033

Hayajneh, 2013, Data management for the internet of things: Design primitives and solution, Sensors, 13, 15582, 10.3390/s131115582

Parent, 2013, Semantic trajectories modeling and analysis, ACM Comput. Surv., 42, 1, 10.1145/2501654.2501656

Goodchild, 2013, Prospects for a space-time GIS, Annu. Assoc. Am. Geogr., 103, 1072, 10.1080/00045608.2013.792175

Pfoser, D., Jensen, C., and Theodoridis, Y. (2000, January 10–14). Novel Approaches to the Indexing of Moving Object Trajectories. Cairo, Egypt.

Zheng, Y., and Zhou, X. (2011). Computing with Spatial Trajectories, Springer-Verlag New York Inc.

Frentzos, E. (2008). Trajectory Data Management in Moving Object Databases. [Ph.D. Thesis, University of Piraeus, Piraeus, Greece].

Mokbel, 2003, Spatio-temporal access methods, IEEE Data Eng. Bull., 26, 40

Chakka, V., Everspaugh, A., and Patel, J. (2003, January 5–8). Indexing Large Trajectory Data Sets with SETI. Asilomar, CA, USA.

Aref, 2010, Spatio-temporal access methods: Part 2 (2003–2010), IEEE Data Eng. Bull., 33, 46

He, 2013, Parallel indexing technique for spatio-temporal data, ISPRS J. Photogramm. Rem. S., 78, 116, 10.1016/j.isprsjprs.2013.01.014

Gong, 2012, An efficient point cloud management method based on a 3D R-tree, Photogramm. Eng. Rem. S., 78, 373, 10.14358/PERS.78.4.373

Lee, 2011, Geopot: A cloud-based geolocation data service for mobile applications, Int. J. Geogr. Inform. Sci., 25, 1283, 10.1080/13658816.2011.558017

Aggarwal, C. (2013). Managing and Mining Sensor Data, Springer Publishing.

Zhu, 2007, An efficient 3d R-tree spatial index method for virtual geographic environments, ISPRS J. Photogramm. Rem. S., 62, 217, 10.1016/j.isprsjprs.2007.05.007

Brinkhoff, 2002, A framework for generating network-based moving objects, GeoInformatica, 6, 153, 10.1023/A:1015231126594

Thông tin
Thông tin xuất bản

Sensors

Tập 14 Số 7

12990-13005

Thông tin tác giả