基于间隔关系算子的多维分布式并行时空索引方法

分布式并行时空索引是海量时空数据高效分布式访问与协同计算的基础。并行时空数据索引更新频繁导致并发控制成本非常高。常见的时空索引多是严格的树型层次结构，这导致了多维时空环境下的树节点重叠问题，增加了并发控制难度，也严重制约了单个查询中索引内部算法的并行化，限制了其在分布式多核计算环境中的性能表现。课题针对性提出基于间隔关系算子的多维分布式并行时空索引方法，拟将多维时空数据转化为多个独立的间隔数据集合；采用基于三角区域递归分解的虚拟二叉树实现各种间隔关系算子操作，将复杂多维时空查询问题转化成一系列简单的可并行的间隔关系算子的多核并行计算问题，实现单个多维时空数据索引内部的并行计算。该索引方法将在细化时空索引并行粒度的同时降低其并发控制开销，充分发挥多核计算机性能优势，提高多维时空索引性能，将为多核计算环境下的海量三维、四维或更高维的时空数据的快速检索提供通用、高效的分布式并行时空索引解决方案。

Distributed parallel spatio-temporal index is the basis of massive spatio-temporal data distrubuted access and collaborative computing. Because of the frequent updation of spatio-temporal data index, it results in very high cost of concurrency control in the index. Common multi-dimensional spatio-temporal indexes are mostly tree structures with strict hierarchy. It leads to the node overlapping problem and concurrency control problem in a high-dimensional spatio-temporal environment, and severely restricts the indexing algorithm parallelization in a single query. Furthermore it limits the indexing performance on multicore computers. For resolving this problem, a multi-dimensional parallel spatio-temporal indexing method based on interval relationship operators will be proposed in this project. This method intends to transform the multi-dimensional spatio-temporal data into multiple independent interval data collections, implements all the kinds of interval relationships operators via a virtual binary tree based on recursive triangle region decomposition. This transformation replaces the complex multi-dimensional spatio-temporal queries with a series of simple parallel interval data relationship operators. This index can reduce the concurrency control while refining the parallel granularity. It is helpful to implement the multi-dimensional parallel spatio-temporal data index in the multi-core parallel computing environment, and hence to improve the performance of the multi-dimensional spatio-temporal index. The index method proposed in this project will provide an effective and efficient distributed parallel spatio-temporal index solution for the fast multi-dimensional spatio-temporal data retrieval in the multi-core computing environment.