平面线段集最近邻查询算法

针对基于R-树的空间索引结构存在的节点覆盖冗余,兄弟节点之间的交叠问题,提出一种新的空间索引结构即RP-树。通过最适合划分函数和数据矩形的有序关系来对空间数据进行划分,使得该树的高度尽可能低,节点交叠较小。以RP-树为平面线段集的索引结构,利用线段集的相关定理和筛选规则,给出了一个求解平线段集最近邻的新查询算法,该算法不仅易于理解,且执行效率较高。     

基于QCR-树的空间索引方法

QR-树处理海量空间数据时,其深度和R-树内目录矩形的重叠面积会变大,导致查询效率降低。针对该问题采用K-means算法对索引对象进行聚类分析,构造新的聚类中心使其能处理具有多种形体的索引对象,并在QR-树中引入超结点存储聚类结果。提出一种QCR-树空间索引结构来提高查询效率,给出QCR-树的插入、删除和查询算法。实验结果表明QCR-树的查询性能优于QR-树,适用于海量数据。     

MapReduce框架下基于R-树的k-近邻连接算法

针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理。首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了 R-树索引快速构建算法和基于 R-树的并行 k-近邻连接算法。在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达。在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用 R-树索引进行 k-近邻连接查询,提高了查询效率。从理论上分析了所提出算法的通信和计算代价。实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值。     

基于聚类的Hilbert R-树空间索引算法

R-树适合于动态索引,但空间重叠大,而Hilbert R-树也不能有效降低节点覆盖和交叠,直接影响R-树的查询效率。为适应大量的GIS查询应用需要,提出对Hilbert R-树节点进行聚类的索引算法,较好地解决相邻数据的聚类存放,使叶节点MBR面积减小,内部节点交叠降低,并对该算法进行实验测试和性能分析,结果表明该算法具有较高的查询效率。     

数据分发管理匹配算法的R-树实现

数据分发管理（DDM）是高层体系结构（HLA）接口规范的6类服务之一,高效的区域匹配算法是DDM研究的重点和难点．当前的多种匹配算法往往只适用于特定的应用环境,且效率不够理想．R-树法是在空间索引技术的基础上提出的一种新的匹配算法,该方法用R-树对DDM区域的矩形进行组织,并利用Hash索引对其叶结点的组织方式进行了改进．实验结果表明R树法可有效减少动态DDM的维护开销,提高分布交互仿真的实时性,通过调整R-树的相关参数,可以进一步改善匹配算法的性能．     

动态确定K值聚类算法的R-树空间索引构建

目前采用的R-树空间聚类技术使用指定k值的聚类算法,初始聚类中心随机或指定选取。这样聚类的结果受初始k值影响,且易受离群空间数据的干扰。为解决上述问题,根据空间数据分布的特点,提出了动态确定k值的空间聚类算法(dynamical k-value spatial clustering algorithm,DKSC)。该算法通过聚类划分空间数据,把同一子空间的数据组织在同一个子树下,从根节点到叶子节点逐层构建R-树,形成高效的R-树空间索引。分别用真实和模拟的空间数据集进行了实验,结果表明该算法优化了构建的R-树空间索引,且具有更高效的查找效率。     

基于结点分裂优化的R-树索引结构

针对R-树索引空间查询效率低下的问题,提出一种基于结点分裂优化的R-树索引结构：SR-树索引。SR-树索引在结点分裂过程中,通过增加叶子结点的空间数据聚集性来减少叶子结点最小外接矩形的覆盖面积。为了有效降低磁盘读写消耗,SR-树结点在写入索引时,首先将索引树在内存中建好,然后在文件中写入树信息,最后通过递归的方式写入结点。实验结果表明,与R-树索引相比,SR-树索引可以在减少最小外接矩形重叠面积的同时,有效降低查询响应时间,从而达到提高查询效率的目的。     

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

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

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

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

MSCR树：一种移动终端电子地图索引结构

现有空间数据索引结构并未同时考虑移动终端电子地图的多比例尺特性及嵌入式设备性能的限制,造成对大区域进行空间查询操作时装载开销过大。深入分析了多种空间索引结构的特点,提出一种新的空间索引结构——MSCR树索引结构,该结构将多级地图中的空间元素线性化,同时以压缩的方式存储空间元素外包矩形数据以提高数据读写效率。实验表明,MSCR树算法有效地提高了查询性能与空间利用率。     

基于空间填充曲线网格划分的最近邻查询算法

在建树过程中,R树存在最小边界矩形之间重叠的现象。当数据量较大时,重叠现象尤为严重,基于R树最近邻查询算法的性能急剧恶化。针对该问题,利用空间填充曲线的降低维度特性和数据聚类特性,提出一种基于网格划分最近邻查询算法。该算法将整个数据空间划分成大小相等、互不重叠的网格,对网格中的点进行线性排序之后,只需要访问查询点所在网格中的点及其周边邻近网格中的点,就能够获得最近邻。在Hilbert曲线、Z曲线和Gray曲线上实现3种最近邻查询算法,在映射算法和数据聚类特性上实验比较3种曲线之间的性能差异。实验结果表明,算法的查询性能明显优于顺序扫描算法和基于R树的最近邻查询算法。     

A new double sorting-based node splitting algorithm for R-tree

A storing of spatial data and processing of spatial queries are important tasks for modern data-bases. The execution efficiency of spatial query depends on underlying index structure. R-tree is a well-known spatial index structure. Currently there exist various versions of R-tree, and one of the most common variations between them is node splitting algorithm. The problem of node splitting in one-dimensional R-tree may seem to be too trivial to be considered separately. One-dimensional intervals can be split on the base of their sorting. Some of the node splitting algorithms for R-tree with two or more dimensions comprise one-dimensional split as their part. However, under detailed consideration, existing algorithms for one-dimensional split do not perform ideally in some complicated cases. This paper introduces a novel one-dimensional node splitting algorithm based on two sortings that can handle such complicated cases better. Also this paper introduces node splitting algorithm for R-tree with two or more dimensions that is based on the one-dimensional algorithm mentioned above. The tests show significantly better behavior of the proposed algorithms in the case of highly overlapping data.     

R-树结点分配的新算法

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

基于R树的协同过滤推荐算法

R树是一个高度平衡树,也是目前应用最为广泛的空间索引结构.本文以用户行为的历史数据之间的相似度构造R树,提出一种基于R树的协同过滤推荐算法（R_CF）;另外,从用户的隐式反馈着手,构建用户兴趣行为数据模型,并进行数据标准化处理.仿真实验表明:较之传统的协同过滤推荐算法（CF）,本文提出的R_CF算法可以极大提升推荐top-n个相似度最高的用户时的查询速度.     

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

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

Efficient algorithms for spatial configuration information retrieval

The problem of spatial configuration information retrieval is a constraint satisfaction problem (CSP), which can be solved using traditional CSP algorithms. But the spatial data can be reorganized using index techniques like R-tree and the spatial data are approximated by their minimum bounding rectangles (MBRs), so the spatial configuration information retrieval is actually based on the MBRs and some special techniques can be studied. This paper studies the mapping relationships among the spatial relations for real spatial objects, the corresponding spatial relations for their MBRs and the corresponding spatial relations between the intermediate nodes and the MBRs in R-tree. Three algorithms are designed and studied, and their performances are compared.     

3DGIS中混合空间索引技术的研究

针对单一的3D空间索引技术检索性能较差的问题,分析了八叉树和经典R树的优缺点,提出了一种将两者结合的混合索引技术——ORSI,给出了ORSI的原理和结构描述,介绍了ORSI的操作算法。ORSI与经典R树的操作性能测试结果表明,ORSI的整体操作效率优于经典R树。