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

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

GRkNN:空间数据库中组反k最近邻查询

反k最近邻(Reversek-Nearest-Neighbor,RkNN)查询是在k最近邻(k-Nearest-Neighbor,kNN)查询问题的基础上产生的,获得将查询对象作为kNN的数据对象集合,RkNN可以用于评价查询对象的影响力.根据实际应用中需要查询一组对象的RkNN,如评价连锁店或商业区的影响.文中提出了针对空间数据库的组反k最近邻(Group RkNN,GRkNN)的概念,并设计了相关算法.查询点集合是一组邻近的空间对象,计算查询对象的最小覆盖圆,将最小覆盖圆中的对象作为一个整体进行过滤,设计了基于R树的剪枝方法,通过提炼获取了最终的GRkNN结果.针对真实数据集进行的大量实验表明,提出的GRkNN算法的效率明显优于目前最好的RkNN算法.

一种障碍空间中的反k最近邻查询方法

随着基于位置的服务(LBS)和物联网的快速发展,空间查询技术越来越重要,而空间查询中的最近邻查询及其各种变体有着广泛的应用.近几年,已有较多对于查询前k个反最近邻对象(RkNN)的研究,其中大部分针对的都是理想欧氏空间.而在真实的情况下,反k最近邻查询通常受障碍物影响.文中研究了障碍空间中反k最近邻查询算法,提出了一种基于障碍Voronoi图的高效的剪枝方法.根据Voronoi图和障碍距离的特性,大幅度减少了数据点处理个数.最后,作者使用真实的数据集和多种方式分布的模拟数据,验证了算法的高效性和准确性.

障碍空间中基于Voronoi图的组反k最近邻查询研究

为了解决已有研究成果无法有效处理障碍空间中的组反k最近邻查询问题,提出了障碍物环境中基于Voronoi图的OGRkNN查询方法,该方法获得的结果集是将一组查询点中任意一点作为障碍kNN的数据点集合,在实际应用中可以用来评估一组查询对象的影响力.依据障碍物集合是否发生变化提出了2种情况下的OGRkNN查询方法,一种是静态障碍物环境下的OGRkNN查询(简称STA_OGRkNN查询)方法,另一种是动态障碍物环境下的OGRkNN查询(简称DYN_OGRkNN查询)方法.其中STA_OGRkNN查询方法利用Voronoi图的邻接特性可以在剪枝阶段有效地过滤掉大量的非候选者,快速地缩小查询范围,提高整个算法的查询效率,在精炼阶段有效地提高了算法的准确性.进一步给出了3种情况下的DYN_OGRkNN查询方法,分别为障碍物动态增加情况下的OGRkNN查询算法、障碍物动态减少情况下的OGRkNN查询算法以及障碍物动态移动情况下的OGRkNN查询算法.理论研究和实验结果表明所提算法具有较高效率.

空间对象的反最近邻查询

本文在对现有反最近邻查询方法研究的基础上,提出了一种新的索引结构—SRdnn-树;在此基础上提出了基于SRdnn-树的反最近邻查询方法,并给出了该结构上的最近邻查询方法,以及插入和删除方法,第5节实验表明,基于SRdnn-树的反最近邻查询在性能上优于以往查询方法。

空间数据库中基于Voronoi图的线段反k最近邻查询

为了解决已有研究成果无法有效处理空间数据库中基于线段的反k最近邻查询问题,提出基于Voronoi图的线段反k最近邻查询方法(LRk NN方法).该方法获得的结果集是将查询线段作为k NN的线段集合,在实际应用中可以用来评估一个查询对象的影响力.LRk NN查询方法分为三个过程:初步剪枝、深度剪枝、精炼过程.在剪枝阶段利用Voronoi图的邻接特性可以有效地过滤掉大量的非候选者,快速地缩小查询范围,提高了整个算法的查询效率.在精炼阶段又利用定义排除不满足查询条件的对象,有效地提高了算法的准确性.理论研究和实验结果表明所提算法具有较高效率.

多维空间的反最近邻查询算法研究与实现

在空间数据库中,空间查询技术已经成为研究的热点。相关领域专家在最近邻查询问题的基础上提出了一个新的空间查询概念反最近邻查询。随着数据形式的不断发展,二维空间中的数据查询已经不能满足数据查询的需求,空间数据查询趋向多维化。论文将就在多维空间中的反最近邻查询技术进行研究,使用一个过滤和提纯的两步算法框架设计并实现多维空间上的反最近邻查询算法。

基于新型索引结构的反最近邻查询

为了提高反最近邻问题的查询效率,首先给出了空间数据的最小包围正方形定义和空间数据矩形的4种序的定义.依据这些定义,提出了一种新的空间数据索引结构——基于最小包围正方形和最近邻距离的索引树(index tree based on the minimum bounding square and the distance of nearest neighbor,MBDNN-tree),该索引结构运用了R-树中分割空间数据的思想,将数据点用其基于最近邻距离的最小包围正方形表示,记为MBSD(minimum bounding square based on nearest neighbor distance),利用多种序关系对原始点集进行划分,从上至下、从左至右地按照结点几何分布以及对应的序关系构造树的各层结点.对建立MBDNN-树所需要的预处理过程以及构造过程的算法进行了详细描述和证明分析,给出了MBDNN-树的性质.在此基础上,给出了MBDNN-树进行反最近邻查询的剪枝规则,进而给出了MBDNN-树进行反最近邻查询的算法及其算法分析.反最近邻查询算法利用了MBDNN-树中同层结点之间的几何有序性,有效地减少了结点的访问数量,从而提高了查询效率.最后对基于此结构的反最近邻查询算法进行实验分析.实验表明:基于MBDNN-树的反最近邻查询算法的查询性能有较大的提高.

空间对象的反最近邻查询处理技术研究

空间数据库中反最近邻查询的研究是空间查询的研究热点。在对现有的反最近邻查询技术进行分析比较的基础上,针对提高动态数据集的查询效率问题,给出了基于R树索引结构的反最近邻查询方案。通过实验结果的分析比较,可以看出该方案能够有效地解决动态数据集的查询问题。

不确定移动对象的查询处理技术研究综述

由于数据采集设备不精确,移动对象延迟更新和隐私保护等原因,移动对象的不确定性普遍存在。在传统数据库中增加概率维,使得对象表达、查询定义、查询处理以及最终结果的呈现,都与传统方法不同,基于确定数据的移动对象查询处理技术无法进行有效处理。因此,基于不确定对象的查询处理技术受到越来越多的关注,成为当前数据库领域的研究热点问题之一。讨论了不确定对象查询面临的挑战;从查询定义、剪枝策略和算法等角度,分别对基于不确定移动对象的范围查询、最近邻查询、反最近邻查询和轨迹查询的研究现状进行了详细的介绍和对比;探讨了今后的研究重点和发展趋势。

基于范围查询的移动对象快照KNN查询算法

提出一种基于范围查询的移动对象快照K最近邻(KNN)查询算法——SKNN。预估包含结果集的子空间,使用该子空间作为范围,计算查询点的KNN兴趣点,以降低I/O成本。引入移动数据库中的缓存技术,缩短查询的平均响应时间。实验结果表明,当移动对象的规模较大时,SKNN算法的性能较优。

二维空间中基于约束关系的RNN查询算法

反最近邻(RNN)查询问题是空间数据库中的研究热点问题,但传统算法主要集中在对整个数据集的查询。该文把约束关系的概念引入到了RNN查询中,给出在约束关系下如何利用索引结构进行查询的方法,并根据NN查询和RNN查询问题的内在联系给出相应求解CRNN问题的算法。实验表明该算法比传统算法更能提高查询效率。