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

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

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

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

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

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

面向不确定数据的概率阈值可见最近邻查询算法

在现实世界中,障碍物的存在影响了查询点到对象的可见性.可见最近邻查询返回到查询点最近的一个可见对象,是时空数据库中的一类重要应用.由于度量设备的误差和隐私保护,很多关于空间对象位置的数据是不确定的.将不确定对象应用到可见最近邻查询中便产生了概率可见最近邻查询,返回成为可见最近邻概率大于0的对象.有些情况下,用户只关心概率超过一定阈值的结果,于是本文提出了概率阈值可见最近邻查询,返回可见最近邻概率超过阈值T的不确定对象,其中阈值T是用户设定的,并且给出了高效的概率阈值可见最近邻查询算法.相比以前的工作,不仅处理了概率和为1的不确定对象,而且处理了概率和小于1的不确定对象;此外,通过引入缺失概率和聚类的概念,提出了高效的过滤技术和快速的批处理技术.最后通过实验验证了本算法的高效性和有效性.     

障碍环境中可视反向视域K最近邻查询

在障碍环境下的空间应用中,用户通常只对视域范围内可视的数据对象感兴趣。为解决障碍环境中视域范围内的反向最近邻查询问题,将视域可视性引入到反向K最近邻查询中,提出一种可视反向视域K最近邻查询算法。给定某空间数据集P、障碍集O和查询点q,可视反向视域K最近邻查询检索P中数据点,并将q作为可视视域K最近邻。应用查询点进行障碍过滤,得到障碍过滤算法,利用数据对象的视域进行剪枝,使用查询点与数据对象的关系剪枝,形成有效的障碍剪枝规则,并根据剪枝规则得到视域可视性判断算法。在此基础上,分别基于R^*-树和VFR-树提出可视反向视域K最近邻查询算法R^*-V2-RKNN和VFR-V2-RKNN,并分别通过对R^*-树和VFR-树进行一次遍历得到查询结果。在真实数据集和模拟数据集上的实验结果表明,VFR-V2-RKNN算法的查询性能明显优于R^*-V2-RKNN算法。     

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

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

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

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

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

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

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

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

空间数据库中混合数据组最近邻查询

现有的组最近邻查询方法主要将空间中数据对象抽象为点或线段进行处理。但在现实应用中,仅仅将空间对象抽象为点或者线段,往往会影响查询的精度及效率。针对现有的组最近邻查询方法无法直接有效地处理混合数据组最近邻查询的不足,提出空间数据库中混合数据组最近邻查询方法。首先提出了混合数据Voronoi图的概念和性质。接着基于混合数据Voronoi图对混合数据集进行剪枝,针对查询对象数量为1和查询对象数量大于1的情况分别给出了相应的剪枝算法。利用所提的剪枝算法能有效去除不可能成为结果的数据对象,得到候选集合。在精炼过程中根据各个数据对象之间的位置关系给出相应的距离计算方法,通过比较候选集中数据对象到各个查询对象的距离之和,最终得到正确的查询结果。理论研究和实验表明,所提算法能够准确、有效地处理混合数据组最近邻查询问题。     

Reverse nearest neighbors in large graphs

A reverse nearest neighbor (RNN) query returns the data objects that have a query point as their nearest neighbor (NN). Although such queries have been studied quite extensively in Euclidean spaces, there is no previous work in the context of large graphs. In this paper, we provide a fundamental lemma, which can be used to prune the search space while traversing the graph in search for RNN. Based on it, we develop two RNN methods; an eager algorithm that attempts to prune network nodes as soon as they are visited and a lazy technique that prunes the search space when a data point is discovered. We study retrieval of an arbitrary number k of reverse nearest neighbors, investigate the benefits of materialization, cover several query types, and deal with cases where the queries and the data objects reside on nodes or edges of the graph. The proposed techniques are evaluated in various practical scenarios involving spatial maps, computer networks, and the DBLP coauthorship graph.     

面向移动对象的高效组最近邻居查询方法

组最近邻居查询是移动对象数据库重要的查询类型之一。本文提出了一种基于网格索引结构的剪枝搜索策略,将空间区域划分为网格,通过对象点的网格单元标识减少组最近邻居查询所需要的节点访问代价。用步长迭代法得到查询对象集的质心,提出了一种移动对象组最近邻居查询MOGNN算法,采用更精确的裁剪搜索空间准则,减少了查询所需要访问的节点数目。实验结果与分析表明,基于网格索引的MOGNN查询算法具有良好的查询性能。     

Spatial query processing for fuzzy objects

Range and nearest neighbor queries are the most common types of spatial queries, which have been investigated extensively in the last decades due to its broad range of applications. In this paper, we study this problem in the context of fuzzy objects that have indeterministic boundaries. Fuzzy objects play an important role in many areas, such as biomedical image databases and GIS communities. Existing research on fuzzy objects mainly focuses on modeling basic fuzzy object types and operations, leaving the processing of more advanced queries largely untouched. In this paper, we propose two new kinds of spatial queries for fuzzy objects, namely single threshold query and continuous threshold query, to determine the query results which qualify at a certain probability threshold and within a probability interval, respectively. For efficient single threshold query processing, we optimize the classical R-tree-based search algorithm by deriving more accurate approximations for the distance function between fuzzy objects and the query object. To enhance the performance of continuous threshold queries, effective pruning rules are developed to reduce the search space and speed up the candidate refinement process. The efficiency of our proposed algorithms as well as the optimization techniques is verified with an extensive set of experiments using both synthetic and real datasets.     

移动对象的动态反向k最近邻研究

反向最近邻查询是空间数据库中最重要的算法之一。传统的反向最近邻查询方法主要是针对静态对象的查询,随着无线通讯和定位技术的快速发展,移动对象发出的查询请求成为新的研究热点。该文将TPR-tree作为算法的索引结构,并提出了基于矩形框的对角线的修剪策略,将半平面修剪策略进行改进,给出了移动对象的动态反向k最近邻的查询方案。     

障碍环境中线段组最近邻查询方法研究

为了解决现有成果无法有效处理障碍环境下的线段组最近邻查询问题,提出了障碍环境中线段组最近邻查询方法。查询过程分为过滤阶段和精炼阶段两个部分。在过滤过程中,首先根据线段Voronoi图的性质以及线段障碍组最近邻查询的定义,提出了针对数据线段的剪枝定理,并提出了OLGNN_Line_Filter算法;根据线段障碍距离的定义,进一步提出针对障碍物的剪枝定理,并给出了OLGNN_Obstacle_Filter算法。在精炼过程中,为了得到更精确的查询结果,提出了相应的精炼定理和精炼算法STA_OLGNN。理论研究和实验表明,所提算法能够有效地处理障碍环境下的线段组最近邻查询问题。     

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.     

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

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

DART+: Direction-aware bichromatic reverse k nearest neighbor query processing in spatial databases

This article presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor(DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBRkNN query returns a subset P′ of P such that k nearest neighbors of each object in P′ include q and each object in P′ has a direction toward q within a pre-defined distance. We formally define the DBRkNN query, and then propose an efficient algorithm, called DART, for processing the DBRkNN query. Our method utilizes a grid-based index to cluster the spatial objects, and the B⁺-tree to index the direction angle. We adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than a pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. As a major extension of DART, we also present an improved algorithm, called DART+, for DBRkNN queries. From extensive experiments with several datasets, we show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time. In addition, our extension algorithm, DART+, also shows significantly better performance than DART.     

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.