移动对象的反向k近邻查询算法的研究

传统的反向k近邻查询的研究主要集中在k=1时的单色移动对象的反向最近邻查询上,单色和双色的反向k近邻查询问题还没有解决。利用网格索引结构结合60°平面修剪策略,提出了一种解决单色和双色的移动对象的连续反向k近邻查询方法。最后实验结果验证了算法的有效性。     

路网中互近邻查询处理方法

提出路网中的互近邻查询问题.给定路网G(V,E),对象集P,查询点q,近邻数k1和k2,互近邻查询返回既是q的k1近邻,又是q的反k2近邻的对象集.为解决该问题,首先提出基础算法,即先求出查询点q的k1近邻作为候选,再验证这些候选是否为真正的结果.然后,在此基础上提出了优化算法,根据落在对象点与查询点最短路径边上的标记点个数直接排除掉一些错误的候选对象.最后,通过实验验证了优化算法的有效性.     

路网中查询点速度不确定的连续k近邻查询方法

提出一种路网中查询点速度不确定的连续k近邻查询方法.查询点在起始位置向服务器提出查询请求,得到k近邻的候选集.随着查询点的移动,利用有效候选集计算当前的k近邻,而不必再向服务器请求,从而减少了服务器计算代价.当候选集部分失效时,由服务器返回候选集中失效的兴趣点的当前信息,使候选集有效.当候选集完全失效时,由查询点重新向服务器提出查询请求,得到新的候选集.并提出一种计算候选集的优化方法,降低了查询代价.最后,通过实验验证了所提算法的有效性.     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

距离-关键字相似度约束的双色反k近邻查询方法

针对空间关键字双色反k近邻查询返回结果质量较低的问题,提出了基于距离-关键字相似度约束的双色反k近邻查询方法。首先,通过设置一个阈值将查询结果中质量较低的用户给过滤掉,从而避免了查询结果中出现空间距离相对较远的用户,保证了查询结果质量;然后,为支持该查询,提出了一种关键字多分辨率网格矩形树（KMG-Tree）索引来管理数据;最后,提出了基于Six-region算法的Six-region-optimize算法来提高查询处理效率。Six-region-optimize算法的查询效率相较baseline和Six-region算法分别平均提高了约85.71%和23.45%。基于真实时空数据进行实验测试和分析,实验结果验证了Six-region-optimize算法的有效性和高效性。     

一种新的面向集合的空间关键字查询方法

面向集合的空间关键字查询处理是数据库领域近年来的热点研究课题.针对已有查询的不足,定义一种新的描述集合质量的Cost函数,提出一种新的面向集合的空间关键字查询方法,并证明基于该Cost函数的查询问题是NP完全问题.对于给定的对象数据集D={o1,o2,…,on},q为包含位置信息和关键字集合的查询点,查询返回的是在对象数据集D中,既满足查询点q的全部关键字,又能成为q的近邻且较紧凑的对象集合.为处理该查询,利用最小圆覆盖包含全部关键字的对象集合,并采用有效的裁剪策略分别实现了该查询的近似查询算法和精确查询算法.最后通过实验验证了所提算法的有效性.     

一种面向不确定对象的可见k近邻查询算法

真实世界中,常存在很多障碍物,影响空间对象到查询点的可见性及距离,可见k近邻查询查找距查询点最近的k个可见对象,是时空查询领域的一类重要算法.由于度量设备误差以及通信开销的限制等因素,空间对象位置不确定因素广泛存在.文中拟对不确定对象执行可见k近邻查询,提出了概率可见k近邻(PVkNN)查询,即查找前k个成为查询点最近邻居概率最大的节点.为了高效地执行这一查询,文中提出了k-界限剪枝方法,基于可见质心的紧缩过滤以及对不可见对象的剪枝策略,从空间角度过滤掉不符合条件的对象.为避免对候选集合中每个对象的概率都进行精确计算,从概率角度提出了根据概率上下限来对候选集合进行进一步的求精方法,采用近似采样技术来获取可见区域的比例,实现了对PVkNN的高效计算.采用真实和模拟数据集设计实验,充分验证了算法的效率和精度.     

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

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

空间数据库平面线段近邻查询问题研究

空间数据库的近邻查询近几年受到人们越来越多的关注.近邻查询根据程度不同可分为点与点的近邻查询、点与线段、线段与线段的近邻查询.目前,前两者研究的较多,后者没有查到相关文献.提出平面线段与线段的近邻查询问题.有针对性地解决一些空间物体无法抽象为点的情况.平面线段的近邻查询在现实中有着广泛的应用价值.根据平面线段与线段是否相交分为两类;不相交的平面线段再根据位置关系分成9种情况.分别对上述各种情况进行讨论研究.给出了线段近邻查询的筛选规则、定理和查询算法,进行了实验分析和比较,新方法实现了平面线段与线段的近邻查询,具有较高的查询效率.     

面向时间依赖路网的连续k近邻查询

连续k近邻查询(continuous k-nearest neighor,Ck NN)定义为查找指定路径上每个点的k个最小代价数据对象。目前关于Ck NN的研究都是在欧式空间与静态路网中实现的,这些算法不能直接应用到边权值变化的时间依赖路网中。定义并解决了时间依赖路网中的Ck NN问题,利用积分的性质以及通过对权值代价函数合并的方式提出了两阶段的基于分割点的Ck NN查询算法。过滤阶段提出了计算节点到达时间的方法,再利用到达时间查询出多个候选k近邻结果;求精阶段将查询点到候选结果的权值函数合并,通过计算函数交点得到分割点,进而为查询返回若干个分割点以及相应区间内的k近邻结果。实验结果表明,与进行多次快照k近邻查询相比,所提算法在响应时间上减少了近一个数量级。     

Alternative Solutions for Continuous K Nearest Neighbor Queries in Spatial Network Databases

Continuous K nearest neighbor queries (C-KNN) are defined as finding the nearest points of interest along an enitre path (e.g., finding the three nearest gas stations to a moving car on any point of a pre-specified path). The result of this type of query is a set of intervals (or split points) and their corresponding KNNs, such that the KNNs of all points within each interval are the same. The current studies on C-KNN focus on vector spaces where the distance between two objects is a function of their spatial attributes (e.g., Euclidean distance metric). These studies are not applicable to spatial network databases (SNDB) where the distance between two objects is a function of the network connectivity (e.g., shortest path between two objects). In this paper, we propose two techniques to address C-KNN queries in SNDB: Intersection Examination (IE) and Upper Bound Algorithm (UBA). With IE, we first find the KNNs of all nodes on a path and then, for those adjacent nodes whose nearest neighbors are different, we find the intermediate split points. Finally, we compute the KNNs of the split points using the KNNs of the surrounding nodes. The intuition behind UBA is that the performance of IE can be improved by determining the adjacent nodes that cannot have any split points in between, and consequently eliminating the computation of KNN queries for those nodes. Our empirical experiments show that the UBA approach outperforms IE, specially when the points of interest are sparsely distributed in the network.     

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

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

Window Query Processing in Linear Quadtrees

The linear quadtree is a spatial access method that is built by decomposing the spatial objects in a database into quadtree blocks and storing these quadtree blocks in a B-tree. The linear quadtree is very useful for geographic information systems because it provides good query performance while using existing B-tree implementations. An algorithm and a cost model are presented for processing window queries in linear quadtrees. The algorithm can handle query windows of any shape in the general case of spatial databases with overlapping objects. The algorithm recursively decomposes the space into quadtree blocks, and uses the quadtree blocks overlapping the query window to search the B-tree. The cost model estimates the I/O cost of processing window queries using the algorithm. The cost model is also based on a recursive decomposition of the space, and it uses very simple parameters that can easily be maintained in the database catalog. Experiments with real and synthetic data sets verify the accuracy of the cost model.     

A crowd enabled approach for processing nearest neighbor and range queries in incomplete databases with accuracy guarantee

With the proliferation of mobile devices and wireless technologies, location based services (LBSs) are becoming popular in smart cities. Two important classes of LBSs are Nearest Neighbor (NN) queries and range queries that provide user information about the locations of point of interests (POIs) such as hospitals or restaurants. Answers of these queries are more reliable and satisfiable if they come from trustworthy crowd instead of traditional location service providers (LSPs). We introduce an approach to evaluate NN and range queries with crowdsourced data and computation that eliminates the role of an LSP. In our crowdsourced approach, a user evaluates LBSs in a group. It may happen that group members do not have knowledge of all POIs in a certain area. We present efficient algorithms to evaluate queries with accuracy guarantee in incomplete databases. Experiments show that our approach is scalable and incurs less computational overhead.     

Multi-Way Distance Join Queries in Spatial Databases

Let a tuple of n objects obeying a query graph (QG) be called the n-tuple. The D_{_distance}-value of this n-tuple is the value of a linear function of distances of the n objects that make up this n-tuple, according to the edges of the QG. This paper addresses the problem of finding the K n-tuples between n spatial datasets that have the smallest D_{_distance}-values, the so-called K-multi-way distance join query (K-MWDJQ), where each set is indexed by an R-tree-based structure. This query can be viewed as an extension of K-closest-pairs query (K-CPQ) [8] for n inputs. In addition, a recursive non-incremental branch-and-bound algorithm following a depth-first search for processing synchronously all inputs without producing any intermediate result is proposed. Enhanced pruning techniques are also applied to n R-trees nodes in order to reduce the total response time and the number of distance computations of the query. Due to the exponential nature of the problem, we also propose a time-based approximate version of the recursive algorithm that combines approximation techniques to adjust the quality of the result and the global processing time. Finally, we give a detailed experimental study of the proposed algorithms using real spatial datasets, highlighting their performance and the quality of the approximate results.     

A relational language with deductions,functions and recursions

We propose here a .relational algebra capable of deducing tuples from a premise expressed in an extended relational form: it also supports user-defined and recursive functions in the form of parameterised views, and provides a facility for easier specification of queries. The paper shows the power of the language in dealing with problems such as ancestors, part explosions and connected tours.This language, called DEAL, is an enhanced version of the PRECI Algebraic Language (PAL) but presented here in a SQL-like syntax.     

A Probe-Based Technique to Optimize Join Queries in Distributed Internet Databases

An adaptive probe-based optimization technique is developed and demonstrated in the context of an Internet-based distributed database environment. More and more common are database systems which are distributed across servers communicating via the Internet where a query at a given site might require data from remote sites. Optimizing the response time of such queries is a challenging task due to the unpredictability of server performance and network traffic at the time of data shipment; this may result in the selection of an expensive query plan using a static query optimizer. We constructed an experimental setup consisting of two servers running the same database management system connected via the Internet. Concentrating on join queries, we demonstrate how a static query optimizer might choose an expensive plan by mistake. This is due to the lack of a priori knowledge of the run-time environment, inaccurate statistical assumptions in size estimation, and neglecting the cost of remote method invocation. These shortcomings are addressed collectively by proposing a probing mechanism. An implementation of our run-time optimization technique for join queries was constructed in the Java language and incorporated into an experimental setup. The results demonstrate the superiority of our probe-based optimization over a static optimization. Received 6 February 1999 / Revised 15 February 2000 / Accepted 10 May 2000     

Tree-based partition querying: a methodology for computing medoids in large spatial datasets

Besides traditional domains (e.g., resource allocation, data mining applications), algorithms for medoid computation and related problems will play an important role in numerous emerging fields, such as location based services and sensor networks. Since the k-medoid problem is NP-hard, all existing work deals with approximate solutions on relatively small datasets. This paper aims at efficient methods for very large spatial databases, motivated by: (1) the high and ever increasing availability of spatial data, and (2) the need for novel query types and improved services. The proposed solutions exploit the intrinsic grouping properties of a data partition index in order to read only a small part of the dataset. Compared to previous approaches, we achieve results of comparable or better quality at a small fraction of the CPU and I/O costs (seconds as opposed to hours, and tens of node accesses instead of thousands). In addition, we study medoid-aggregate queries, where k is not known in advance, but we are asked to compute a medoid set that leads to an average distance close to a user-specified value. Similarly, medoid-optimization queries aim at minimizing both the number of medoids k and the average distance. We also consider the max version for the aforementioned problems, where the goal is to minimize the maximum (instead of the average) distance between any object and its closest medoid. Finally, we investigate bichromatic and weighted medoid versions for all query types, as well as, maximum capacity and dynamic medoids.     

Database Repairs and Analytic Tableaux

In this article, we characterize in terms of analytic tableaux the repairs of inconsistent relational databases, that is databases that do not satisfy a given set of integrity constraints. For this purpose we provide closing and opening criteria for branches in tableaux that are built for database instances and their integrity constraints. We use the tableaux based characterization as a basis for consistent query answering, that is for retrieving from the database answers to queries that are consistent with respect to the integrity constraints.