ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2019, Vol. 56 ›› Issue (3): 666-676.doi: 10.7544/issn1000-1239.2019.20170750

Previous Articles    

A Spatio-Temporal Index Based on Skew Spatial Coding and R-Tree

Zhao Xinyi1, Huang Xiangdong1,2, Qiao Jialin1, Kang Rong1, Li Na1, Wang Jianmin1,2   

  1. 1(School of Software, Tsinghua University, Beijing 100084); 2(Beijing Key Laboratory for Industrial Bigdata System and Application, Beijing 100084)
  • Online:2019-03-01

Abstract: With the development of mobile Internet and Internet of Things, more and more mobile devices such as vehicles and mobile phones are embedded with GPS services. These devices generate a lot of spatio-temporal data with multi-dimensional attributes such as time, space longitude and latitude when moving. Traditional spatio-temporal indexes have neither the ability to handle large amounts of data, nor the ability to handle data with both time and space dimensions, nor the ability to support many kinds of spatio-temporal query. This paper illustrates GRIST (Geohash and R-Tree based index for spatio-temporal data), an innovative two-level spatio-temporal index based on Geohash and R-Tree. The first layer is a spatial index based on grid partition, which partitions the space into non-overlapping subspaces with different size. Each grid is encoded by Geohash. The second layer is the time layer index based on the R-Tree, where each spatial grid corresponds to a one-dimensional R-Tree index. Also, this paper supports two types of queries, one is time-based query, the other is spatio-temporal-based query which can be further subdivided into range query and trajectory query. In addition, this paper realizes GRIST by NoSQL K-V database Cassandra and uses Spark to realizes distributed query. Compared with PostGIS and GeoMesa, GRIST has better load and query performance, 10~45 times better in load time and 2~4 times better in query time.

Key words: spatio-temporal data, spatio-temporal index, spatio-temporal range query, trajectory query, distributed data management

CLC Number: