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

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.