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.     

Range aggregate processing in spatial databases

A range aggregate query returns summarized information about the points falling in a hyper-rectangle (e.g., the total number of these points instead of their concrete ids). This paper studies spatial indexes that solve such queries efficiently and proposes the aggregate Point-tree (aP-tree), which achieves logarithmic cost to the data set cardinality (independently of the query size) for two-dimensional data. The aP-tree requires only small modifications to the popular multiversion structural framework and, thus, can be implemented and applied easily in practice. We also present models that accurately predict the space consumption and query cost of the aP-tree and are therefore suitable for query optimization. Extensive experiments confirm that the proposed methods are efficient and practical.     

Mining spatial association rules in image databases

In this paper, we propose a novel spatial mining algorithm, called 9DLT-Miner, to mine the spatial association rules from an image database, where every image is represented by the 9DLT representation. The proposed method consists of two phases. First, we find all frequent patterns of length one. Next, we use frequent k-patterns (k ? 1) to generate all candidate (k + 1)-patterns. For each candidate pattern generated, we scan the database to count the pattern’s support and check if it is frequent. The steps in the second phase are repeated until no more frequent patterns can be found. Since our proposed algorithm prunes most of impossible candidates, it is more efficient than the Apriori algorithm. The experiment results show that 9DLT-Miner runs 2-5 times faster than the Apriori algorithm.     

Object-based directional query processing in spatial databases

Direction-based spatial relationships are critical in many domains, including geographic information systems (GIS) and image interpretation. They are also frequently used as selection conditions in spatial queries. In this paper, we explore the processing of object-based direction queries and propose a new open shape-based strategy (OSS). OSS models the direction region as an open shape and converts the processing of the direction predicates into the processing of topological operations between open shapes and closed geometry objects. The proposed strategy OSS makes it unnecessary to know the boundary of the embedding world and also eliminates the computation related to the world boundary. OSS reduces both I/O and CPU costs by greatly improving the filtering effectiveness. Our experimental evaluation shows that OSS consistently outperforms classical range query strategies (RQS) while the degree of performance improvement varies by several parameters. Experimental results also demonstrate that OSS is more scalable than RQS for large data sets.     

Authenticated indexing for outsourced spatial databases

In spatial database outsourcing, a data owner delegates its data management tasks to a location-based service (LBS), which indexes the data with an authenticated data structure (ADS). The LBS receives queries (ranges, nearest neighbors) originating from several clients/subscribers. Each query initiates the computation of a verification object (VO) based on the ADS. The VO is returned to the client that can verify the result correctness using the public key of the owner. Our first contribution is the MR-tree, a space-efficient ADS that supports fast query processing and verification. Our second contribution is the MR*-tree, a modified version of the MR-tree, which significantly reduces the VO size through a novel embedding technique. Finally, whereas most ADSs must be constructed and maintained by the owner, we outsource the MR- and MR*-tree construction and maintenance to the LBS, thus relieving the owner from this computationally intensive task.     

Clustering multidimensional sequences in spatial and temporal databases

Many environmental, scientific, technical or medical database applications require effective and efficient mining of time series, sequences or trajectories of measurements taken at different time points and positions forming large temporal or spatial databases. Particularly the analysis of concurrent and multidimensional sequences poses new challenges in finding clusters of arbitrary length and varying number of attributes. We present a novel algorithm capable of finding parallel clusters in different subspaces and demonstrate our results for temporal and spatial applications. Our analysis of structural quality parameters in rivers is successfully used by hydrologists to develop measures for river quality improvements.

Scalable visibility color map construction in spatial databases

Recent advances in 3D modeling provide us with real 3D datasets to answer queries, such as “What is the best position for a new billboard?” and “Which hotel room has the best view?” in the presence of obstacles. These applications require measuring and differentiating the visibility of an object (target) from different viewpoints in a dataspace, e.g., a billboard may be seen from many points but is readable only from a few points closer to it. In this paper, we formulate the above problem of quantifying the visibility of (from) a target object from (of) the surrounding area with a visibility color map (VCM). A VCM is essentially defined as a surface color map of the space, where each viewpoint of the space is assigned a color value that denotes the visibility measure of the target from that viewpoint. Measuring the visibility of a target even from a single viewpoint is an expensive operation, as we need to consider factors such as distance, angle, and obstacles between the viewpoint and the target. Hence, a straightforward approach to construct the VCM that requires visibility computation for every viewpoint of the surrounding space of the target is prohibitively expensive in terms of both I/Os and computation, especially for a real dataset comprising thousands of obstacles. We propose an efficient approach to compute the VCM based on a key property of the human vision that eliminates the necessity for computing the visibility for a large number of viewpoints of the space. To further reduce the computational overhead, we propose two approximations; namely, minimum bounding rectangle and tangential approaches with guaranteed error bounds. Our extensive experiments demonstrate the effectiveness and efficiency of our solutions to construct the VCM for real 2D and 3D datasets.     

Approximate range query processing in spatial network databases

Spatial range query is one of the most common queries in spatial databases, where a user invokes a query to find all the surrounding interest objects. Most studies in range search consider Euclidean distances to retrieve the result in low cost, but with poor accuracy (i.e., Euclidean distance less than or equal network distance). Thus, researchers show that range search in network distance retrieves the results with high accuracy but with a vast amount of network distance computations. However, both of these techniques retrieve all objects in a given radius with a high number of false hits. Yet, in many situations, retrieving all objects is not necessary, especially when there are already enough objects closer to the query point. Also, when the radius of the search increases, a demotion in the performance will occur. Hence, approximate results are valuable just as the exact result, and approximate results can be obtained much faster than the exact result and are less costly. In this paper, we propose two approximate range search methods in spatial road network, namely approximate range Euclidean restriction and approximate range network expansion, to reduce the number of false hits and the number of network distance computations in a considerable manner. After the verification, these two methods are shown to be robust and accurate.     

Uniform generation in spatial constraint databases and applications

We study the efficient approximation of queries in linear constraint databases using sampling techniques. We define the notion of an almost uniform generator for a generalized relation and extend the classical generator of Dyer, Frieze and Kannan for convex sets to the union and the projection of relations. For the intersection and the difference, we give sufficient conditions for the existence of such generators. We show how such generators give relative estimations of the volume and approximations of generalized relations as the composition of convex hulls obtained from the samples.     

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

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

Exploiting spatial indexes for semijoin-based join processing indistributed spatial databases

In a distributed spatial database system, a user may issue a query that relates two spatial relations not stored at the same site. Because of the sheer volume and complexity of spatial data, spatial joins between two spatial relations at different sites are expensive in terms of computational and transmission costs. In this paper, we address the problems of processing spatial joins in a distributed environment. We propose a semijoin-like operator, called the spatial semijoin, to prune away objects that do not contribute to the join result. This operator also reduces both the transmission and local processing costs for a later join operation. However, the cost of the elimination process must be taken into account, and we consider approaches to minimize these overheads. We also study and compare two families of distributed join algorithms that are based on the spatial semijoin operator. The first is based on multi-dimensional approximations obtained from an index such as the R-tree, and the second is based on single-dimensional approximations obtained from object mapping. We have conducted experiments on real data sets and report the results in this paper     

An approximate algorithm for top-k closest pairs join query in large high dimensional data

In this paper we present a novel approximate algorithm to calculate the top-k closest pairs join query of two large and high dimensional data sets. The algorithm has worst case time complexity and space complexity and guarantees a solution within a factor of the exact one, where t  {1, 2, … , ∞} denotes the Minkowski metrics L_t of interest and d the dimensionality. It makes use of the concept of space filling curve to establish an order between the points of the space and performs at most d + 1 sorts and scans of the two data sets. During a scan, each point from one data set is compared with its closest points, according to the space filling curve order, in the other data set and points whose contribution to the solution has already been analyzed are detected and eliminated. Experimental results on real and synthetic data sets show that our algorithm behaves as an exact algorithm in low dimensional spaces; it is able to prune the entire (or a considerable fraction of the) data set even for high dimensions if certain separation conditions are satisfied; in any case it returns a solution within a small error to the exact one.     

城市空间信息数据库升级换代的实践

文章针对城市规划信息系统的建设特点，结合了广州城市规划信息系统中城市基础地理信息数据库建设的具体实践，详细介绍了城市规划信息系统中基础地理信息数据库建设的技术方法，并在此基础上提出了基于ArcSDE的地理信息数据库解决方案。     

面向外包空间数据库的范围查询验证

针对空间范围查询验证方法（例如VR-tree和MR-tree）普遍存在验证对象（VO）中包含大量的节点验证信息,造成服务器到客户端的传输代价较大以及客户端验证效率较低等问题,提出一种新的验证索引结构（ADS）MGR-tree。首先利用拆分思想,通过在Grid-tree的叶子节点中嵌入R-tree,并结合Merkle哈希树的验证方法,极大地减小VO的大小,提高查询和验证的效率。在此基础上,利用Hilbert曲线降维的特性,构建了优化的索引结构MHGR-tree,并提出一种过滤策略,进一步提高验证的效率。实验结果表明,所提方法具有更好的表现。在最好情况下,MHGR的VO大小和验证时间仅为MR的63%和19%。     

Trip planning queries with location privacy in spatial databases

Privacy has become a major concern for the users of location-based services (LBSs) and researchers have focused on protecting user privacy for different location-based queries. In this paper, we propose techniques to protect location privacy of users for trip planning (TP) queries, a novel type of query in spatial databases. A TP query enables a user to plan a trip with the minimum travel distance, where the trip starts from a source location, goes through a sequence of points of interest (POIs) (e.g., restaurant, shopping center), and ends at a destination location. Due to privacy concerns, users may not wish to disclose their exact locations to the location-based service provider (LSP). In this paper, we present the first comprehensive solution for processing TP queries without disclosing a user’s actual source and destination locations to the LSP. Our system protects the user’s privacy by sending either a false location or a cloaked location of the user to the LSP but provides exact results of the TP queries. We develop a novel technique to refine the search space as an elliptical region using geometric properties, which is the key idea behind the efficiency of our algorithms. To further reduce the processing overhead while computing a trip from a large POI database, we present an approximation algorithm for privacy preserving TP queries. Extensive experiments show that the proposed algorithms evaluate TP queries in real time with the desired level of location privacy.     

A taxonomy for moving object queries in spatial databases

In the past decade, many works have focused on the development of moving object database indexing and querying. Most of those works have concentrated on the common spatial queries which are used with static objects as well. However, moving objects have different features from static objects which may lead to a variety of queries. Therefore, it is important to understand the full spectrum of moving object queries, even before starting to build an index structure for such objects. The aim of this paper is to provide a complete picture of the capabilities of moving object queries. Thus motivated, in this paper we propose a taxonomy of moving object queries, comprising five perspectives: (i) Location perspective, (ii) Motion perspective, (iii) Object perspective, (vi) Temporal perspective and (v) Patterns perspective. These give an overall view of what moving object queries are about. In this work, each perspective is described and examples are given.     

Continuous visible nearest neighbor query processing in spatial databases

In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CVNN query returns a set of \({\langle p, R\rangle}\) tuples such that \({p \in P}\) is the nearest neighbor to every point r along the interval \({R \subseteq q}\) as well as p is visible to r. Note that p may be NULL, meaning that all points in P are invisible to all points in R due to the obstruction of some obstacles in O. In contrast to existing continuous nearest neighbor query, CVNN retrieval considers the impact of obstacles on visibility between objects, which is ignored by most of spatial queries. We formulate the problem, analyze its unique characteristics, and develop efficient algorithms for exact CVNN query processing. Our methods (1) utilize conventional data-partitioning indices (e.g., R-trees) on both P and O, (2) tackle the CVNN search by performing a single query for the entire query line segment, and (3) only access the data points and obstacles relevant to the final query result by employing a suite of effective pruning heuristics. In addition, several interesting variations of CVNN queries have been introduced, and they can be supported by our techniques, which further demonstrates the flexibility of the proposed algorithms. A comprehensive experimental evaluation using both real and synthetic data sets has been conducted to verify the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms.