空间数据库中的障碍反向最近邻查询

反向最近邻查询已成为空间查询的热点问题,而障碍物在实际应用中是不可避免的,因而在障碍物环境中的反向最近邻查询也成为重要的空间查询。已有的可视反向最近邻查询只考虑了可视性,并没有考虑最小障碍距离。提出一种障碍物环境中新的反向最近邻查询的变体,查找障碍距离最小的反向最近邻,即障碍反向最近邻查询。利用障碍距离的计算和相应的剪枝规则,给出障碍反向最近邻查询的算法及相关定理和证明。     

面向不确定数据的概率障碍k聚集最近邻查询

针对现有方法无法有效处理不确定数据的障碍k聚集最近邻查询问题的不足,提出了基于不确定Voronoi图的概率障碍k聚集最近邻查询(probabilistic obstacle k aggregate nearest neighbor query,POk ANN)方法。该方法分为3个阶段,分别是查询点集处理阶段、过滤阶段和精炼阶段。在处理阶段,计算查询点集的最小覆盖圆圆心q,为剪枝做准备。过滤阶段针对3种聚集函数设计了不同的过滤算法,去除不可能成为结果的数据点进而得到候选集合。精炼阶段将候选集合中概率值大于给定阈值的k个数据点集合存入结果集合并返回给用户。理论研究和实验表明,所提出的方法在概率障碍k聚集最近邻查询方面有明显的优势。     

移动对象反向最近邻查询技术研究

提出一种基于自调节网格索引的反向最近邻查询(RNNQ)算法,将空间划分为大小相等的网格单元,每个单元作为一个桶存储移动对象,采用基于桶内对象数目和网格几何特征的剪枝策略减少反向最近邻查询所需访问的节点。查询点周围单元桶内对象过多时进行二次网格划分,减小节点访问代价。实验结果表明,该算法具有良好的查询性能,优于基于TPR树索引的RNNQ算法。     

室内双色数据集上的反向最近邻查询

随着Wi-Fi、RFID等室内定位技术的发展,产生了越来越多的基于室内空间的位置服务需求。目前已有文献提出了针对室内环境的范围查询和最近邻查询,而双色反向最近邻（bichromatic reverse nearest neighbor,BRNN）查询作为常见的空间查询类型,在室内空间中尚未有相关的研究。为此,提出了基于兴趣点集合的兴趣点融合图模型,并提出了基于路径、基于楼层和基于单元的3种剪枝策略,用于在查询处理时削减搜索空间。在兴趣点融合图和剪枝策略的基础上,提出了室内双色反向最近邻（indoor bichromatic reverse nearest neighbor, IBRNN）查询算法Smart。Smart算法通过对兴趣点融合图中的图元素的检查,从而判断与该图元素关联的移动对象是否有可能属于结果集。最后通过实验,对所提算法的有效性和高效性进行了验证。     

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

为了提升障碍空间中k最近邻查询的效率,研究了障碍空间中基于Voronoi图的k最近邻查询方法,提出了在障碍空间基于Voronoi图的kNN-Obs算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用Voronoi图的过滤功能,较大程度地减少了被查询点的个数。精炼过程主要根据障碍距离和邻接生成点对候选集内对象进行第二次筛选。进一步给出了处理新增加点的ADDkNN-Obs算法和处理删除点的DENkNN-Obs算法。实验表明该算法在处理障碍空间中的k最近邻问题时具有优势。     

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

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

基于R树及其变种的最近邻查询研究

最近邻查询是空间数据查询领域中最重要的查询技术之一.最近邻查询根据所查询的目标对象的运动特性分为静态最近邻查询和动态最近邻查询.静态最近邻查询的关键在于运用最小距离和最小最大距离作为查询条件,对索引树的节点进行排序和剪枝进而查找目标对象 通过对现有最近邻查询算法的分析研究,比较这些现有算法的优缺点     

球面上的K最近邻查询算法

针对球面上数据对象点集的特征和K最近邻查询的需求,提出2种处理球面上K最近邻查询的算法:基于查询轴的K最近邻查询算法(PAM方法)和基于查询圆面的K最近邻查询算法(PCM方法).对2种算法进行实验比较,结果表明,PAM方法和PCM方法都适合处理球面上的最近邻查询问题,PAM方法在存储量和查询复杂度方面相对于PCM方法具...     

路网中双色数据集上连续反向k近邻查询处理的研究

近年来,反向最近邻查询(RNN)算法研究得到了普遍的关注,成为了数据库领域的一个研究热点。欧氏空 间中提出了较多的高效算法,而路网中的反向最近邻处理方面所做的工作不够,有关这方面的成果较少。路网中查询 点和数据对象之间以及不同数据对象之间的距离受到路网连通性的影响,欧氏空间中的反向最近部方法在路网中不 适用。反向最近部查询有两种类型:单色反向最近部查询(Monochromatic RNN, MRNN)和双色反向最近部查询(13i- chromatic RNN,13RNN)。到目前为止,仍然没有有效的算法来处理路网中双色数据集上的连续反向k近部查询。因 此,研究路网中双色数据集上连续反向k近部查询是很有意义的。     

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

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

一种移动对象增量组最近邻居查询方法

基于移动对象增量最近邻居查询(INCNN),提出一种移动对象增量组最近邻居查询方法(INCGNN)。该方法以较小的代价求出每次更新时刻的组最近邻居。针对组最近邻居查询的特点,给出了k+1组最近邻居查询改进算法,椭圆剪枝和延迟更新3种优化查询的策略。实验结果表明,INCGNN明显优于REEGNN,3种优化策略能较好地提高查询性能。     

基于Δ-tree的递归深度优先KNN查询算法

基于Δ-tree提出一种用于高维数据的主存K最近邻(KNN)查询算法。该算法利用递归调用方法深度优先遍历Δ-tree,找到距离查询点较近的叶子节点,并选择其中较优的KNN候选点进行查询,从而缩小修剪距离、提高查询速度。实验结果表明,与已有算法相比,该算法具有更高的查询效率。     

Visible Reverse k-Nearest Neighbor Query Processing in Spatial Databases

Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings) and their presence may affect the visibility between objects. In this paper, we introduce a novel variant of RNN queries, namely, visible reverse nearest neighbor (VRNN) search, which considers the impact of obstacles on the visibility of objects. Given a data set P, an obstacle set O, and a query point q in a 2D space, a VRNN query retrieves the points in P that have q as their visible nearest neighbor. We propose an efficient algorithm for VRNN query processing, assuming that P and O are indexed by R-trees. Our techniques do not require any preprocessing and employ half-plane property and visibility check to prune the search space. In addition, we extend our solution to several variations of VRNN queries, including: 1) visible reverse k-nearest neighbor (VRkNN) search, which finds the points in P that have q as one of their k visible nearest neighbors; 2) delta-VRkNN search, which handles VRkNN retrieval with the maximum visible distance delta constraint; and 3) constrained VRkNN (CVRkNN) search, which tackles the VRkNN query with region constraint. Extensive experiments on both real and synthetic data sets have been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.     

Continuous visible k nearest neighbor query on moving objects

A visible k nearest neighbor (Vk NN) query retrieves k objects that are visible and nearest to the query object, where “visible” means that there is no obstacle between an object and the query object. Existing studies on the Vk NN query have focused on static data objects. In this paper we investigate how to process the query on moving objects continuously. We propose an effective filtering-and-refinement framework for evaluating this type of queries. We exploit spatial proximity and visibility properties between the query object and data objects to prune search space under this framework. A detailed cost analysis and a comprehensive experimental study are conducted on the proposed framework. The results validate the effectiveness of the pruning techniques and verify the efficiency of the proposed framework. The proposed framework outperforms a straightforward solution by an order of magnitude in terms of both communication and computation costs.     

基于贪心策略的最近邻Top-k偏好查询方法

传统Top-[k]空间关键字查询忽略了兴趣对象周围的基础设施属性对于用户偏好的影响,针对该问题,研究了基于影响区域约束关系的Top-[k]空间关键字偏好查询问题,设计了一种基于贪心策略的最近邻算法GS-NNA（Greedy Strategy based Nearest Neighbor Algorithm）。该算法采用R*-tree和倒排文件两种索引结构,结合贪心思想和最近邻算法,每次选择分值最高的兴趣对象作为候选结果集,并利用阈值判定条件对R*-tree进行剪枝。实验结果表明,GS-NNA算法与现有相关算法相比,有效提高了查询效率。     

障碍空间中基于并行蚁群算法的k近邻查询

为解决障碍空间中的k近邻查询问题,提出一种基于改进的并行蚁群算法的k近邻查询方法（PAQ）。首先,利用不同信息素种类的蚁群实现并行查询k近邻;其次,增加时间因素作为路径长短的判断条件,以最直接地呈现蚂蚁的搜索时间;然后,重新定义初始信息素浓度,以避免蚂蚁的盲目搜索;最后,引入可视点将障碍路径分割为多段欧氏路径,选择可视点进行概率转移,并改进启发函数,以促使蚂蚁朝着更为正确的方向搜索,避免算法过早陷入局部最优。与WithGrids相比,当数据点个数小于300时,对于线段障碍,算法运行时间平均缩短约91.5%;对于多边形障碍平均缩短约78.5%。实验结果表明,该方法在数据规模较小时的运行时间具有明显的优势,且可以处理多边形障碍。     

基于Voronoi图的线段反向最近邻查询

提出一种基于平面线段的反向最近邻查询方法,用于找出线段集中以查询线段作为最近邻的线段。通过构造线段集的Voronoi图处理不相交的线段。根据其邻接特性和局部特性,给出基于Voronoi图的线段反向最近邻查询算法及相关定理和证明。实验结果表明,反向最近邻方法易于找到相交的线段,具有较高的查询效率。     

Probabilistic Group Nearest Neighbor Queries in Uncertain Databases

The importance of query processing over uncertain data has recently arisen due to its wide usage in many real-world applications. In the context of uncertain databases, previous works have studied many query types such as nearest neighbor query, range query, top-k query, skyline query, and similarity join. In this paper, we focus on another important query, namely, probabilistic group nearest neighbor (PGNN) query, in the uncertain database, which also has many applications. Specifically, given a set, Q, of query points, a PGNN query retrieves data objects that minimize the aggregate distance (e.g., sum, min, and max) to query set Q. Due to the inherent uncertainty of data objects, previous techniques to answer group nearest neighbor (GNN) query cannot be directly applied to our PGNN problem. Motivated by this, we propose effective pruning methods, namely, spatial pruning and probabilistic pruning, to reduce the PGNN search space, which can be seamlessly integrated into our PGNN query procedure. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed approach, in terms of the wall clock time and the speed-up ratio against linear scan.