多维空间索引结构SHG-Tree(英文)

R-Tree及其变种的多维索引结构在数据的操作过程中通过对空间的分隔和不断调整将整个空间划分为大小不等的子空间以容纳足够的空间对象,这种方法能有效地实现多维空间对象的索引,但不能避免频繁的节点分裂与重组操作所造成的计算开销,也不能避免对叶子节点中的候选对象进行空间匹配所带来的计算开销。提出了一种能有效解决上述问题的索引结构:SHG-Tree。基于SHG-Tree的索引方法将多维空间划分为不同粒度的格子单元并将这些格子单元通过SHG-Tree按空间包含关系组织为层次树结构,同一层的格子互不相交且空间范围固定。空间对象通过文中提出的线性化方法转换为一系列不同粒度的互不相交的空间格子,进而将对象在其覆盖的格子中注册以实现空间对象至SHG-Tree的映射。查询操作只需将查询条件映射为相应的格子并取出这些格子中的对象作为查询结果。这种索引结构能有效减少节点的分裂和组合带来的计算开销,也解决了传统R-Tree索引中对于叶子节点中的候选对象进行区域匹配的计算开销。基于SHG-Tree的索引结构支持包括相交查询、区域查询、包含查询、top-N查询、k-NN查询等常用的多维查询,实验表明SHG-Tree能在毫秒级实现各种空间查询。     

用代数格实现点数据索引

提出用代数格实现多维点数据索引的一般方法,在该方法中,首先用格矢量量化器对点数据进行量化,然后用倒排文件和散列表存储和索引量化后的点数据,以便利用格良好的代数和几何性质实现快速检索,最后给出了基于Ｅ８格的八维点数据索引性能的计算机模拟结果。     

支持线段查询索引结构CB树

在空间数据库中点、线段和区域是构成向量对象的三种基本实体。现有的索引结构能够将点或区域对象有效地组织成散列或分层目录,并且提供精确的检索方法。然而,这些索引结构索引线段时会出现以下问题。索引结构不能准确地表示线段的空间信息,这将阻碍对线段空间数据的高质量存储。位于层次目录中节点之间将产生大量死空间和重叠区域,随着时间的推移这将降低系统性能。提出一种采用数据压缩的索引结构CB树。与R树索引结构相比,CB树具有较优查询效率,占用较少存储空间。     

空间索引技术研究

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

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

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

一种基于CHORD系统的多维相似查询处理方法

如何在对等计算环境下处理多维空间中的相似查询是目前学术界的研究热点之一。本文通过基于代表点的多维空间划分策略,提出了一种对等计算环境下的分布式多维索引技术,实现了一种基于CHORD系统的多维相似查询处理。仿真实验证明了本文提出的方法的有效性。     

3D GIS中线性八叉树空间索引的建立与查询算法研究

三维地理信息系统空间数据库具有数据量大、空间实体关系复杂、空间操作计算量大等特点。为了提高检索效率,必须建立高效的空间索引机制。八叉树空间索引是对二维GIS中四叉树索引进行扩展的一种三维空间数据结构,具有思路简单、容易理解和实现、查询速度快的优点。本文首先阐述了线性八叉树空间索引的原理,然后重点介绍了线性八叉树空间索引的建立和查询算法。     

分布式WebGIS构件化研究

对Internet/WWW计算环境下WebGIS系统的构件化进行理论和实践的探索，基于COM／DCOM建立一个实用的WebGIS对象构件系统Ceo-Unio。从地理空间数据模型，体系结构，构件层次和构件功能划分等方面对构件化的WebGIS进行阐述，并通过采用空间索引和空间缓存等技术，为地理空间数据的检索和传输效率等问题提供了一种有效的解决方案，所实现的系统已经在多个领域得到良好的应用。     

基于内容的中文文本检索方法

随着信息量的急剧增加,检索技术显得尤为关键.目前很多检索技术都是基于索引的检索技术.文中借助了Lucene的索引技术与检索机制,通过对索引信息的改进以及使用基于内容的改进方法,对Lucene结果与查询语句在向量空间中重新计算相似度,实现了对长段查询语句检索结果排序位置的提高.     

面向海量水利数据的索引方法研究

水利数据的存储形式多样、数据量庞大以及水利实体种类丰富,针对每一类水利实体对象,不仅存在基础描述信息,也存在一系列测量业务信息,这2类数据存储和更新频率不相同。水利业务检索不仅要求能实现对象基础信息的快速检索,还要求根据基础描述信息和业务信息之间的依赖进行组合查询,而目前云环境中,尚缺能满足此类兼顾多类型数据之间依赖关系的高效索引方法。此外,水利数据量的急剧增长,给系统检索性能带来了巨大的挑战。为此,本文提出基于Hadoop的分布式双层索引结构HRB,针对不同的数据类型建立不同的索引。经实验验证,HRB索引与常规分布式索引相比,索引创建效率更优,且在数据量达到千万级别时,HRB检索速度更快,表明HRB具有一定的使用价值。     

WebGIS中多维空间数据多尺度表达索引结构*

针对现有数据结构无法支持WebGIS中多维空间数据的多尺度表达,提出了一种改进的数据结构：a)主树由金字塔层级结构规则分割的区域四叉树索引结构变形而来;b)具有支持多维数据的重叠子树结构;c)利用树的深度反映空间分辨率的变化;d)主树的所有节点均为空间对象载体,子树的节点为多维数据单元。分析了该索引产生的必要性,对该索引结构进行描述,并着重对该索引结构中的数据生成算法、多维数据支持和搜索过程进行了讨论。针对相同数据源,使用本结构与图层表达法进行对比实验,结果表明,该索引方法能对WebGIS中海量多维空间数     

Hierarchical structure to winged-edge structure: a conversion algorithm

The winged-edge data structure is advantageous for traversing the topological graph of the boundary representation of a solid object. This paper presents an algorithm for converting hierarchical boundary representations into representations in the winged-edge data structure. As a result of the conversion, the adjacency relationships of geometric entities embedded in hierarchical boundary representations,-which may be evaluated through boundary evaluation on solid objects defined via Boolean set-operations, can be easily and efficiently accessed.     

时空相点移动对象数据索引PM-Tree

随着移动定位技术和无线通讯技术发展,移动对象的应用领域越来越广阔.位置随时间而变化的移动对象产生的时空数据具有规模大、多维性、结构复杂和关系复杂等特点.由于移动对象的运动轨迹大多被限定在特定的交通网络中,因此基于路网的移动对象索引成为时空数据索引研究的一个重要应用分支.目前,针对移动对象历史数据的区域查询优化的研究重点...     

Novel Techniques for Robust Voxelization and Visualization of Implicit Surfaces

Voxelization is the transformation of geometric surfaces into voxels. Up to date this process has been done essentially using incremental algorithms. Incremental algorithms have the reputation of being efficient but they lack an important property: robustness. The voxelized representation should envelop its continuous model. However, without robust methods this cannot be guaranteed. This article describes novel techniques of robust voxelization and visualization of implicit surfaces. First of all our recursive subdivision voxelization algorithm is reviewed. This algorithm was initially inspired by Duff's image space subdivision method. Then, we explain the algorithm to voxelize implicit surfaces defined in spherical or cylindrical coordinates. Next, we show a new technique to produce infinite replications of implicit objects and their voxelization method. Afterward, we comment on the parallelization of our voxelization procedure. Finally we present our voxel visualization algorithm based on point display. Our voxelization algorithms can be used with any data structure, thanks to the fact that a voxel is only stored once the last subdivision level is reached. We emphasize the use of the octree, though, because it is a convenient way to store the discrete model hierarchically. In a hierarchy the discrete model refinement is simple and possible from any previous voxelized scene thanks to the fact that the voxelization algorithms are robust.     

空间数据库中的一种混合索引结构的研究

空间索引是实现空间查询的关键技术,其性能的好坏直接决定着空间数据的存储效率及空间查询的性能。为了提高空间查询效率,提出一种混合空间索引结构松散QR-树：LQR-tree。针对已有的QR-树索引结构在节点分配中,可能存在较小的对象落入较大的节点中的问题,将松散四叉树和R-树相结合,能够实现节点下移,优化处理移动空间对象的查询,给出LQR-tree的结构和插入删除算法,并提出对应算法的相关定理和证明。     

A new approach for the voxelization of volumetric CSG graphs

This paper presents a new approach for the voxelization of volumetric scene graphs. The algorithm generates slices of each primitive intended to be voxelized using an FPGA based pixel processor. The Blist representation is used for the volume scene tree which reduces storage requirement for each voxel to the log(H+1) bits. The most important advantage of this voxelization algorithm is that any volume scene tree expression can be evaluated without using any computation or stack. Also the algorithm is not object specific, i.e. the same algorithm can be used for the voxelization of different types of objects (convex and concave objects, polygons, lines and surfaces).     

RTC树的构建与不确定近邻关系查询方法

空间索引结构和查询技术在空间数据库中具有重要的作用,针对已有的方法在复杂空间数据对象的近似和组织方面的局限性,提出了一种基于最小外接矩形(MBR)、梯形和圆的新的索引结构(RTC树).为了有效处理复杂空间数据对象的最近邻(NN)关系查询问题,提出了基于RTC树的最近邻查询(NNRTC)算法,NNRTC算法利用剪枝规则可减少节点遍历和距离计算.针对障碍物对数据集中最近邻的影响问题,提出了障碍物环境下的基于RTC树的最近邻查询(BNNRTC)算法,BNNRTC算法先在理想空间进行查询,再对查询结果进行判断.为了有效处理动态单纯型连续近邻链查询问题,进一步给出了基于RTC树的动态单纯型连续近邻链查询(SCNNCRTC)算法.实验结果表明,相对基于R树的查询方法,所提的方法在处理数据量较大的复杂空间对象的数据集时可提高60%~80%的效率.     

基于聚类的空间数据多比例尺索引树

针对现有空间对象多尺度索引结构聚簇性不高的问题,在R树索引的基础上提出一种基于聚类的空间数据多比例尺索引结构。利用树的层次结构反映空间数据的多比例尺特性,用k-means算法对相同等级的空间对象进行聚类分组,减少空间区域覆盖和重叠。实验结果表明,该方法与基于四叉树的多比例尺索引相比,能有效提高空间数据多比例尺显示的性能。     

一种极小化覆盖的空间索引结构——MCSI-树

以缩小各层节点覆盖为目标,运用数据空间分割技术,结合二叉树和R-树思想,提出一种空间数据索引结构——MCSI-树。在该结构中,空间数据之间的拓扑关系得到记载,各层节点的覆盖明显减少,查询区域减小,使区域查询速度得到提高。给出MCSI-树的建立算法及算法的正确性、可终止性证明及时间复杂度,并给出节点插入算法。     

利用覆盖区域设计与实现移动对象索引

对移动对象索引频繁更新问题进行了研究,提出了一种基于区域覆盖的空间索引结构虚拟网格四分树(virtual grid quadtree,VGQ);通过索引移动对象所在的区域而非移动对象本身来减少由于移动对象位置的改变而引起的索引结构的改变,并给出了近似连续范围查询算法及增量和自底向上优化策略。实验结果表明,VGQ在查询效率和空间使用上是一种有效的索引方法。