可伸缩的道路网络多连续k近邻查询处理

针对基于道路网络的多用户连续k近邻查询处理,提出了一种可伸缩的多用户连续查询处理(scalable processing of multiple continuous queries,SPMCQ)框架.SPMCQ框架采用流水线处理策略,将连续k近邻查询执行分解为可同时作业的预处理、查询执行和结果分发3个阶段,利用多线程技术提高查询处理的并行性.基于SPMCO框架,分别利用基于内存的哈希表和线性链表结构对移动对象位置和道路网络有向图模型进行存储和管理,提出了多连续k近邻查询处理SCkNN算法.实验结果表明,在处理多用户连续k近邻查询时,该算法性能优于目前的道路网络连续k近邻查询处理算法.     

Scalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain data

In several emerging and important applications, such as location-based services, sensor monitoring and biological databases, the values of the data items are inherently imprecise. A useful query class for these data is the Probabilistic Nearest-Neighbor Query (PNN), which yields the IDs of objects for being the closest neighbor of a query point, together with the objects’ probability values. Previous studies showed that this query takes a long time to evaluate. To address this problem, we propose the Constrained Nearest-Neighbor Query (C-PNN), which returns the IDs of objects whose probabilities are higher than some threshold, with a given error bound in the answers. We show that the C-PNN can be answered efficiently with verifiers. These are methods that derive the lower and upper bounds of answer probabilities, so that an object can be quickly decided on whether it should be included in the answer. We design five verifiers, which can be used on uncertain data with arbitrary probability density functions. We further develop a  partial evaluation technique, so that a user can obtain some answers quickly, without waiting for the whole query evaluation process to be completed (which may incur a high response time). In addition, we examine the maintenance of a long-standing, or continuous C-PNN query. This query requires any update to be applied to the result immediately, in order to reflect the changes to the database values (e.g., due to the change of the location of a moving object). We design an incremental update method based on previous query answers, in order to reduce the amount of I/O and CPU cost in maintaining the correctness of the answers to such a query. Performance evaluation on realistic datasets show that our methods are capable of yielding timely and accurate results.     

Vague continuous K-nearest neighbor queries over moving objects with uncertain velocity in road networks

Recent research has focused on Continuous K Nearest Neighbor (CKNN) queries in road networks, where the queries and the data objects are moving. Most existing approaches assume the fixed velocity of moving objects. The release of fixed moving velocity makes the query process slowly due to the significant repetitive query cost. In this paper, we study CKNN queries over moving objects with uncertain velocity in road networks. A Distance Interval Model (DIM) is designed to calculate the minimal and maximal road network distances between moving objects and query point. Furthermore, we propose a novel Possibility-based Vague KNN (PVKNN) algorithm to process the query efficiently, which determines the CKNN query results with possibility within each division time subinterval of given time interval by applying the vague set theory. In the PVKNN algorithm, the query efficiency can be improved significantly with the pruning, distilling and possibility-ranking phases. With these phases, the objects candidates are scaled down and the given time interval is divided into subintervals to reduce the repetitive query cost. In addition, an index structure TPR^uv-Tree is designed to efficiently index moving objects with uncertain velocity in road network by involving edge connection and moving objects information. Experiments with simulation and comparison show that significant improvement in the performance of efficiency can be achieved with our proposed algorithms.     

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.     

Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity

Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [t _s , t _e ] and a moving query object q, a CR query is to find the moving objects whose Euclidean distances to q are within a user-given distance at each time instant within [t _s , t _e ]. A CKNN query is to retrieve the K-Nearest Neighbors (KNNs) of this query object q at each time instant within [t _s , t _e ]. In this paper, we investigate how to process these spatio-temporal queries efficiently under the situation that the velocity of each object is not fixed. This uncertainty on the velocity of object inevitably results in high complexity in processing spatio-temporal queries. We will discuss the complications incurred by this uncertainty and propose two algorithms, namely the Possibility-based possible within objects searching algorithm and the Possibility-based possible KNN searching algorithm, for the CR query and the CKNN query, respectively. A Possibility-based model is designed accordingly to quantify the possibility of each object being the result of a CR query or a CKNN query. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approaches.     

Aggregate nearest neighbor queries in uncertain graphs

Most recently, uncertain graph data begin attracting significant interests of database research community, because uncertainty is the intrinsic property of the real-world and data are more suitable to be modeled as graphs in numbers of applications, e.g. social network analysis, PPI networks in biology, and road network monitoring. Meanwhile, as one of the basic query operators, aggregate nearest neighbor (ANN) query retrieves a data entity whose aggregate distance, e.g. sum, max, to the given query data entities is smaller than those of other data entities in a database. ANN query on both certain graph data and high dimensional data has been well studied by previous work. However, existing ANN query processing approaches cannot handle the situation of uncertain graphs, because topological structures of an uncertain graph may vary in different possible worlds. Motivated by this, we propose the aggregate nearest neighbor query in uncertain graphs (UG-ANN) in this paper. First of all, we give the formal definition of UG-ANN query and the basic UG-ANN query algorithm. After that, to improve the efficiency of UG-ANN query processing, we develop two kinds of pruning approaches, i.e. structural pruning and instance pruning. The structural pruning takes advantages the monotonicity of the aggregate distance to derive the upper and lower bounds of the aggregate distance for reducing the graph size. Whereas, the instance pruning decreases the number of possible worlds to be checked in the searching tree. Comprehensive experimental results on real-world data sets demonstrate that the proposed method significantly improves the efficiency of the UG-ANN query processing.     

动态环境中连续K近邻查询的边界线方法

通过观察可以发现连续七近邻查询中KNN发生改变的必要条件是第k个邻居发生变化,因此不需要监测所有k近邻,只需要监测第k个邻居即可.该方法采用边界线来监测第k个邻居的变化,不过这需要将原始空间转变为时间-距离(TD)空间后进行操作.在TD空间中每一个对象用一个时间函数来表示,通过监测当前第七个邻居的前视矩形区域来构造边界线.实验结果表明,边界线算法在七非常大的时候是最有效的.     

Probabilistic nearest neighbor queries of uncertain data via wireless data broadcast

Most existing location-dependent query processing methods are based on the client-server model. However, due to the increasing nubmer of smart mobile devices, there can be a large volume of data being processed on the server side and the server can be system performance bottleneck. This paper takes the first step towards processing probabilistic nearest neighbor queries of uncertain data objects via wireless data broadcast (BPNN). Our method leverages the key properties of Voronoi Diagrams for Uncertain Data (UV-Diagram). To preserve the good properties of UV-Diagram, according to the property of Hilbert curve, UV-Hilbert-Partition is proposed to partition the UV-Diagram into several grid cells, called Hilbert-Cells, which have good locality-preserving behavior. Then a special organizing method is proposed. For a certain UV-Diagram, the CellFrame structure, which can be located based on the coordinates of a query client, is used to efficiently minimize the broadcast cycle and keep the probabilistic nearest neighbor results. Based on the sequence of the CellFrames, a distributed index, called UVHilbert-DI, is proposed to support BPNN query processing. Finally, the efficient BPNN algorithms based on UVHilbert-DI is presented and extensive experiments have been conducted to demonstrate the performance of our approaches.     

Probabilistic nearest neighbor query processing on distributed uncertain data

A nearest neighbor (NN) query, which returns the most similar object to a user-specified query object, plays an important role in a wide range of applications and hence has received considerable attention. In many such applications, e.g., sensor data collection and location-based services, objects are inherently uncertain. Furthermore, due to the ever increasing generation of massive datasets, the importance of distributed databases, which deal with such data objects, has been growing. One emerging challenge is to efficiently process probabilistic NN queries over distributed uncertain databases. The straightforward approach, that each local site forwards its own database to the central server, is communication-expensive, so we have to minimize communication cost for the NN object retrieval. In this paper, we focus on two important queries, namely top-k probable NN queries and probabilistic star queries, and propose efficient algorithms to process them over distributed uncertain databases. Extensive experiments on both real and synthetic data have demonstrated that our algorithms significantly reduce communication cost.     

Efficient processing of probabilistic group subspace skyline queries in uncertain databases

Due to the pervasive data uncertainty in many real applications, efficient and effective query answering on uncertain data has recently gained much attention from the database community. In this paper, we propose a novel and important query in the context of uncertain databases, namely probabilistic group subspace skyline (PGSS) query, which is useful in applications like sensor data analysis. Specifically, a PGSS query retrieves those uncertain objects that are, with high confidence, not dynamically dominated by other objects, with respect to a group of query points in ad-hoc subspaces. In order to enable fast PGSS query answering, we propose effective pruning methods to reduce the PGSS search space, which are seamlessly integrated into an efficient PGSS query procedure. Furthermore, to achieve low query cost, we provide a cost model, in light of which uncertain data are pre-processed and indexed. Extensive experiments have been conducted to demonstrate the efficiency and effectiveness of our proposed approaches.     

DHTJoin: processing continuous join queries using DHT networks

Continuous query processing in data stream management systems (DSMS) has received considerable attention recently. Many applications share the same need for processing data streams in a continuous fashion. For most distributed streaming applications, the centralized processing of continuous queries over distributed data is simply not viable. This paper addresses the problem of computing approximate answers to continuous join queries over distributed data streams. We present a new method, called DHTJoin, which combines hash-based placement of tuples in a Distributed Hash Table (DHT) and dissemination of queries by exploiting the embedded trees in the underlying DHT, thereby incurring little overhead. DHTJoin also deals with join attribute value skew which may hurt load balancing and result completeness. We provide a performance evaluation of DHTJoin which shows that it can achieve significant performance gains in terms of network traffic.     

基于KNN的剩余油形态识别

对从实验中采集到的剩余油图像进行分析研究,可以为油藏后期开采提供理论依据。通过收集确定类型的剩余油特征数据作为样本集向量空间,对待分类剩余油特征数据进行归一化处理,之后求取欧氏距离。使用KNN(K近邻)分类方法近邻投票确定剩余油类别,可以较为快速准确地得到分类结果。     

连续不确定XML数据查询处理算法

针对目前连续不确定XML数据同步多区间的查询处理算法易造成较大时间开销的问题,提出一种基于蒙特卡洛最小二乘思想的小枝模式查询处理算法QueryLSMC.算法根据查询请求依节点遍历序列顺序处理路径栈中节点,利用链表匹配并存储中间结果,通过构造随机样本集线性拟合目标节点中的连续分布函数,避免了对大量矩形分段的处理,有效地减少了计算量.实验结果表明,在取得理想精度的同时,该算法具有高效性.     

Efficiently processing snapshot and continuous reverse k nearest neighbors queries

Given a set of objects and a query q, a point p is called the reverse k nearest neighbor (RkNN) of q if q is one of the k closest objects of p. In this paper, we introduce the concept of influence zone that is the area such that every point inside this area is the RkNN of q and every point outside this area is not the RkNN. The influence zone has several applications in location-based services, marketing and decision support systems. It can also be used to efficiently process RkNN queries. First, we present efficient algorithm to compute the influence zone. Then, based on the influence zone, we present efficient algorithms to process RkNN queries that significantly outperform existing best-known techniques for both the snapshot and continuous RkNN queries. We also present a detailed theoretical analysis to analyze the area of the influence zone and IO costs of our RkNN processing algorithms. Our experiments demonstrate the accuracy of our theoretical analysis. This paper is an extended version of our previous work (Cheema et?al. in Proceedings of ICDE, pp. 577–588, 2011). We make the following new contributions in this extended version: (1) we conduct a rigorous complexity analysis and show that the complexity of one of our proposed algorithms in Cheema et?al. (Proceedings of ICDE, pp. 577–588, 2011) can be reduced from O(m ²) to O( km) where m?>?k is the number of objects used to compute the influence zone, (2) we show that our techniques can be applied to dimensionality higher than two, and (3) we present efficient techniques to handle data updates.     

Nearest neighbor queries with peer-to-peer data sharing in mobile environments

Nearest neighbor queries, such as determining the proximity of stationary objects (e.g., restaurants and gas stations) are an important class of inquiries for supporting location-based services. We present a novel approach to support nearest neighbor queries from mobile hosts by leveraging the sharing capabilities of wireless ad-hoc networks. We illustrate how previous query results cached in the local storage of neighboring mobile users can be leveraged to either fully or partially compute and verify nearest neighbor queries at a local host. The feasibility and appeal of our technique is illustrated through extensive simulation results that indicate a considerable reduction of the query load on the remote database. Furthermore, the scalability of our approach is excellent because a higher density of mobile hosts increases its effectiveness.     

Distributed processing of continuous sliding-window k-NN queries for data stream filtering

A sliding-window k-NN query (k-NN/w query) continuously monitors incoming data stream objects within a sliding window to identify k closest objects to a query. It enables effective filtering of data objects streaming in at high rates from potentially distributed sources, and offers means to control the rate of object insertions into result streams. Therefore k-NN/w processing systems may be regarded as one of the prospective solutions for the information overload problem in applications that require processing of structured data in real-time, such as the Sensor Web. Existing k-NN/w processing systems are mainly centralized and cannot cope with multiple data streams, where data sources are scattered over the Internet. In this paper, we propose a solution for distributed continuous k-NN/w processing of structured data from distributed streams. We define a k-NN/w processing model for such setting, and design a distributed k-NN/w processing system on top of the Content-Addressable Network (CAN) overlay. An extensive evaluation using both real and synthetic data sets demonstrates the feasibility of the proposed solution because it balances the load among the peers, while the messaging overhead within the P2P network remains reasonable. Moreover, our results clearly show the solution is scalable for an increasing number of queries and peers.     

基于SR-树的空间对象最近邻查询

最近邻查询是空间数据库的重要应用之一,最近邻查询概念的扩展,即时象的相似性查询中,利用以往的定位查询以厦范围查询方法不能很好的解决最近邻查询的问题,在分析NN查询的基本概念和存储区域的基础上,提出区别于以往NN查询的基于SR-树的多时象NN查询方法,根据某几个查询点,找出离它们最近的一个点或者是七个点,在某种意义上是寻求一种最优方案。     

A survey of queries over uncertain data

Uncertain data have already widely existed in many practical applications recently, such as sensor networks, RFID networks, location-based services, and mobile object management. Query processing over uncertain data as an important aspect of uncertain data management has received increasing attention in the field of database. Uncertain query processing poses inherent challenges and demands non-traditional techniques, due to the data uncertainty. This paper surveys this interesting and still evolving research area in current database community, so that readers can easily obtain an overview of the state-of-the-art techniques. We first provide an overview of data uncertainty, including uncertainty types, probability representation models, and sources of probabilities. We next outline the current major types of uncertain queries and summarize the main features of uncertain queries. Particularly, we present and analyze several typical uncertain queries in detail, such as skyline queries, top- $k$ queries, nearest-neighbor queries, aggregate queries, join queries, range queries, and threshold queries over uncertain data. Finally, we present many interesting research topics on uncertain queries that have not yet been explored.