面向时空数据流的移动对象空间索引构建

A Moving Object Spatial Index for Spatio-Temporal Data Stream

本文针对时空数据流提出了一种基于时间窗口数据排序和批量装载的移动对象空间索引构建方法HSTRCL.该方法用固定长度的时间窗口将连续的时空数据流进行切分,每当一个时间窗口完成数据缓存,采用优化的索引批量装载技术,从传统的构建流程中尽可能分离出耗时的数据划分和排序操作,将数据流的接收及其他构建操作并行执行,避免不必要的加锁同步开销,加快索引的构建效率;同时,采用基于Hash和STR的主、辅索引构建技术,满足高性能且多样化的查询需求.另外,为进一步提高对象查询性能,引入聚合技术划分对象,提出了一种基于时间窗口对象聚合和批量装载的移动对象空间索引构建方法OAHSTRCL,对象查询时间约为HSTRCL的65%,但对空间查询性能会有一定程度的影响.通过理论分析和多种实验验证了所提方法的有效性.

In light of the characteristics of spatio-temporal data stream,we propose a moving object spatial index construction method called HSTRCL,which is based on time window data sorting and bulk loading.It segments the continuous spatio-temporal data stream with fixed-length time windows;after finishing caching the data of a time window,by combining parallel processing and optimized bulk loading technology,we isolate as much as possible the time-consuming work of data partitioning and sorting operations from the traditional build process,and parallize them with the reception of data streams and other build operations.Furthermore,we avoid unnecessary locking synchronization overhead.And all these techniques improve the efficiency of index construction.In addition,to meet the performance and diverse query requirements,we also adopt the primary-auxiliary index construction technology based on Hash and STR.To further improve the performance in the object query scenario,we invent another moving object spatial index construction method OAHSTRCL via time window object aggregation and bulk loading,where objects are divided more finely,and the object query time required is about 65% of HSTRCL,though it will affect the performance of spatial query to some extent.Theoretical analysis and experiments have demonstrated the effectiveness of our proposed methods.