空间对象数据库的网格索引机制

本文提出了针对空间对象的一种新的索引机制，称为网格索引。Ｌｄｅｘ基于空间对象的位置及其分布，是一种高效实用的空间索引方法。文章全面地讨论了它的查找、插入、删除和修改算法及实现技术。     

UPNIS的空间查询——面向类对象的八叉树空间索引机制

针对管网信息系统中的三维空间对象－管网,提出了一种基于固定三维网格划分的八叉树空间索引机制,称为Ｏｃｔｒｅｅ;并提出了一种层次分明的编码方法,有效地存储和管理数目庞大的八叉树结点。为了进一步缩小空间查询检索操作的范围,引入了面向类对象的二级查询技术,有效地提高了城镇管网信息系统ＵＰＮＩＳ的性能。     

空间数据库网格索引机制的最优划分

该文证明了当空间对象的分布特征小于0．2929时，一级网格索引机制才有效，并获得了最佳网格划分条件，通过分析二级网格的最优划分，证明了二级网格检索机制比一级网格索引机制有效，可以减少存储桶的个数。     

基于数据空间网格划分的PK-树索引结构

在大规模高维数据挖掘研究中,数据存储与索引方法的有效性是决定算法时空效率的重要因素。将数据空间网格划分策略与高效率的树型索引结构结合起来,可以充分发挥两者在数据组织上的综合优势,将复杂问题转换为结构化的简单重复问题：在统一的框架下给出了各种数据空间网格划分的定义,讨论了两种适用于实现网格化数据索引的R-树和PK-树索引结构：试验结果表明,PK-树在数据存储和索引上具有更高的效率,与网格化数据组织方法结合起来,对于降低大规模高维数据分析问题的时空复杂度具有重要意义。     

一种基于R树和四叉树的移动对象空间数据库混合索引结构

由于实时跟踪移动的空间对象需要不断的更新空间数据库的索引从而导致系统执行效率非常低下，传统静态的空间索引结构性能并不是很好的工作在动态环境下。提出了一种称为Q＋R树的移动空间对象混合索引结构，阐述了该数据结构的生成、更新、查询方面算法思想，最后给出了Q＋R树的试验分析结论。     

基于数据空间网格划分的PK 树索引结构*

在大规模高维数据挖掘研究中,数据存储与索引方法的有效性是决定算法时空效率的重要因素。将数据空间网格划分策略与高效率的树型索引结构结合起来,可以充分发挥两者在数据组织上的综合优势,将复杂问题转换为结构化的简单重复问题。在统一的框架下给出了各种数据空间网格划分的定义,讨论了两种适用于实现网格化数据索引的R树和PK树索引结构。试验结果表明,PK树在数据存储和索引上具有更高的效率,与网格化数据组织方法结合起来,对于降低大规模高维数据分析问题的时空复杂度具有重要意义。     

一种基于网格与R树的多级混合索引

结合网格索引和R树索引的特点,提出了一种基于网格与R树的多级混合索引.该方案首先将矩形地理空间进行粗网格划分建立多级网格索引.然后针对每个小网格建立基于R树的空间索引.详细讨论了该索引的结构、建立算法、删除算法以及应用该索引的检索算法,并进行了算法分析.与网格索引和R树索引相比,该索引以略大的空间开销换取了更高的查找性能.     

主存空间对象的索引方法

空间索引关系空间数据库和地理信息系统的整体性能。目前，随着计算机主存价格的迅速下降，发展主存空间数据库已经成为可能，主存空间数据库需要相适应的空间索引。本文设计两种主存的空间索引－主存网格索引和主存Ｆ－树索引，并对两者的性能进行比较。在多数应用环境下，Ｆ－树空间索引性能更优。     

基于动态网格的移动对象索引

在移动对象数据库中,移动对象的数量可能会经常变化,这就给索引技术提出了新的挑战。移动对象索引技术的效率是移动对象数据库的一个重要研究课题。为了防止数据库由于移动对象数量的变化而导致性能锐减,本文在网格文件索引的基础上提出了一种动态网格索引技术。通过实验比较显示,它相对于静态索引具有更好的适应性。     

加速PMR四分树构造的研究

PMR四分树空间索引结构在包含空间连接的空间数据库的查询中是很有效的,本文对桶载入PMR四分树的算法做了一些改进,即两种互补的技术：一种改进的插入算法和一种桶载入方法。该技术使得四分树的构造速度相对于传统的四分树构造方法大大提高。该方法可运用到许多基于规则划分的空间数据结构上,来加快它们的构造。     

UPNIS的空间查询─面向类对象的八叉树空间索引机制

针对管网信息系统中的三维空间对象一管网,提出了一种基于固定三维网格划分的八叉树空间索引机制,称为Ｏｃｔｒｅｅ;并提出了一种层次分明的编码方法,有效地存储和管理数目庞大的八叉树结点。为了进一步缩小空间查询检索操作的范围,引入了面向类对象的二级查询技术,有效地提高了城镇管网信息系统ＵＰＮＩＳ（ＵｒｂａｎＰｉｐｅｌｉｎｅＮｅｔｗｏｒｋＩｎｆｏｒｍａｔｉｏｎＳｙｓｔｅｍ）的性能。     

基于空间和属性数据的联合索引技术

传统联合查询通常需要空间数据库对2个索引进行检索,通过集合运算得到最终结果,运算效率较低。针对该缺陷,提出基于空间和属性数据的联合索引技术,在索引目录项中加入属性数据提高联合检索速度。实验结果表明,该技术对于属性与空间位置有较高相关度的数据,具有较高查询效率。     

基于移动对象运动模式构建的空间索引结构

由于实时跟踪移动的空间对象需要不断地查询和更新空间数据库的索引，经典R树空间索引结构的静态管理空间对象的方法并不适合移动环境，从而导致系统执行效率非常低下。根据对移动对象运动模式的分析，文中提出了一种称为ASI（Adaptive Spatial Index based on Motion Characteristic of Moving Objects）的移动空间对象索引结构，阐述了该索引结构的核心算法、构造方法、具体的数据存储方案，最后给出了该索引结构的试验分析结果。     

面向移动GIS的动态四叉树空间索引算法

介绍了常用的空间索引算法,对其性能进行了比较,认为这些算法用于需要动态更新空间索引结构的移动GIS系统中时具有较大的局限性。针对移动GIS系统中对空间索引的特殊要求,提出了动态四叉树空间索引算法,对算法的计算效率进行了分析,实验表明该算法用于移动GIS系统时效果良好。     

基于DPR树的分布式并行空间索引机制的研究

针对分布式并行环境下海量空间数据管理与并行化处理的效率问题,以提高分布式并行空间数据的查询效率为目的,根据现有的空间索引结构与并行化技术,提出一种新的分布式并行空间索引结构--DPR树.DPR树是空间索引技术与并行化技术优化结合的成果.DPR树在数据的总体划分与部分查询中所采用的均是基于高效处理技术.它在原有的并行Master-client R树的基础上进行改进,采用了HCSDP数据划分技术,并将其应用到分布式环境下,且每个节点机中各子树采用了改进的R树--R*Q树.通过性能分析表明,该索引结构具有高效的查询性能.     

一种有效的混合空间索引机制

论文结合网格索引和R树索引的特点,提出了一种基于粗分网格和聚类R树的混合索引方案(HSIBGR)。该方案首先将矩形地理空间进行粗网格划分建立一级索引,然后针对每个小网格建立基于R树的二级索引,采用聚类技术处理溢出R树结点的分裂。论文还对HSIBGR索引机制进行了理论分析和实验验证,结果表明HSIBGR索引机制能有效地减少存储开销,提高检索效率,具有良好的性能。     

一种基于二层网格的移动对象B+树索引

在已有的基于空间分割的移动对象B+树索引基础上,提出一种分割空间的新方法,对空间进行二层网格分割,使空间分割很好地解决由移动对象在空间中分布不均造成的索引效率下降的问题。给出基于这种索引结构的Range查询和kNN查询算法。实验结果表明, 该索引结构的性能基本不受移动对象分布的影响。     

边界约束的非相交球树实体对象多维统一索引

针对现有空间索引剖分结构复杂、节点重叠率高及对多维实体对象检索及运算支撑较弱等问题,构建了一种边界约束的非相交球实体对象多维统一空间索引;利用球的几何代数外积表达,提出了基于求交算子的直线-平面和直线-球面的相交判定与交点提取方法,建立了多维实体对象体元化剖分方法及包含边界约束的非相交离散球实体填充算法,实现了实体对象空间均匀、非重叠的分割,并在填充球的个数、重叠率以及对象逼近近似度等约束条件上获得了较好的平衡.定义了最小外包球生成与更新的迭代算法与包含球体积修正的批量Neural Gas层次聚类算法,在尽可能保证球树各分支平衡性的前提下,实现了索引层次体系的稳健构建.利用几何代数下球对象间几何关系计算的内蕴性与参数更新的动态性,实现了索引结构的动态生成与更新,进而设计了实体对象表面及其内部任意位置及区域的检索策略及基于实体索引的空间关系计算方法.基于不同实体对象的模拟实验显示,基于几何代数的实体对象索引可以有效实现多维实体对象表面及其内部任意位置及区域的快速检索,并能在有限时间内以较高的精度实现多维实体对象最近邻距离和动态实体对象相交状态的检索.相对于常用球树索引,所提出的索引方法在填充率、节点重叠率、填充误差、体元个数、层次球个数、体积百分比和时间占用等方面均具有明显优势,且不同分辨率剖分条件下的索引结构及空间关系计算精度具有更高的稳健性,可运用于具有较强时间约束下复杂多维动态场景中对象检索与空间关系计算.     

QR-树:一种基于R-树与四叉树的空间索引结构

提出了一种基于R-树与“四叉树”空间层次划分的空间索引结构QR-树,给出了其数据结构和算法描述。实验证明:与R-树相比,QR-树以略大(有时甚至略小)的空间开销代价,换取了更高的性能,且索引目标数越多,QR-树的整体性能越好。     

R*-树空间索引的改进

R*-树基于局部调整的思想对节点进行管理,存在时间与效率上的不足。为克服R*-树的不足,给出了一种新型的存储结构,并给出新型存储结构的插入、溢出、分裂等空间索引常用操作的算法。分析新的存储结构的优点,并通过实验结果说明该方案比R*-树具有更高的效率。