道路网络中移动对象的连续反k最近邻查询算法

在道路网络中,对象的位置和运动被约束在网络中,对象之间的距离不是传统的欧氏距离,而是由网络连通性决定的网络距离,基于欧氏空间的反k最近邻查询算法不适用于道路网络。为了解决道路网络中移动对象连续的反k最近邻查询问题,给出了道路网络的一种索引结构及一种利用扩展树处理查询的方法,在此基础上,提出了道路网络中适用与单、双色连续反k最近邻查询算法（CRkNNMA算法）,证明了该算法的正确性。     

时空数据库中基于TPR-树的反向最近邻查询

为研究动态环境下解决反向最近邻查询的算法,采用TPR-树索引结构给出了解决动态环境下的最近邻查询算法,并提出反向最近邻查询算法.该算法可有效解决平面上连续移动点的反向最近邻查询.     

移动云计算环境下的双色反近邻查询算法

研究在移动云计算环境下的最大双色反最近邻查询优化问题,设计新的高效的双色反最近邻查询算法——SILM算法.SILM算法是基于MapReduce框架下的倒排网格索引结构,在Map函数中对分片数据区域使用PCT轮圈算法.对包含在圆区域内或与圆相交的网格的权值记为1,在Reduce函数中使用网格处理算法对分片数据区域进行扫描及合并,对重叠的网格的权值进行累加,输出网格空间中权值最大的网格区域.SILM算法可以在多计算节点上进行分布式计算,更适合于在移动云计算环境下处理大规模并行查询请求.通过实验对SILM算法的效率进行验证.实验结果表明,当数据量较大(数据点个数大于2.0×10~6)时,SILM算法的查询效率是目前解决最优选址问题最佳算法的2倍.     

移动点对象轨迹上k-最近邻查询

移动点对象轨迹上k-最近邻查询是时空数据库中重要的查询之一.在时间-距离空间基础上,提出监测第k个最近邻的方法,采取了速度更新预测策略及更新预留内存的自底向上更新的R-树索引结构.当移动对象的速度或路径发生改变时,把即将更新的位置信息先存储在内存更新列表中,后更新列表已达最大预设值时才去更新R-树索引结构.此方法有效减少了磁盘的访问次数,提高了查询的效率.     

一种快速的反向k近邻查找算法及其改进

提出一种快速的反向k近邻查找算法,该方法利用现代计算机具有外存便宜、运行速度快的特点,预先计算数据之间的距离,并组织为数据索引块存储于外存,由计算机在空闲时自动进行维护.在进行反向最近邻查询时,只需读入相应的索引块,就可进行直接查询,其时间复杂度为O(N),而且不受k的影响.为减少索引块的读取时间,提出一种改进方法来有效地压缩索引块,仅用必要的二进制位来存储对象之间的距离,并将冗余减少到最低水平,提高了算法的效率.最后通过实验分析评估算法的有效性和效率.     

RPA：一种内存高效的度量空间recall@R近似最近邻搜索索引（英文）

现有的度量空间的近似最近邻搜索（approximate nearest neighbor search, ANNS）方法通常依赖于预选择的支撑点构成的序列,序列中的支撑点按照到数据元素的距离升序排列．然而,大多数现有的度量空间ANNS方法由于索引结构复杂、支撑点过多或者未能充分利用距离信息导致搜索时内存开销巨大．为此,提出精简排列阵（reduced permutation array, RPA）的度量空间recall@R近似最近邻搜索方法．对于全体数据元素,RPA预先选择k个支撑点,对每个数据元素仅存储离该数据元素最近的l个（l?k）,并将所有元素的支撑点序列构建为一个数组结构．在搜索过程中,利用一种得分函数,该函数基于查询对象到各个支撑点的距离来近似计算数据元素到查询对象的距离．同时,维护一个有界最小堆,以保存R个候选结果数据元素．RPA具有结构简单、内存效率高和可扩展性强等特点．实验结果表明,在相同召回率的情况下,与排列索引（permutation-based index, P-index）相比,RPA平均具有高达3倍的内存压缩比．研究结果可在内存资源有限的单机环境下提供一种有效的...     

基于Voronoi图的反向最近邻查询方法研究

为了解决数据集中数据点的反向最近邻问题,利用Voronoi图及空间分割区域的性质计算查询点的反向最近邻,通过Voronoi图的特性可免去每次都计算数据集中给定查询点的最近邻的步骤,每次查询可过滤出少数的几个数据点并对其进行反向最近邻的判断.给出了在数据点被加入或删除时,对查询点的反向最近邻变化情况的判断方法与算法.为了便于数据库查询,设计了相应的空间存储数据结构.比较分析表明,该方法较适用于平面及复杂曲面上的数据点的反向最近邻的查询.     

基于SR-树的空间对象反最近邻查询技术研究

反最近邻查询是空间数据库的重要应用之一,是在最近邻查询基础上提出的一种新的查询类型,以往基于范围查询或最近邻查询的方法搜索影响集效率不高,本文在分析RNN查询的基本概念和存储区域的基础上,区别于R＊-树,提出了基于SR-树的RNN查询方法,优化了空间对象的反最近查询性能,在高维空间查询上具有明显优势。     

一种基于双重距离尺度的高维索引结构

为了提高高维数据相似查询的效率,提出一种基于双重距离尺度(DDM)的新型高维索引结构.通过建模得到该DDM的四元组数据结构, 对于高维空间中的数据点,通过k平均聚类算法将数据点聚成若干类，分别计算每个点对应的始点和质心距离,得到基于加权的质心距离, 并将加权的质心距离作为每个数据点的索引键值，且用基于分片的B+树建立索引，得到了该索引的创建算法.高维空间的查询就转变成对一维空间的检索，并研究了数据点的维数、数据量和查询请求参数对查询性能的影响.结果表明, 该DDM能更有效地缩小搜索空间，减少距离计算的开销,特别适合海量高维数据的查询.     

概率可视最近邻查询算法

针对不确定对象的可视最近邻查询问题,对不确定Voronoi图的性质进行分析,提出多层邻接生成点和多层不确定Voronoi区域等概念,给出判断概率可视最近邻的理论方法,并提出基于不确定Voronoi图的概率可视最近邻查询算法,该算法通过直接确定参与查询的概率可视最近邻的范围以及参与可视性判断的障碍集的范围,避免了索引遍历时大量的比较计算和剪枝操作,采用真实数据集和模拟数据集对提出的算法进行了性能分析,实验结果表明,提出的算法能够有效地处理不确定对象的可视最近邻查询．     

空间数据库中反k最远邻查询方法

在欧式空间下反最远邻查询算法的研究已取得了很多成果,但反尼最远邻查询问题还未得到有效解决。本文提出一种反k最远邻查询算法,有效地解决了反足最远邻查询问题,查询算法采用了过滤一提炼的解决模型。在过滤阶段,提出了反远中垂线裁剪方法。该裁剪法是通过做中垂线来过滤不是查询点的反七最远邻的点。在提炼阶段,提出了反远范围尼查询提炼方法。该提炼方法是通过判断对象点是否在设定的范围外来验证该点是否是查询点的反女最远邻。最后通过实验验证了所提算法的有效性。     

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

确定对象在空间数据库研究中受到人们的重视,不确定对象的反向最近邻研究成为研究热点。文中给出不确定对象反向最近邻查询的形式化表示,将其称为可能反向最近邻查询,即为检索所有可能成为给定不确定对象的反向最近邻的可能性大于给定阈值的不确定性对象。提出基于各种剪枝规则的算法,解决多维不确定对象的可能反向最近邻查询问题。     

一种连续最近邻查询的优化方法

连续最近邻查询是空间数据库中最重要的查询之一,在地理信息系统和位置定位服务等领域有重要应用.给定一个空间数据集P和查询线段q,连续最近邻查询返回结果＜R,T＞,其中T是一个间隔,R是这个间隔中所有点的最近邻.已有的连续最近邻查询算法无法实现I/O的优化,为此,提出一种优化的连续最近邻查询方法,该方法具有较高的I/O效率,不仅在减少磁盘访问数量方面进行优化,同时也提高CPU的性能.     

交通网络中移动对象定点CRNN查询算法

目的在交通网络中实现移动对象的定点CRNN查询监控,确定受到定点影响的移动对象集合.方法根据交通网络的特征,定义网络中RNN的概念,采用PMR四叉树来索引交通网络结构,利用监控树来简化对网络上移动对象的计算判断和监控.结果测试显示该算法能够针对现实交通网络,实现定点CRNN的查询监控.结论实验表明,在移动对象和查询数量增大时,该算法显示出较好的伸缩性.     

基于改进Kd-Tree构建算法的k近邻查询

k近邻查询算法是查询大规模空间数据的常用算法之一,使用Kd-Tree先构建大规模空间数据的索引,然后对搜索空间进行层次划分,再进行k近邻查询,能保证搜索的效率。但是,传统的Kd-Tree构建有两个缺点：使用测试数据点进行k近邻查询每次都需要回溯到根节点,影响了查询的效率;Kd-Tree使用split域对空间进行层次划分,空间划分为立方体（二维数据表现为矩形）,多边形空间在相交判断时会出现没必要进行数据距离比较的多余空间,这样会影响查询的效率。针对这两个缺点,本文提出了相应的改进算法---RB算法。实验结果证明,该算法比传统的KD算法拥有更高的查询效率。本文的主要贡献有两点：（1）构建一种快速创建Kd-Tree索引来支持KNN算法进行大规模数据的分类查询操作。（2）改进传统的Kd-Tree索引构建方法,提出新的改进算法RB算法,提高KNN算法查询的效率。