基于查询集空间分布的聚合最近邻查询算法

聚合最近邻查询涉及到多个查询对象,因此比传统最近邻查询更复杂,而且其查询集空间分布特征暗含了查询集聚合最近邻的区域分布信息。充分考虑查询集分布特征,给出了利用分布特征指导聚合最近邻搜索的方法,并以此提出了一种新的聚合最近邻查询算法——AM算法。AM算法能动态地捕捉并利用查询集空间分布特征,使得对数据点的搜索按正确的次序进行,避免对不必要数据点的搜索。最后通过实验验证了AM算法的高效性。     

基于Voronoi图的组最近邻查询

组最近邻查询由于涉及多个查询点,因此比传统的最近邻查询更为复杂.充分考虑查询点的分布特征以及它们构成的几何图形的性质和特点,给出组最近邻所应满足的条件及判断组最近邻的理论方法.提出基于Voronoi图的组最近邻查询的VGNN算法,可以精确求解查询点集的最近邻.对于查询点不共线的情况,该算法的查询方式是以一点为中心、向外扩张式的;对于查询点共线的情况,该算法给出搜索范围,限定了参与计算的数据点的个数.给出基于Voronoi图的VTree索引.实验结果表明,基于VTree索引的VGNN算法具有较好的性能,并且当查询点不共线时,其性能具有较高的稳定性.     

基于闭区域和开区域修剪的MTRNN过滤算法研究

传统的多类型反向最近邻(multiple type reverse nearest neighbor, MTRNN)查询算法没有过滤搜索空间中的数据, 因此效率低下。为有效提高MTRNN查询的效率, 在概述MTRNN基础上采用几何方法开发了基于R-tree的闭区域和开区域修剪方法并进一步提出了高效的过滤算法。过滤算法通过构造闭修剪区域和开修剪区域来修剪查询空间, 对大数据下的MTRNN查询过滤效果十分显著。最后通过实验验证了算法的有效性。     

不确定数据上范围受限的最近邻查询算法

不确定数据的查询处理是数据库领域近年来的热点研究课题.提出一种不确定数据上的范围受限的最近邻查询.给定不确定数据集D={o1,o2,…,on},范围约束R是一个简单多边形,q为一固定的查询点,范围受限的最近邻查询返回的是在数据集D中,既满足范围约束R,又能成为查询点q的最近邻的对象集合.为处理该查询,提出了范围受限的最近邻核心集的概念和范围受限的最近邻核心集的查找算法.并提出一种计算范围受限的最近邻候选集的优化方法,降低了查询代价.最后通过实验验证了该算法的有效性.     

道路网络中的多类型K最近邻查询

空间数据库的多类型最近邻查询逐渐受到人们的关注,关于K最近邻查询的研究也较多,但多类型K最近邻查询的研究还存在空白。针对道路网络中的多类型K-最近邻（MT-KNN）问题,结合多类型最近邻查询及K最近邻查询的理论,提出了多类型K最近邻查询算法。通过对分层编码视图进行扩展,建立了多路径分层编码视图,并利用逐步扩展局部路径的方法,实现了多类型K最近邻查询,实验结果分析表明算法具有较好的性能。     

室内概率阈值反向最近邻查询

室内空间变得越发的庞大和复杂,随之产生了越来越多的室内空间查询需求.目前已有文献提出了针对室内空间环境的范围查询和最近邻查询,而作为常见的空间查询类型的反向最近邻查询,尚未有相关的研究.为此,提出了室内概率阈值反向最近邻查询和基于定位设备的设备可达图模型.在图模型基础上,提出了室内概率阈值反向最近邻查询处理算法,该算法由基于图模型的批量剪枝、基于室内距离的剪枝、基于概率的剪枝和概率计算4部分构成,通过剪枝策略修剪掉不可能出现在结果集中的对象,从而缩小了查询空间,提高了效率.     

基于Voronoi图的最近邻查询的研究

移动查询点的最近邻查询是移动计算和现实生活应用中一种很基本也很重要的查询类型.基于Voronoi图的最近邻查询在计算几何中已被研究了相当长一段时间.但在以往的研究中基于Voronoi图的最近邻查询究竟是基于何种具体的索引结构去实现对查询空间的搜索的,却很少被提及.本文把传统的R树和Voronoi图在解决最近邻查询问题中的优越性相结合,提出了一种新的索引结构:VR树.进而给出了基于VR树索引结构的1NN查询算法.     

面向存在不确定对象的组最近邻查询方法

组最近邻查询是空间对象查询领域的一类重要查询,通过该查询可找到距离给定查询点集最近的空间对象.由于图像分辨率或解析度的限制等因素,空间对象的存在不确定性广泛存在于某些涉及图像处理的查询应用中.这些对象位置数据的存在不确定性会对组最近邻查询结果产生影响.本文给出面向存在不确定对象的概率阈值组最近邻查询定义,设计了高效的查询处理机制,通过剪枝优化等手段提高概率阈值组最近邻查询效率,并进一步提出了高效概率阈值组最近邻查询算法.采用多个真实数据集对概率阈值组最近邻算法进行了实验验证,结果表明所提算法具有良好的查询效率.     

改进的全局最近邻查询算法及其在空间数据库中的应用

针对基础数据集合和参考数据集合为相同数据集的情况,给出了一种新型的空间数据库全局最近邻查询算法,该算法能够利用数据最近邻结果的自身特点,避免较大的查询过程中的资源开销.实验结果表明,算法的效率要明显优于常用最近邻查询算法,并且对于不同的数据维数和数据元素数量,特别是对于高维的空间数据集合,算法具有较高的稳定性.     

一种障碍空间中不确定对象的连续最近邻查询方法

近年来,基于位置的服务获得了越来越广泛的关注,其中最近邻查询是最常用的一种查询方式.测量手段的不准确性以及数据本身的性质导致不确定性在位置数据中普遍存在,这种不确定性会对最近邻查询结果产生影响.空间中障碍物的存在也给空间数据查询带来了挑战.文中研究存在障碍物的空间中不确定对象连续最近邻查询的处理方法,设计了一种剪枝策略大幅降低需要计算的不确定对象数目,并进一步提出了障碍空间中不确定对象最近邻查询安全区域的概念及安全区域生成算法.设计了安全区域的索引存储方法.实验结果表明,文章所提出的方法具有良好的效率和可扩展性.     

Nearest Neighbor Queries in Shared-Nothing Environments

In this paper, we propose an efficient solution to the problem of nearest neighbor query processing in declustered spatial databases. Recently a branch-and-bound nearest neighbor finding (BB-NNF) algorithm has been designed to process nearest neighbor queries in R-trees. However, this algorithm is strictly serial (branch-and-bound oriented) and its performance degrades, during processing of a nearest neighbor query, if applied to a parallel environment, since it does not exploit any kind of parallelization. We develop an efficient query processing strategy for parallel nearest neighbor finding (P-NNF), assuming a shared nothing multi-processor architecture, where the processors communicate via a network. In our method, the relevant sites are activated simultaneously. In order to achieve this goal, statistical information is used. The efficiency measure is the response time of a given query. Experimental results, based on real-life and synthetic datasets, show that the proposed method outperforms the branch-and-bound method by factors.     

Range nearest-neighbor query

A range nearest-neighbor (RNN) query retrieves the nearest neighbor (NN) for every point in a range. It is a natural generalization of point and continuous nearest-neighbor queries and has many applications. In this paper, we consider the ranges as (hyper)rectangles and propose efficient in-memory processing and secondary memory pruning techniques for RNN queries in both 2D and high-dimensional spaces. These techniques are generalized for kRNN queries, which return the k nearest neighbors for every point in the range. In addition, we devise an auxiliary solution-based index EXO-tree to speed up any type of NN query. EXO-tree is orthogonal to any existing NN processing algorithm and, thus, can be transparently integrated. An extensive empirical study was conducted to evaluate the CPU and I/O performance of these techniques, and the study showed that they are efficient and robust under various data sets, query ranges, numbers of nearest neighbors, dimensions, and cache sizes.     

受限区域内的单纯型连续近邻链查询方法

由于已有的最近邻查询方法无法直接处理受限区域内的单纯型连续近邻链查询问题,针对受限区域和障碍物的复杂性,详细研究了受限区域内无障碍物和有障碍物环境下的单纯型连续近邻链查询方法,分别提出了VOR_NB_CRSCNNC算法和VOR_CB_CRSCNNC算法。算法基于计算几何中的Voronoi图和判定圆域对空间数据对象进行预先筛选和计算,每次查询仅需考虑落在数量较少的Voronoi多边形和判定圆域内的数据点,预先过滤掉大量数据,减少每次计算涉及的数据量。理论研究和实验分析表明,所提出的算法在查询过程中减少了数据逐一判断的冗余计算,受受限区域形状的影响较小,较大程度提高了查询效率。     

基于Voronoi图及其对偶图的反最近邻查询

最近邻查询是地理信息系统领域经常遇到的问题,而反最近邻查询是在最近邻查询的基础上提出的一种新的查询类型。在分析利用Voronoi图进行最近邻查询的基础上,提出了基于Voronoi图及其对偶图Delaunay图的反最近邻查询,大大缩小了在海量空间数据库中进行反最近邻查询的查询范围。     

基于簇内乘积量化的最近邻检索方法

本文针对大规模高维数据近邻检索中的瓶颈问题,提出基于向量量化的一种检索方法—簇内乘积量化树方法.该方法运用向量量化和乘积量化的多层树状结构高效表征大规模高维数据集,与现有方法相比降低了索引表空桶率;其次提出基于贪心队列的近邻簇筛选方法减小了计算复杂度,加快了近邻检索速度;最后提出面量化方法用于近似计算候选数据集向量与查询向量间的距离,与点量化和线量化方法相比量化误差更小,提高了近邻查询准确率.本文提出的簇内乘积量化树算法在算子Sift和Gist描述的大规模高维数据集上与乘积量化树技术相比,首次召回准确率提高了57.7%,索引表空桶率降低幅度在50%以上,与局部优化乘积量化技术相比,查全率高达97%,而查询时间却仅需原来的1/9.实验结果表明本文提出的基于簇内乘积量化的近邻方法提升了近邻检索性能,为大规模高维数据集近邻检索提供了理论支持.     

Monochromatic and bichromatic reverse top-k group nearest neighbor queries

The Group Nearest Neighbor (GNN) search is an important approach for expert and intelligent systems, i.e., Geographic Information System (GIS) and Decision Support System (DSS). However, traditional GNN search starts from users’ perspective and selects the locations or objects that users like. Such applications fail to help the managers since they do not provide managerial insights. In this paper, we focus on solving the problem from the managers’ perspective. In particular, we propose a novel GNN query, namely, the reverse top-k group nearest neighbor (RkGNN) query which returns k groups of data objects so that each group has the query object q as their group nearest neighbor (GNN). This query is an important tool for decision support, e.g., location-based service, product data analysis, trip planning, and disaster management because it provides data analysts an intuitive way for finding significant groups of data objects with respect to q. Despite their importance, this kind of queries has not received adequate attention from the research community and it is a challenging task to efficiently answer the RkGNN queries. To this end, we first formalize the reverse top-k group nearest neighbor query in both monochromatic and bichromatic cases, and then propose effective pruning methods, i.e., sorting and threshold pruning, MBR property pruning, and window pruning, to reduce the search space during the RkGNN query processing. Furthermore, we improve the performance by employing the reuse heap technique. As an extension to the RkGNN query, we also study an interesting variant of the RkGNN query, namely a constrained reverse top-k group nearest neighbor (CRkGN) query. Extensive experiments using synthetic and real datasets demonstrate the efficiency and effectiveness of our approaches.     

一种局部相关不确定数据库快照集合上的概率频繁最近邻算法

局部相关空间不确定数据越来越受到许多实际应用的关注.提出了一种新颖的定义在不确定数据库的多个快照上的概率频繁近邻查询,目的是在多个快照数据上找到以一定概率频繁成为查询点最近邻的那些对象.应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵的开销.为了很好地解决这一问题,提出了一般的处理框架,...     

基于平面线段的反向最近邻查询

反向最近邻查询是空间数据库空间查询的研究热点。目前反向最近邻查询的查询粒度都是基于一维的点．在一些空间物体不能抽象为点的情况下将其抽象为点进行反向最近邻查询,查询结果不能达到一定的精度。该文在分析基于平面线段的最近邻查询和R树结构的基础上提出了一种改进的R树－Rcd树,并给出了基于Rcd树的平面线段反向最近邻查询算法．该方法能实现平面线段的反向最近邻查询。