空间索引技术研究

空间索引可以提高空间数据库的操作效率,目前人们的研究工作更多地集中在空间数据的多维索引的研究上.文中全面地总结了当前空间数据库领域中空间索引以及时空索引的研究进展,描述了R树系列索引的构建思想,节点插入与分裂操作的不同.通过实验深入分析了R树以及R树变体的磁盘访问率,插入,删除,更新的CPU时间,验证了在数据激增的情况下,R树系列索引的复杂性带来的重叠问题会指数递增.由于R树当前应用的深度和广度,研究基于 R树的高效时空高维索引技术是解决索引应用问题一个有效方法.提出了索引性能改进的方向在于多种索引技术的结合,尤其是树形结构索引和网状结构索引的结合.     

KDT树:一种多维空间数据索引结构

通过扩展KD树索引结构,提出了一种新的多维空间数据索引结构——KDT树,给出了数据结构和算法描述,并通过与当前流行的空间数据索引结构——R树的对比,对其性能进行了测试与评估。实验表明,作为一种主存索引结构,KDT树在时间效率方面明显优于R树,并且此种优势随着索引记录数量的增多而越加明显。此外,KDT树亦能较好地解决常规KD树在索引占据一定空间范围的空间对象(如:线、面、体等)时存在的问题。     

三维R树在空间数据索引中的应用

随着 GIS 在军事和民事上的应用,国内外学者已经研究出各种各样的空间数据索引以提升系统性能。在总结目前空间数据索引技术研究进展的情况下,重点介绍一种适用于三维空间数据库的基于空间聚类的三维 R 树索引技术。     

一种用于空间数据多尺度表达的R树索引结构

针对现有R树无法支持空间数据多尺度表达的问题,提出了一种用于空间数据多尺度表达的R树变形索引结构:(1)允许空间对象出现在非叶结点上;(2)利用树的深度反映空间分辨率的变化,提供分辨率维的支持;(3)树的分支结构考虑对自动制图综合算法的支持.分析了该变形R树索引结构的空间数据多尺度查询过程,并着重对该索引结构生成算法中的约束条件、插入算法和分裂算法进行了讨论.针对相同数据源,使用该方法与基于四叉树的空间数据多尺度索引方法进行了对比实验,结果表明,该索引方法能有效检索多分辨率形式组织的空间数据,具有综合结果记忆功能,效率明显.     

基于Oracle Spatial的空间数据索引

本文介绍了地理信息系统(GIS)中的属性数据和空间数据,详细阐述了基于Oracle Spatial的空间数据索引的分类,R树索引和四叉树索引的特点,以及创建索引时应注意的细节,还进一步比较了这两类索引各自的优缺点和适用条件,为应用时选择何种类型的索引提供了参考标准.     

A树—一种新颖的空间数据索引方法

本文介绍了一种新颖的空间数据索引方法－Ａ树。Ａ树对精确查询，各种拓扑关系上的查询，ＮＮ查询以及面向对象语义的良好支持证明了Ａ树不仅人有对空间数据进行索引时的先进性，并且能够满足大多数空间数据库的应用要求。     

基于空间数据不同索引方法的比较

空间索引是空间数据库的关键技术,其性能的高低决定着整个数据库的效率。本文分别对R树及其变形树、四叉树、网格文件作了介绍,并基于空间数据对这几种索引结构的性能作了比较,其结果为今后进一步研究提供了参考依据。     

Oracle空间数据索引

本文深入分析了Oracle数据库在空间数据索引方面的机制及其强大功能。首先,通过对传统数据类型索引机制的分析,介绍了Oracle数据库在关系数据库中的索引功能。然后,引入了对象数据库的空间数据类型,并深入分析了Oracle空间数据索引的机制;最后通过实际例子加以说明。     

Oracle空间数据索引

本文深入分析了Oracle数据库在空间数据索引方面的机制及其强大功能.首先,通过对传统数据类型索引机制的分析,介绍了Oracle数据库在关系数据库中的索引功能.然后,引入了对象数据库的空间数据类型,并深入分析了Oracle空间数据索引的机制;最后通过实际例子加以说明.     

对象关系型空间数据库的访问方式的改进

对象关系型空间数据库使得地理空间对象可以作为一种新的类型存储到空间数据库中。然而索引访问方式与数据类型是紧密联系的。为了使空间数据库用户为每个新空间数据类型建立自己的索引,同时减轻工作量,对将GiST索引框架引入到空间数据库进行了介绍,并分析了GiST框架下的空间索引的好处与劣势。在此基础上,实现了访问效率较高的GiST R*树索引,并对其时间效率和空间效率进行测试。     

空间索引技术-回顾与展望

空间数据库系统通过引入空间索引机制来提高空间数据操作的效率。迄今人们已经提出了许多空间索引方法,文章回顾了这些方法的基本思想,并根据它们所采用的基础数据结构和存储空间数据的方法将现有的空间索引方法进行分类。最后,简要的讨论了空间索引方法的发展方向。     

空间索引的混合树结构研究

针对大型的空间数据库和多媒体数据库的应用,R-树索引结构是一种有效的高维数据索引结构,但R树也有其缺点,文章提出了一种基于四叉树和R-树的混合树空间索引结构,研究结果表明:在存储开销上,混合树比R-树略高,但插入、删除、特别是查找的性能得到了显著的提高,且索引量越大,混合树的查找性能越明显优于R-树。     

基于Oracle Spatial的GIS数据组织及查询

GIS的一个难点是实现空间数据和属性数据的一体化存储和管理,研究用Oracle Spatial技术来解决这个问题。在确定了采用对象一关系模型来存储GIS数据后,比较了空间数据的两种导入方式,在此基础上,选用EasyLoader工具将GIS数据导入到Oracle数据库中,再用四元树索引为其建立索引。最后,选择Java作为开发工具,采用JDBC方式与Oracle数据库相连并实现了对GIS数据的查询。     

GML空间数据索引机制研究

随着GML规范的不断完善及GIS软件厂商的广泛支持,GML已经成为事实上的空间数据编码、传输、存储、发布的国际标准,越来越多的空间数据开始以GML格式存储。如何有效地存储管理GML空间数据,已经成为GIS研究的热点问题。结合XML 文档编码和传统的空间数据索引,对GML空间数据的索引进行了深入的研究,提出了基于空间索引的GML一体化索引机制以及相应的查询处理策略与相关算法,并以R树索引为例,对一体化索引的查询处理性能进行了实验分析。实验结果表明,该文提出的基于空间索引的GML一体化索引机制是可行的、高效的。     

Efficient processing of spatial joins with DOT-based indexing

A spatial join is a query that searches for a set of object pairs satisfying a given spatial relationship from a database. It is one of the most costly queries, and thus requires an efficient processing algorithm that fully exploits the features of the underlying spatial indexes. In our earlier work, we devised a fairly effective algorithm for processing spatial joins with double transformation (DOT) indexing, which is one of several spatial indexing schemes. However, the algorithm is restricted to only the one-dimensional cases. In this paper, we extend the algorithm for the two-dimensional cases, which are general in Geographic Information Systems (GIS) applications. We first extend DOT to two-dimensional original space. Next, we propose an efficient algorithm for processing range queries using extended DOT. This algorithm employs the quarter division technique and the tri-quarter division technique devised by analyzing the regularity of the space-filling curve used in DOT. This greatly reduces the number of space transformation operations. We then propose a novel spatial join algorithm based on this range query processing algorithm. In processing a spatial join, we determine the access order of disk pages so that we can minimize the number of disk accesses. We show the superiority of the proposed method by extensive experiments using data sets of various distributions and sizes. The experimental results reveal that the proposed method improves the performance of spatial join processing up to three times in comparison with the widely-used R-tree-based spatial join method.     

一种基于Hilbert排列码的GIS空间索引方法

分析了基于栅格格网的索引数据结构在空间查询中的重要地位,讨论了基于多维数据一维映射的空间排列的优点,对Morton码、Gray码、Hibert码和Sierpinsky码的空间聚类特征进行了分析和比较,得出了Hilbert码在空间查询中效率最高的结论,考虑到基于特征的GIS数据模型的特点,兼顾内存索引与磁盘索引,提出了基于Hilbert空间排列的点特征二叉平衡排序树动态索引结构和基于角点回溯的线特征索引结构,并对其在GIS空间查询中的应用方法进行了论述。     

A generic and efficient framework for flash-aware spatial indexing

Spatial indexing on flash-based Solid State Drives (SSDs) has become a core aspect in spatial database applications, and has been carried out by flash-aware spatial indices. Although there are some flash-aware spatial indices proposed in the literature, they do not exploit all the benefits of SSDs, leading to loss of efficiency and durability. In this article, we propose eFIND, a new generic and efficient framework for flash-aware spatial indexing. eFIND takes into account the intrinsic characteristics of SSDs by employing (i) a write buffer to avoid expensive random writes, (ii) a flushing algorithm that smartly picks modifications to be flushed in batch to the SSD, (iii) a read buffer to decrease the overhead of random reads, (iv) a temporal control to avoid interleaved reads and writes, and (v) a log-structured approach to provide data durability. Performance tests showed the efficiency of eFIND. Compared to the state of the art, eFIND improved the construction of spatial indices from 43% to 77%, and the spatial query processing from 4% to 23%.     

R-树结点分配的新算法

近年来,针对空间数据库索引的研究引起了人们越来越多的兴趣和关注。为了快速、有效地处理存储于空间数据库中的海量空间数据,专家学者提出了大量的基于磁盘的空间索引方法。其中,1984年Guttman提出的R-树是目前非常有效的空间索引结构。针对R-树的结点分配算法存在的不足,提出了一种新的结点分配算法。研究结果表明： 新的分配算法比原始的算法产生的交叠会更小,从而有效地控制了多路查询的几率,较明显地提高了空间查询的效率。     

基于数据库的多分辨率地形索引结构的研究

当空间应用进入到网络化后，人们迫切需要利用数据库的约束机制为空间数据提供更好的保护，目前数据库系统只能管理单一分辨率的地形空间数据。该文提出了一种可在关系数据库顶端实现的、支撑动态多分辨率地形与可视化数据调用的关系模型。该模型解决了在大规模地形可视化程序中，数据库系统客户端/服务器间的数据交换问题，利用了X树索引技术将多分辨率地形映射到关系模型中，利用特征空间将累进查询过程转换为几个简单的一维范围查询的联合，在各表中每个帧分别进行一次索引扫描，即可获得全部必要的数据，使其更好地处理大规模的地形数据。实验结果表明，利用该模型能够获得良好的检索效果。