GIS空间索引技术探究

空间索引是空间数据库的关键技术之一,也是困扰GIS工作者的最大难题之一。因而对如何建立更有效的空间索引结构一直是GIS领域最现实、最急迫、也是最前沿的研究课题。本文介绍了GIS中具有代表性的几种空间索引方法,并且进行了分析对比。最后,简要的讨论了空间索引方法的发展方向。     

空间查询处理技术综述

空中索引是依据空间对象的位置和形状或空间对象间的某种关系,按照一定顺序排列的一种数据结构。不同方式组织起来的索引结构需采用不同的检索方法,因此空中索引在一定程度上决定了空间查询处理的效率。回顾了常用的空间查询处理方法,并对现有的空中索引结构及空间查询处理技术进行了系统分类,分别对欧式空间、道路网络及无线广播环境下用于空间查询处理的空中索引及查询算法进行了详细描述。     

空间数据库索引技术的研究

空间数据库的索引是提高空间数据库存储效率、空间检索性能的关键技术。传统的索引技术不能有效地索引空间数据。在综述现有空间数据库索引技术的基础上，提出了一种面向大型空间数据库的QR-树索引方法。     

空间数据在嵌入式导航系统中的索引

研究了基于嵌入式Linux平台电子地图数据的空间索引,介绍了空间索引的基本方法。通过分析常见的空间索引算法如B树、R树、四叉树等算法的特点,结合嵌入式电子地图数据特点,设计了基于Hilbert编码的格网空间数据索引机制,并改进了格网索引的数据结构,从而提高了索引效率;并使用嵌入式数据库SQLite管理空间数据,达到了预期效果。     

一种PMR四叉树空间索引效率分析模型的研究

空间索引效率分析模型技术在每一个商业应用中都会有一套特定的分析模型和评判标准,并且评估模式的指标和权重带有很大的主观性,需要引入科学方法来确定有效指标。探讨了针对PMR四叉树索引的空间索引效率分析的特殊案例,将最优化技术引入到空间索引效率分析中,使得空间索引的性能评价有了一定的理论依据。     

一种基于动态散列的GIS空间索引构造算法

文章在介绍动态散列和传统空间索引四叉树的构造方法的基础上,综合二者的优点,提出了一种基于动态散列的空间索引构造算法,该方法改变了传统四叉树通过效率低下的空间对象的递归比较构造索引过程,采用计算机运算效率较高的二进制位运算和位比较的动态散列扩充散列值来构造空间索引。实践证明,该算法大大减少了空间索引的构造时间和效率,具有很高的应用价值。     

一种GIS自适应层次网格空间索引算法

分析了目前常用的空间索引算法的缺点,对应用最为广泛的网格空间索引数据结构进行了剖析;在描述了网格空间索引算法的同时,依据空间实体外接矩形的几何特性,给出了具有自适应能力的改进型网格空间索引算法———自适应层次网格空间索引算法;最后分析了此算法的自适应性和索引效率。     

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

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

空间索引技术研究

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

基于iMeMex数据模型的数据空间索引方法研究

目前,个人和组织的信息呈现急剧增长趋势,且非结构化数据所占比重在不断增加,这些属于某个主体的海量、分布、异构和共存的数据构成了一个异构数据空间,如何为用户提供高效、便捷和多样化的搜索查询服务是数据空间面临的巨大挑战,为数据空间中异构数据构建高效的索引方法是解决这一问题的基础。对iMeMex数据模型的特点和数据空间中查询方法进行了分析,在此基础上通过扩展倒排列表方法,提出了一种基于iMeMex数据模型的索引方法,来提高对数据空间中异构数据的搜索查询效率。新的索引方法通过扩展倒排列表的关键字列和链表节点信息索引资源视图,来支持和提高关键字查询、谓词查询和路径查询的处理效率。实验结果表明,该索引方法能够有效、可行地解决数据空间中异构数据索引和查询效率问题。     

GML空间数据索引机制研究

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

基于Oracle Spatial的空间数据索引

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

空间数据索引技术

多维数据库的应用日益广泛，如何有效地存储组织多维的数据，提高多维数据处理的效率已成为一个核心问题，对空间数据索引技术的研究情况作了分析，介绍了各类技术的基本思想，最后着重介绍一种用于高维持特征向量检索的新的、通用的空间数据索引技术，将只能在空间坐标数据类型之上建立索的传统的R树扩充为任意在数据类型上建立索引的类属的R树。     

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.     

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%.     

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

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

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

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

Direction relations and two-dimensional range queries: optimisation techniques

This paper defines direction relations (e.g., north, northeast) between two-dimensional objects and shows how they can be efficiently retrieved using B-, KDB- and R- tree-based data structures. Essentially, our work studies optimisation techniques for 2D range queries that arise during the processing of direction relations. We test the efficiency of alternative indexing methods through extensive experimentation and present analytical models that estimate their performance. The analytical estimates are shown to be very close to the actual results and can be used by spatial query optimizers in order to predict the retrieval cost. In addition, we implement modifications of the existing structures that yield better performance for certain queries. We conclude the paper by discussing the most suitable method depending on the type of the range and the properties of the data.     

Using B<Superscript>+</Superscript>-trees for processing of line segments in large spatial databases

Points, lines, and regions are the three basic entities for constituting vector-based objects in spatial databases. Many indexing methods (G-tree, K-D-B tree, Quad-tree, PMR-tree, Grid-file, R-tree, and so on) have been widely discussed for handling point or region data. These traditional methods can efficiently organize point or region objects in a space into a hashing or hierarchical directory. They provide efficient access methods to meet the requirement of accurate retrievals. However, two problems are encountered when their techniques are applied to deal with line segments. The first is that representing line segments by means of point or region objects cannot exactly and properly preserve the spatial information about the proximities of line segments. The second problem is derived from the large dead space and overlapping areas in external and internal nodes of the hierarchical directory caused by the use of rectangles to enclose line objects. In this paper, we propose an indexing structure for line segments based on B ⁺ -tree to remedy these two problems. Through the experimental results, we demonstrate that our approach has significant improvement over the storage efficiency. In addition, the retrieval efficiency has also been significantly prompted as compared to the method using R-tree index scheme. These improvements derive mainly from the proposed data processing techniques and the new indexing method.     

空间数据挖掘研究综述

信息化的发展使得更多的空间数据被使用，因此获取空间知识也就越来越重要和有意义，并使得空间数据挖掘成为一个很有前途的研究领域。本文系统概括了空间分类和预测、空间聚类、空间孤立点和空间关联规则4类空间数据挖掘方法及其进展，最后探讨了空间数据挖掘的未来发展方向。