移动对象的动态反向最近邻查询技术

为了处理移动对象的动态反向最近邻,对时空动态反向最近邻查询问题进行形式化的定义,利用时空距离函数及限界区域等概念给出计算移动对象的动态反向最近邻的定理与算法,提出移动查询点的动态最近邻的全域查询及局域查询的方法,利用动态检测圆及时空距离函数进行动态反向最近邻的查询判断,其计算量可减少40%~60%。构建新的时空索引结构——TPRDNN树,给出操作TPRDNN树的查询算法。     

基于改进Metric索引的反向最远邻查询方法

PIV算法在构建Metric索引时,需要计算凸包顶点与凸包内的全部数据点距离,当数据集较大时,会浪费存储空间并增加查询消耗。为此,改进Metric索引,只存储凸包顶点与凸包内的部分数据点的距离,提出利用凸包内的点与凸包顶点之间的距离,判断该点是否是查询点反向最远邻的方法。测试结果表明,与PIV算法相比,该方法可以正确得到反向最远邻查询结果,并减少占用的存储空间和查询消耗,提高查询效率。     

障碍环境中可视反向视域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树的平面线段反向最近邻查询算法,该方法能实现平面线段的反向最近邻查询。     

欧式空间中反向最远邻查询方法的研究

大部分反向最远邻查询算法采用过滤-提纯查询处理框架,对数据集和查询点的位置关系不进行判断。针对这种情况,提出了一种处理欧式空间中反向最远邻查询方法,首先利用查询点与凸包之间的位置关系进行判断,得到三种情况,针对第三种情况再进行过滤和提纯两步处理。在过滤步骤中,使用修改的半平面修剪策略,除去大量的数据点,在提纯步骤排除不是查询点反向最远邻的数据点。实验结果验证了算法的有效性。     

利用离散边界点判断的反向最远邻查询算法

目前大部分的反向最远邻查询方法对查询点是否存在反向最远邻的情况不进行判断,当查询点不存在反向最远邻的结果集时,也进行全部的操作,增加了查询消耗。针对这种情况,提出了利用离散边界点判断查询点是否存在反向最远邻结果集的方法,利用离散边界点、四分邻域区和半平面修剪策略进行过滤操作,并验证过滤后得到的结果集中数据点的有效性。实验测试了查询点的位置对查询的影响和数据集的大小以及数据分布对查询的影响,并与利用凸包判断的方法进行了对比分析。实验结果表明,当查询点不是离散边界点时,查询消耗几乎为0,当查询点移动到边界时,查询消耗增加。实验表明提出的方法可以得到查询点的反向最远邻结果集。     

路网中双色反向k近邻查询处理

目前,路网中反向最近邻查询引起了广泛关注,有很多算法被提出.在实际路网中,由于移动数据对象的种类多种多样,单色反向最近邻查询有时并不能完全满足要求.因此,研究路网双色反向最近邻查询具有重要的实际意义.考虑到这种情况,提出一种路网中双色反向最近邻查询算法.通过PMR四叉树索引路网,采用Dijkstra算法遍历路网.为了保证连续监控,为查询点和对象分别设置安全区.为了验证候选对象,为其设置验证监控区.由于双色查询中,对象的种类不同,因此分别采用两个集合来保存这两类对象.通过实验对比,证明该算法具有较好的有效性和稳定性.     

Voronoi图的构建与受限区域内的最近邻查询方法研究

Voronoi图在空间数据查询、数据挖掘、图像处理、模式识别和智能交通管理等方面具有重要的作用。为了简化构建的复杂性和提高构建效率,基于分治法、启发式局部优化策略和局部数据点的扫描线动态更新策略,提出了基于凸包的Voronoi图生成方法,给出了Create_Voronoi()算法。进一步,为了弥补已有近邻查询方法无法处理受限区域内的最近邻查询的不足,基于Voronoi图研究了受限区域内的同质和异质最近邻查询方法,分别提出了TVor_NN()算法和YVor_NN()算法。理论研究和实验分析表明,提出的研究方法在Voronoi图的构建和受限范围的最近邻查询等方面具有较大的优势。     

基于Voronoi图的连续反向最近邻查询

为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。     

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.     

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.     

Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data

Reverse nearest neighbor (RNN) search is very crucial in many real applications. In particular, given a database and a query object, an RNN query retrieves all the data objects in the database that have the query object as their nearest neighbors. Often, due to limitation of measurement devices, environmental disturbance, or characteristics of applications (for example, monitoring moving objects), data obtained from the real world are uncertain (imprecise). Therefore, previous approaches proposed for answering an RNN query over exact (precise) database cannot be directly applied to the uncertain scenario. In this paper, we re-define the RNN query in the context of uncertain databases, namely probabilistic reverse nearest neighbor (PRNN) query, which obtains data objects with probabilities of being RNNs greater than or equal to a user-specified threshold. Since the retrieval of a PRNN query requires accessing all the objects in the database, which is quite costly, we also propose an effective pruning method, called geometric pruning (GP), that significantly reduces the PRNN search space yet without introducing any false dismissals. Furthermore, we present an efficient PRNN query procedure that seamlessly integrates our pruning method. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed GP-based PRNN query processing approach, under various experimental settings.     

Ranked Reverse Nearest Neighbor Search

Given a set of data points P and a query point q in a multidimensional space, reverse nearest neighbor (RNN) query finds data points in P whose nearest neighbors are q. Reverse k-nearest neighbor (RkNN) query (where k ges 1) generalizes RNN query to find data points whose kNNs include q. For RkNN query semantics, q is said to have influence to all those answer data points. The degree of q's influence on a data point p (isin P) is denoted by kappap where q is the kappap-th NN of p. We introduce a new variant of RNN query, namely, ranked reverse nearest neighbor (RRNN) query, that retrieves t data points most influenced by q, i.e., the t data points having the smallest kappa's with respect to q. To answer this RRNN query efficiently, we propose two novel algorithms, kappa-counting and kappa-browsing that are applicable to both monochromatic and bichromatic scenarios and are able to deliver results progressively. Through an extensive performance evaluation, we validate that the two proposed RRNN algorithms are superior to solutions derived from algorithms designed for RkNN query.     

基于Delaunay图的反向最近邻查询

将查询点作为Delaunay图的一个生成点,利用Delaunay图的生成点与其邻接生成点之间的关系,在查询点的邻接生成点集(元素个数小于等于6)中计算数据集中给定点的反向最近邻。把伴随Delaunay图增量生成过程产生的Delaunay树作为查询索引结构,该结构能存储Delaunay图,在数据点插入和删除时维护Delaunay图的拓扑结构。     

Reverse Nearest Neighbors Search in Ad Hoc Subspaces

Given an object q, modeled by a multidimensional point, a reverse nearest neighbors (RNN) query returns the set of objects in the database that have q as their nearest neighbor. In this paper, we study an interesting generalization of the RNN query, where not all dimensions are considered, but only an ad hoc subset thereof. The rationale is that 1) the dimensionality might be too high for the result of a regular RNN query to be useful, 2) missing values may implicitly define a meaningful subspace for RNN retrieval, and 3) analysts may be interested in the query results only for a set of (ad hoc) problem dimensions (i.e., object attributes). We consider a suitable storage scheme and develop appropriate algorithms for projected RNN queries, without relying on multidimensional indexes. Given the significant cost difference between random and sequential data accesses, our algorithms are based on applying sequential accesses only on the projected atomic values of the data at each dimension, to progressively derive a set of RNN candidates. Whether these candidates are actual RNN results is then validated via an optimized refinement step. In addition, we study variants of the projected RNN problem, including RkNN search, bichromatic RNN, and RNN retrieval for the case where sequential accesses are not possible. Our methods are experimentally evaluated with real and synthetic data     

用兴趣点凸包和SVM加权反馈实现图像检索

针对采用环状颜色直方图的图像检索方法存在的不足,提出一种基于兴趣点凸包的图像特征提取方法,通过对用小波变换检测出的必趣点递归求出它们的凸包,并将每个凸包上的兴趣点按一定的算法安插在相应的桶内,对每个桶求出颜色直方图,利用桶与桶之间的相似度定义两幅图像的相似度.这种特征提取方法可有效抑制兴趣点集合中出现游离兴趣点的情况,结合基于兴趣点的空间离散度和Gabor小波纹理等特征实现图像检索,可有效提高图像检索精度.最后,提出一种新的相关反馈方法,通过利用支持向量机分类结果设置权值来改进移动查询点相关反馈方法.实际图像数据库上的实验表明,引入这种反馈方法后可将图像检索的查准率提高20%左右,查全率提高10%左右.     

Convex sets as prototypes for classifying patterns

We propose a general framework for nonparametric classification of multi-dimensional numerical patterns. Given training points for each class, it builds a set cover with convex sets each of which contains some training points of the class but no points of the other classes. Each convex set has thus an associated class label, and classification of a query point is made to the class of the convex set such that the projection of the query point onto its boundary is minimal. In this sense, the convex sets of a class are regarded as “prototypes” for that class. We then apply this framework to two special types of convex sets, minimum enclosing balls and convex hulls, giving algorithms for constructing a set cover with them and for computing the projection length onto their boundaries. For convex hulls, we also give a method for implicitly evaluating whether a point is contained in a convex hull, which can avoid computational difficulty for explicit construction of convex hulls in high-dimensional space.     

Voronoi-based reverse nearest neighbor query processing on spatial networks

The use of Voronoi diagram has traditionally been applied to computational geometry and multimedia problems. In this paper, we will show how Voronoi diagram can be applied to spatial query processing, and in particular to Reverse Nearest Neighbor (RNN) queries. Spatial and geographical query processing, in general, and RNN in particular, are becoming more important, as online maps are now widely available. In this paper, using the concept of Voronoi diagram, we classify RNN into four types depending on whether the query point and the interest objects are the generator points of the Voronoi Polygon or not. Our approach is based on manipulating Network Voronoi Diagram properties and applying a progressive incremental network expansion for finding the polygon inner network distances required to solve RNN queries. Our experimentation results show that our approaches have good response times in answering RNN queries.     

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

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