Density-based spatial keyword querying

With the rocket development of the Internet, WWW(World Wide Web), mobile computing and GPS (Global Positioning System) services, location-based services like Web GIS (Geographical Information System) portals are becoming more and more popular. Spatial keyword queries over GIS spatial data receive much more attention from both academic and industry communities than ever before. In general, a spatial keyword query containing spatial location information and keywords is to locate a set of spatial objects that satisfy the location condition and keyword query semantics. Researchers have proposed many solutions to various spatial keyword queries such as top-K keyword query, reversed kNN keyword query, moving object keyword query, collective keyword query, etc. In this paper, we propose a density-based spatial keyword query which is to locate a set of spatial objects that not only satisfies the query’s textual and distance condition, but also has a high density in their area. We use the collective keyword query semantics to find in a dense area, a group of spatial objects whose keywords collectively match the query keywords. To efficiently process the density based spatial keyword query, we use an IR-tree index as the base data structure to index spatial objects and their text contents and define a cost function over the IR-tree indexing nodes to approximately compute the density information of areas. We design a heuristic algorithm that can efficiently prune the region according to both the distance and region density in processing a query over the IR-tree index. Experimental results on datasets show that our method achieves desired results with high performance.     

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.     

A Spatial Access-Oriented Implementation of a 3-D GIS Topological Data Model for Urban Entities

3-D analysis in GIS is still one of the most challenging topics for research. With the goal being to model possible movement within the built environment, this paper, therefore, proposes a new approach to handling connectivity relationships among 3-D objects in urban environments in order to implement spatial access analyses in 3-D space. To achieve this goal, this paper introduces a 3-D network data model called the geometric network model (GNM), which has been developed by transforming the combinatorial data model (CDM), representing a connectivity relationship among 3-D objects using a dual graph. For the transformation, this paper presents (1) an O(n ²) algorithm for computing a straight medial axis transformation (MAT), (2) the processes for transforming phenomena from 3-D CDM to 3-D GNM, and (3) spatial access algorithms for the 3-D geometric network based upon the Dijkstra algorithm. Using the reconstructed geometric network generated from the transformations, spatial queries based upon the complex connectivity relationships between 3-D urban entities are implemented using Dijkstra algorithm. Finally, the paper presents the results of an experimental implementation of a 3-D network data model (GNM) using GIS data of an area in downtown Columbus, Ohio.     

Continuous visible k nearest neighbor query on moving objects

A visible k nearest neighbor (Vk NN) query retrieves k objects that are visible and nearest to the query object, where “visible” means that there is no obstacle between an object and the query object. Existing studies on the Vk NN query have focused on static data objects. In this paper we investigate how to process the query on moving objects continuously. We propose an effective filtering-and-refinement framework for evaluating this type of queries. We exploit spatial proximity and visibility properties between the query object and data objects to prune search space under this framework. A detailed cost analysis and a comprehensive experimental study are conducted on the proposed framework. The results validate the effectiveness of the pruning techniques and verify the efficiency of the proposed framework. The proposed framework outperforms a straightforward solution by an order of magnitude in terms of both communication and computation costs.     

Continuous monitoring of range spatial keyword query over moving objects

In this paper, we propose an efficient solution for processing continuous range spatial keyword queries over moving spatio-textual objects (namely, CRSK-mo queries). Major challenges in efficient processing of CRSK-mo queries are as follows: (i) the query range is determined based on both spatial proximity and textual similarity; thus a straightforward spatial proximity based pruning of the search space is not applicable as any object far from a query location with a high textual similarity score can still be the answer (and vice versa), (ii) frequent location updates may invalidate a query result, and thus require frequent re-computing of the result set for any object updates. To address these challenges, the key idea of our approach is to exploit the spatial and textual upper bounds between queries and objects to form safe zones (at the client-side) and buffer regions (at the server-side), and then use these bounds to quickly prune objects and queries through smart in-memory data structures. We conduct extensive experiments with a synthetic dataset that verify the effectiveness and efficiency of our proposed algorithm.     

Indexing moving objects for directions and velocities queries

Moving object databases are required to support different types of queries with a large number of moving objects. New types of queries namely directions and velocity queries (DV queries), are to be supported and covered. The TPR-tree and its successors are efficient indexes that support spatio-temporal queries for moving objects. However, neither of them support the new DV queries. In this paper, we propose a new index for moving objects based on the TPR*-tree, named Direction and Velocity of TPR*-tree or DV-TPR*-tree, in order to build data a structure based on the spatial, direction and velocity domains. DV-TPR*-tree obtains an ideal distribution that supports and fulfils the new query types (DV queries). Extensive performance studies show that the query performance of DV-TPR*-tree outperforms the TPR-tree and its successors.     

Efficient Processing of Continual Range Queries for Location-Aware Mobile Services

Efficient processing of continual range queries is important in providing location-aware mobile services. In this paper, we study a new main memory-based approach to indexing continual range queries to support location-aware mobile services. The query index is used to quickly answer the following question continually: “Which moving objects are currently located inside the boundaries of individual queries?” We present a covering tile-based (COVET) query index. A set of virtual tiles are predefined, each with a unique ID. One or more of the virtual tiles are used to strictly cover the region defined by an individual range query. The query ID is inserted into the ID lists associated with the covering tiles. These covering tiles touch each other only at the edges. A COVET index maintains a mapping between a covering tile and all the queries that contain that tile. For any object position, search is conducted indirectly via the covering tiles. More importantly, a COVET-based query index allows query evaluation to take advantage of incremental changes in object locations. Computation can be saved for those objects that have not moved outside the boundaries of covering tiles. Simulations are conducted to evaluate the effectiveness of the COVET index and compare virtual tiles of different shapes and sizes.     

Voronoi-based multi-level range search in mobile navigation

Due to the universality and importance of range search queries processing in mobile and spatial databases as well as in geographic information system (GIS), numerous approaches on range search algorithms have been proposed in recent years. But ordinary range search queries focus only on a specific type of point objects. For queries which require to retrieve objects of interest locating in a particular region, ordinary range search could not get the expected results. In addition, most existing range search methods need to perform a searching on each road segments within the pre-defined range, which decreases the performance of range search. In this paper, we design a weighted network Voronoi diagram and propose a high-performance multilevel range search query processing that retrieves a set of objects locating in some specified region within the searching range. The experimental results show that our proposed algorithm runs very efficiently and outperforms its main competitor.     

A usability-driven approach to the development of a 3D web-GIS environment

The main goal of this work is to provide an advanced visual environment where users that are not skilled for what concerns the computer science domain may compose queries related to those geographical phenomena for which the third dimension is a relevant feature. Visual queries are composed in a 3D environment accessible from the web where the users manipulate geographical objects, called 3D geometaphors. The geometaphors represent the operands of an underlying algebra characterized by a set of topological, directional and metrical operators; such operators are expressed in the query environment in terms of visual relationships between the geographical objects. The introduction of the third dimension for querying the geographical databases has challenged the authors with a number of important issues related to the area of visualization, navigation and object manipulation. According to the principles of usability engineering, the authors have built different prototypes based on a client-server architecture that have been iteratively evaluated by experts and final users in order to discover drawbacks and to improve the quality of the proposal. The result is a coordinated user-friendly 3D visual metaphor for querying GIS on the web, where all the elements needed for composing a query have a visual, easy to understand, counterpart.     

基于位置-文本关系的空间对象top-k查询与排序方法

针对普通的空间关键字查询通常会导致多查询结果的问题。本文提出了一种基于空间对象位置-文本相关度的top- k 查询与排序方法,用于获取与给定空间关键字查询在文本上相关且位置上相近的典型空间对象。该方法分为离线处理和在线查询处理2个阶段。在离线阶段,根据空间对象之间的位置相近性和文本相似性,度量任意一对空间对象之间的位置-文本关系紧密度。在此基础上,提出了基于概率密度的代表性空间对象选取算法,根据空间对象之间的位置-文本关系为每个代表性空间对象构建相应的空间对象序列。在线查询处理阶段,对于一个给定的空间关键字查询,利用Cosine相似度评估方法计算查询条件与代表性空间对象之间的相关度,然后使用阈值算法（threshold algorithm,TA）在预先创建的空间对象序列上快速选出top- k 个满足查询需求的典型空间对象。实验结果表明:提出的空间对象top- k 查询与排序方法能够有效地满足用户查询需求,并且具有较高的准确性、典型性和执行效率。     

An Object Model of Direction and Its Implications

Direction is an important spatial concept that is used in many fields such as geographic information systems(GIS) and image interpretation. It is also frequently used as a selection condition in spatial queries. Previous work has modeled direction as a relational predicate between spatial objects. Conversely, in this paper, we model direction as a new kind of spatial object using the concepts of vectors, points and angles. The basic approach is to model direction as a unit vector. This novel view of direction has several obvious advantages: Being modeled as a spatial object, a direction object can have its own attributes and operation set. Secondly, new spatial data types such as oriented spatial objects and open spatial objects can be defined at the abstract object level. Finally, the object view of direction makes direction reasoning easy and also reduces the need for a large number of inference rules. These features are important in spatial query processing and optimization. The applicability of the direction model is demonstrated by geographic query examples.     

Round-Eye: A system for tracking nearest surrounders in moving object environments

This paper presents “Round-Eye”, a system for tracking nearest surrounding objects (or nearest surrounders) in moving object environments. This system provides a platform for surveillance applications. The core part of this system is continuous nearest surrounder (NS) query that maintains views of the nearest objects at distinct angles from query points. This query differs from conventional spatial queries such as range queries and nearest neighbor queries as NS query considers both distance and angular aspects of objects with respect to a query point at the same time. In our system framework, a centralized server is dedicated (1) to collect location updates of both objects and queries, (2) to determine which NS queries are invalidated in presence of object/query location changes and corresponding result changes if any, and (3) to refresh the affected query answers. To enhance the system performance in terms of processing time and network bandwidth consumption, we propose various techniques, namely, safe region, partial query reevaluation, and incremental query result update. Through simulations, we evaluate our system with the proposed techniques over a wide range of settings.     

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.     

Continuous aggregate nearest neighbor queries

This paper addresses the problem of continuous aggregate nearest-neighbor (CANN) queries for moving objects in spatio-temporal data stream management systems. A CANN query specifies a set of landmarks, an integer k, and an aggregate distance function f (e.g., min, max, or sum), where f computes the aggregate distance between a moving object and each of the landmarks. The answer to this continuous query is the set of k moving objects that have the smallest aggregate distance f. A CANN query may also be viewed as a combined set of nearest neighbor queries. We introduce several algorithms to continuously and incrementally answer CANN queries. Extensive experimentation shows that the proposed operators outperform the state-of-the-art algorithms by up to a factor of 3 and incur low memory overhead.     

Spatial inverse query processing

Traditional spatial queries return, for a given query object q, all database objects that satisfy a given predicate, such as epsilon range and k-nearest neighbors. This paper defines and studies inverse spatial queries, which, given a subset of database objects Q and a query predicate, return all objects which, if used as query objects with the predicate, contain Q in their result. We first show a straightforward solution for answering inverse spatial queries for any query predicate. Then, we propose a filter-and-refinement framework that can be used to improve efficiency. We show how to apply this framework on a variety of inverse queries, using appropriate space pruning strategies. In particular, we propose solutions for inverse epsilon range queries, inverse k-nearest neighbor queries, and inverse skyline queries. Furthermore, we show how to relax the definition of inverse queries in order to ensure non-empty result sets. Our experiments show that our framework is significantly more efficient than naive approaches.     

Direction-aware KNN queries for moving objects in a road network

Recently more and more people focus on k-nearest neighbor (KNN) query processing over moving objects in road networks, e.g., taxi hailing and ride sharing. However, as far as we know, the existing k-nearest neighbor (KNN) queries take distance as the major criteria for nearest neighbor objects, even without taking direction into consideration. The main issue with existing methods is that moving objects change their locations and directions frequently over time, so the information updates cannot be processed in time and they run the risk of retrieving the incorrect KNN results. They may fail to meet users’ needs in certain scenarios, especially in the case of querying k-nearest neighbors for moving objects in a road network. In order to find the top k-nearest objects moving toward a query point, this paper presents a novel algorithm for direction-aware KNN (DAKNN) queries for moving objects in a road network. In this method, R-tree and simple grid are firstly used as the underlying index structure, where the R-tree is used for indexing the static road network and the simple grid is used for indexing the moving objects. Then, it introduces the notion of “azimuth” to represent the moving direction of objects in a road network, and presents a novel local network expansion method to quickly judge the direction of the moving objects. By considering whether a moving object is moving farther away from or getting closer to a query point, the object that is definitely not in the KNN result set is effectively excluded. Thus, we can reduce the communication cost, meanwhile simplify the computation of moving direction between moving objects and query point. Comprehensive experiments are conducted and the results show that our algorithm can achieve real-time and efficient queries in retrieving objects moving toward query point in a road network.

     

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

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

Buffer queries

A class of commonly asked queries in a spatial database is known as buffer queries. An example of such a query is to "find house-power line pairs that are within 50 meters of each other." A buffer query involves two spatial data sets and a distance d. The answer to this query are pairs of objects, one from each input set, that are within distance d of each other. Given nonpoint spatial objects, evaluation of buffer queries could be a costly operation, even when the numbers of objects in the input data sets are relatively small. This paper addresses the problem of how to evaluate this class of queries efficiently. A fundamental problem with buffer query evaluation is to find an efficient algorithm for solving the minimum distance (miniDist) problem for lines and regions. An efficient minDist algorithm, which only requires a subsequence of segments from each object to be examined, is derived. Finding a fast minDist algorithm is the first step in evaluating a buffer query efficiently. It is observed that many, and sometimes even most, candidates can be proven in the answer without resorting to the relatively expensive minDist operation. A candidate is first evaluated with a least expensive technique-called O-object filtering. If it fails, a more costly operation, called 1-object filtering, is applied. Finally, if both filterings fail, the most expensive minDist algorithm is invoked. To show the effectiveness of the these techniques, they are incorporated into the well-known tree join algorithm and tested with real-life as well as artificial data sets. Extensive experiments show that the proposed algorithm outperforms existing techniques by a wide margin in both execution time as well as IO accesses. More importantly, the performance gain improves drastically with the increase of distance values.     

Query processing over incomplete autonomous databases: query rewriting using learned data dependencies

Incompleteness due to missing attribute values (aka “null values”) is very common in autonomous web databases, on which user accesses are usually supported through mediators. Traditional query processing techniques that focus on the strict soundness of answer tuples often ignore tuples with critical missing attributes, even if they wind up being relevant to a user query. Ideally we would like the mediator to retrieve such possibleanswers and gauge their relevance by accessing their likelihood of being pertinent answers to the query. The autonomous nature of web databases poses several challenges in realizing this objective. Such challenges include the restricted access privileges imposed on the data, the limited support for query patterns, and the bounded pool of database and network resources in the web environment. We introduce a novel query rewriting and optimization framework QPIAD that tackles these challenges. Our technique involves reformulating the user query based on mined correlations among the database attributes. The reformulated queries are aimed at retrieving the relevant possibleanswers in addition to the certain answers. QPIAD is able to gauge the relevance of such queries allowing tradeoffs in reducing the costs of database query processing and answer transmission. To support this framework, we develop methods for mining attribute correlations (in terms of Approximate Functional Dependencies), value distributions (in the form of Naïve Bayes Classifiers), and selectivity estimates. We present empirical studies to demonstrate that our approach is able to effectively retrieve relevant possibleanswers with high precision, high recall, and manageable cost.