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

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.

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

当今中国社会面临的诸如环境污染、土地演化、海岸变迁、人口剧增、城市扩张、传染病转播、火灾传播、泥石流等自然灾害监控与防治等问题，无不与时空概念紧密相关，并且每时每刻都在持续不断地产生着大量的时空数据。时空数据可以帮助人类了解历史、掌握现在、预测将来，有助于提高人类对四维时空中各种存在与状态演变的洞察、感知与预测能力；对环境监测、矿山安全、城市内涝、土地管理、泥石流和地震等自然灾害的监测、预报、防治与救援等时空敏感性问题的求解具有重要意义。项目针对分布式并行计算环境下时空大数据高效存储与访问需求，主要在分布式并行计算环境下的智能时空索引理论架构、基于间隔数据集的多维时空对象表达方法、间隔关系算子与间隔数据索引方法、时序数据的分布式时空索引与相似性查询、基于异构内存的分布式时空数据计算框架、并行索引算法及其在地形可视化方面的应用等方面开展了较为深入的研究工作。.项目研究提出了一种分布式并行计算环境下的智能时空索引架构，实现了一种基于异构内存的分布式时空大数据计算框架，它将时空数据及其所有操作抽象为时空管道、时空数据集和时空转换，之上提供时空要素数据集和要素存储接口, 以屏蔽底层分布式操作细节；实验结果表明, 该框架能有效支持异构集群上的大规模空间数据的高效查询和处理。基于该计算框架，设计并实现了基于间隔关系算子的多维分布式并行时空索引方法，将多维时空数据转化为多个独立的间隔数据集合；采用基于三角区域递归分解的虚拟二叉树实现各种间隔关系算子操作，将复杂多维时空查询问题转化成一系列简单的可并行的间隔关系算子的多核并行计算问题，实现了单个多维时空数据索引内部的并行计算。该索引方法在细化时空索引并行粒度的同时降低其并发控制开销，充分发挥多核计算机性能优势，提高了多维时空索引性能，为多核计算环境下的海量三维、四维或更高维的时空数据的快速检索提供了通用、高效的分布式并行时空索引解决方案。