三维场景中基于空间方向关系的混合索引结构研究

The situation that the large-scale application of three-dimensional scene in the internet which is called as ”3D internet” proposes new requirements which are more accurate index structure and more faster query mechanisms. To meet this demand, first of all, we propose a new idea named equivalent transform for query process. The index structures and query language will be equivalent transformed to generate the new structures to speed up the process because of the characteristics of spatial structure. Experimental results show the effectiveness of the proposed transformation scheme. Second, an accurate, multi-layered and cleared mix index structure will be proposed by directional relationship combined with multi spatial relationship such as topological relationship and distance relationship. Last, the group will combine the mixed index structures and the method of equivalent transform to create a new faster and more accurate query process to satisfy the needs of three-dimensional internet.

三维场景在网络环境下的大规模应用即“三维互联网”的迅猛发展，对三维空间数据的索引结构和查询机制提出更快速、更准确的新要求。为应对这一时代发展的需求，本课题首先针对查询过程提出等价转化的新思想，将空间数据的索引结构与查询语句进行相同的等价转化，利用的转化后所获得的新索引结构在空间结构上的特性对查询过程进行优化，现有实验表明这一思路是可行的；其次，本课题提出结合空间数据的特性，将方向关系与拓扑关系、距离关系等多种空间关系相结合，生成准确的、多层次的、清晰的混合索引结构；最后，将混合索引结构与等价转化思想相结合，得到全新的、快速的、准确的能够满足“三维互联网”应用需求的索引结构和查询优化机制。

随着三维空间数据的大量获取和广泛应用，对于空间数据库中三维空间对象的索引结构和查询机制提出了更高的要求。一方面，目前的索引结构采用单一化结构，很难适应复杂多变的三维空间对象的存储要求，因此需要研究结合三维对象本身所具有的空间关系的、高效率的混合索引结构；另一方面，现有的查询机制也应该得到进一步的研究与发展，通过与等价转化等新思路的结合获取更为高效的查询处理理论，使其更好的满足空间数据查询的需求。在研究工作中，本课题首先研究空间方向关系理论，形成完整的三维空间方向关系基础理论体系，提出基于三维空间中方向关系定性推理及查询方法；其次，将三维空间对象本身所具有的空间关系与现有的索引结构研究相结合，提出更准确的、多层次的、清晰的混合索引结构，提高对三维空间对象的索引效率；最后，在此基础之上，利用等价转化理论，对混合索引结构与空间查询作相应的优化，以提高空间数据查询的效率。目前，对于模糊移动对象的方向关系推理进一步完善了空间关系理论；建立Grid+R树的高效率的混合索引结构来索引分布不平均的三维点空间对象，使空间查询的效率提高了约40%；将空间方向与距离的组合推理应用于分布式障碍空间数据库的可视查询机制的优化中，大幅提高了可视查询算法性能；通过创建可视性关系表，建立了三维虚拟现实场景基于可视查询的动态加载框架。在保持用户体验不变的前提下，极大的减少了空间对象的加载数量，降低了对于网络带宽和硬件的要求；提出基于等价转化的k最近邻查询提高了空间数据的查询效率。将本课题的工作继续进行下去，会获取完整的三维空间关系基础理论。将其应用于对于三维空间对象的高效索引结构和查询机制的研究中，可以构建起以空间数据库为核心的网络环境下的三维场景引擎。基于该引擎可以实现对三维虚拟现实场景的快速、准确的查询与最低数据量的加载。这不仅符合云计算及移动互联网的发展趋势，更可以推动以虚拟现实应用为中心的“三维互联网”的发展。