Distributed Moving Object Spatial Index For Spatio-Temporal Data Stream

With the rapid development of the Internet of Things technology,the application scenarios of location-based services(LBS)in real life are becoming more and more widespread.The data collected by LBS usually carries information in the time and space dimensions,so it can be referred to as spatio-temporal data,and the streaming spatio-temporal data that arrives continuously is referred to as spatio-temporal data stream.In the spatio-temporal data stream scenario,traditional index construction methods are difficult to achieve good performance.They usually only consider limited static data,or dynamically update existing indexes in batches,but without considering the characteristics of spatio-temporal data stream,such as infinity,disorder and real-time.In this regard,this paper proposes a distributed moving object spatial index for spatio-temporal data stream,which can support the efficient storage of massive spatio-temporal data and provide fast and reliable query services.The main contributions of this paper are as follows:1.A moving object spatial index construction method based on time window data sorting and bulk loading is proposed,which called HSTRCL.This method divides the continuous spatio-temporal data stream through the time window,and then uses the improved STR algorithm to construct the spatial main index in each time window.At the same time,it combines the hash algorithm to construct the object auxiliary index in order to meet various types of query requirements.In addition,in order to reduce the index construction delay as much as possible,after the end of each time window,the relevant parameters of the index are calculated in parallel and the R-tree skeleton is constructed,while the rapid bulk loading method is used for index construction.2.A moving object spatial index construction method based on time window object aggregation and bulk loading is proposed,which called OAHSTRCL.Based on HSTRCL,this method pre-aggregates spatio-temporal data according to the unique identifier of its corresponding moving object,then obtains a number of object aggregation units,which called OAC,and then continues to perform subsequent index construction steps based on OAC.Compared with HSTRCL,this method has faster construction speed,lower latency,and better performance on object query,but the performance of spatial query is slightly worse than the former.3.A distributed index system oriented to spatio-temporal data stream is proposed.It uses a two-layer index structure,which contains inner and outer layers.The outer layer uses the B+ tree to index in the time dimension.The inner layer uses the main-auxiliary index structure to index spatial data and moving objects.In addition,by combining methods such as improved consistent hashing algorithm and multiple copies of the outer layer index,it can provide high-performance query services,while achieving rapid index construction and reasonable storage of massive spatio-temporal data.