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

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

ISU -Tree:一种支持概率k近邻查询的不确定高维索引

文中提出一种支持概率k近邻查询的不确定高维索引结构--ISU-Tree.在高维空间,首先对n个不确定数据对象进行k平均聚类,然后分别对每个不确定超球进行初始"切片",并对其进行多特征编码得到对应的统一化索引键值,并且用B+树建立索引.这样,高维空间的概率查询就转变成对一维空间的启发式的范围查询及求精运算.理论及实验分析表明ISU-Tree索引能更有效地缩小搜索空间,减少积分计算的代价.在查询效率方面要明显优于其它的索引方法,尤其适合海量高维不确定数据的概率查询.     

一种基于改进四叉树的GIS空间选择查询算法——以ESRI SHAPE格式文件为例

该文通过对原有四叉树在结点分裂和索引对象的结点分配方法方面进行改进,使索引对象被合理地并且不重复地分配到四叉树中的各个树结点中,减少了信息冗余,结点分布更加合理,从而提高整个索引树的搜索效率。并以ESRISHAPE格式文件为例,详细探讨了改进的四叉树在地理信息系统(GIS)的空间选择查询(包括点查询和开窗查询)中的应用与实现算法。实践表明,该算法逻辑清晰,实现简单,查询高效,具有实用价值。     

基于NNlists的路网k路径近邻查询

为满足k路径近邻查询的实时性要求,运用预计算思想提出了基于NNlists的BNNL算法,通过在用户当前位置和目的地结点进行双向Dijkstra扩展得到两点间的最短路径,再通过对最短路径上的路网结点预计算的m近邻进行优化处理,最终得到正确的k路径近邻。该方法提高了k路径近邻查询的查询速度,尤其适用于兴趣点密度较大、k值较大的情况。     

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

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

移动对象的反向k近邻查询算法的研究

传统的反向k近邻查询的研究主要集中在k=1时的单色移动对象的反向最近邻查询上,单色和双色的反向k近邻查询问题还没有解决。利用网格索引结构结合60°平面修剪策略,提出了一种解决单色和双色的移动对象的连续反向k近邻查询方法。最后实验结果验证了算法的有效性。     

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

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

DCST:主存空间高效的缓存敏感型T-树索引研究

已有主存索引通过指针消除和预取机制提升索引结构的缓存感知能力,减少缓存失效次数,但是并没有有效地利用现代计算机的CPU性能和内存空间。为了进一步提升索引结构对内存空间以及CPU性能的利用率,提出了DCST-树索引结构。该索引结构采用数据压缩的方式,对结点中的关键字进行压缩,提高索引结构对内存空间和缓存空间的利用率,减少内存访问次数,提高缓存命中率。同时,对结点进行分区,增加结点容量,提高结点扇出度,降低树的高度。实验结果表明,所提方案比现有主存索引机制具有更加高效的空间利用率和缓存感知能力,同时具有更加优秀的查询处理能力。     

基于VAR树的反向最近邻查询技术的研究

在空间数据库中,反向最近邻查询技术是最重要的查询技术之一,它是在最近邻查询技术的基础上提出的,如何有效地实现反向最近邻查询一直是人们研究的热点.以往都是基于类似R树索引结构的查询,在高维的情况下,使查询的速度急剧下降,形成"维数灾难".因此引用了一种新的索引结构--VAR树,并对VAR树进行了改进,引进了性能优越的SR树,并给出了基于这种索引结构的最近邻和反最近邻查询的算法.经实验验证基于VAR树的反向最近邻查询算法,在高维空间中的查询效率有了较大的提高.     

基于倒排表与B+树的联合索引技术

为提高XML文档的查询效率,提出一种基于倒排表与B+树的联合索引技术。DTD结构索引和内容索引采用倒排表作为索引单位,XML文档索引使用B+树作为索引基本组织。在DTD结构索引的结点编码中设置标识信息,便于确定需要查询的文档。通过建立DTD结构索引、XML文档索引和内容索引,实现混合型XML文档的查询。理论分析与实验结果表明,该技术具有较小的空间开销和较高的查询效率。     

受限网络模糊对象最近邻查询

针对网络空间中有范围约束、不确定对象的最近邻查询问题,提出范围受限的网络空间模糊对象最近邻查询概念,并根据查询顺序的不同,给出NN-R查询算法和R-NN查询算法。两种算法均采用网络位置信息与连接信息分别存储的方式,使用聚类文件进行组织,减少I/O操作。NN-R算法在近邻查询过程中利用查询对象与受限范围的α-距离作为约束,缩小搜索范围。R-NN算法将受限范围内查询对象的欧氏近邻作为候选对象,利用欧氏距离的下界性与易求性降低时间复杂度。两种算法时间复杂度分别为O((log_(m1)|E|+(|V~*|m3+1)log_(m2)|V|+|E|+|V|log|V|+n(lgn+1))和O(log_(m4)n+(k+1)log_(m1)|E|+|E|+|V|log|V|)。实验结果表明,在各自适用条件下,两种算法均有较好的性能。     

时间依赖路网中反向k近邻查询

在现存的反向k近邻查询方案中,比较高效的研究大多集中在欧氏空间或者静态路网,对时间依赖路网中的反向k近邻查询的研究相对较少。已有算法在兴趣点密度稀疏或者k值较大时,查询效率较低。对此,提出了基于子网划分的反向k近邻查询算法mTD-SubG。首先,将整个路网划分为大小相同的子网,通过子网的边界节点向其他子网进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后, 利用已有时间依赖路网下的近邻查询算法,判定查找到的兴趣点是否为反向k近邻结果。实验中将mTD-SubG算法与已有算法mTD-Eager进行对比,结果表明mTD-SubG算法的响应时间比mTD-Eager算法减少了85.05%,遍历节点个数比mTD-Eager算法减少了51.40%。     

一种时间序列相似匹配新算法

为提高时间序列相似匹配的精度和效率，提出一种基于小波包变换的时间序列相似匹配算法．首先利用小波包可对信号进行精细分析的特点，对时间序列进行维数约简，用变换后的低频系数和部分高频均值系数作为特征向量表示原始序列；然后用多维索引结构R树存储这些特征向量，将欧几里德距离作为相似尺度，在此基础上实现了范围查询和k近邻查询，对电力负荷时间序列数据的仿真实验结果表明了算法的有效性。     

路网上的单色和双色反k最远邻查询

传统的路网上的反最远邻查询是直接找出查询点的反最远邻,这种方法不但效率不高,而且需要大量内存资源进行预计算。为了更有效地解决基于路网的单色和双色反k最远邻查询问题,提高反k最远邻查询的效率,提出了从反最近邻的角度来分析反最远邻查询问题,把反最远邻查询转化为反最近邻问题。根据这一理论,提出了一种有效的基于路网的单色和双色的反k最远邻查询算法。通过实验与实验分析表明,该方法具有良好的实用价值。     

K-nearest neighbor finding using MaxNearestDist

Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These algorithms are generally applicable to any index based on hierarchical clustering. The idea is that the data is partitioned into clusters which are aggregated to form other clusters, with the total aggregation being represented as a tree. These algorithms have traditionally used a lower bound corresponding to the minimum distance at which a nearest neighbor can be found (termed MinDist) to prune the search process by avoiding the processing of some of the clusters as well as individual objects when they can be shown to be farther from the query object q than all of the current k nearest neighbors of q. An alternative pruning technique that uses an upper bound corresponding to the maximum possible distance at which a nearest neighbor is guaranteed to be found (termed MaxNearestDist) is described. The MaxNearestDist upper bound is adapted to enable its use for finding the k nearest neighbors instead of just the nearest neighbor (i.e., k=1) as in its previous uses. Both the depth-first and best-first k-nearest neighbor algorithms are modified to use MaxNearestDist, which is shown to enhance both algorithms by overcoming their shortcomings. In particular, for the depth-first algorithm, the number of clusters in the search hierarchy that must be examined is not increased thereby potentially lowering its execution time, while for the best-first algorithm, the number of clusters in the search hierarchy that must be retained in the priority queue used to control the ordering of processing of the clusters is also not increased, thereby potentially lowering its storage requirements.     

使用R树进行k-NN搜索

在地理信息系统中经常要做k-NN搜索，进行这些查询用到的算法与位置和范围查询的算法不同，需要专门进行研究，介绍了一种分支界限遍历R树算法，并将该算法概括为k-NN算法。文中讨论了两种方法。对R树进行结点内MBR的排序以及剪枝过程，以减少搜索空间中需访问结点的数量，有效地进行k-NN搜索。     

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

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

不确定性对象的反向最近邻查询

多数不确定性对象的反向近邻查询不能明确回答某个不确定性对象是否为查询对象的反向最近邻,针对该问题,提出概率反向最近邻查询的概念,设计不确定性对象的概率反向最近邻查询的索引结构,给出一种基于该结构的不确定性对象的反向最近邻查询算法。     

基于抗体选择策略的克隆挖掘算法

针对如何有效地利用大量的原始数据分析现状来预测未来的问题,基于抗体选择策略提出一种克隆选择挖掘算法。通过评估抗体的支持度、可信度和亲和度,求得有效的关联规则。实验结果表明,该算法能较快地获得可理解的规则,并且具有较高的准确率。     

基于网格查询的局部离群点检测算法

针对基于密度的局部离群因子算法（LOF），需要计算距离矩阵来进行[k]近邻查寻，算法时间复杂度高，不适合大规模数据集检测的问题，提出基于网格查询的局部离群点检测算法。算法利用距离目标网格中的数据点最近的[k]个其他数据点，一定在该目标网格或在该目标网格的最近邻接网格中这一特性，来改进LOF算法的邻域查询操作，以此减少LOF算法在邻域查询时的计算量。实验结果证明，提出的LOGD算法在与原LOF算法具有基本相同的检测准确率的情况下，能够有效地降低离群点检测的时间。