An adaptive updating protocol for reducing moving object database workload

In the last decade, spatio-temporal database research focuses on the design of effective and efficient indexing structures in support of location-based queries such as predictive range queries and nearest neighbor queries. While a variety of indexing techniques have been proposed to accelerate the processing of updates and queries, not much attention has been paid to the updating protocol, which is another important factor affecting the system performance. In this paper, we propose a generic and adaptive updating protocol for moving object databases with less number of updates between objects and the database server, thereby reducing the overall workload of the system. In contrast to the approach adopted by most conventional moving object database systems where the exact locations and velocities last disclosed are used to predict their motions, we propose the concept of Spatio-temporal safe region to approximate possible future locations. Spatio-temporal safe regions provide larger space of tolerance for moving objects, freeing them from location and velocity updates as long as the errors remain predictable in the database. To answer predictive queries accurately, the server is allowed to probe the latest status of objects when their safe regions are inadequate in returning the exact query results. Spatio-temporal safe regions are calculated and optimized by the database server with two contradictory objectives: reducing update workload while guaranteeing query accuracy and efficiency. To achieve this, we propose a cost model that estimates the composition of active and passive updates based on historical motion records and query distribution. More system performance improvements can be obtained by cutting more updates from the clients, when the users of system are comfortable with incomplete but accuracy bounded query results. We have conducted extensive experiments to evaluate our proposal on a variety of popular indexing structures. The results confirm the viability, robustness, accuracy and efficiency of our proposed protocol.     

MOVIES: indexing moving objects by shooting index images

With the exponential growth of moving objects data to the Gigabyte range, it has become critical to develop effective techniques for indexing, updating, and querying these massive data sets. To meet the high update rate as well as low query response time requirements of moving object applications, this paper takes a novel approach in moving object indexing. In our approach, we do not require a sophisticated index structure that needs to be adjusted for each incoming update. Rather, we construct conceptually simple short-lived index images that we only keep for a very short period of time (sub-seconds) in main memory. As a consequence, the resulting technique MOVIES supports at the same time high query rates and high update rates, trading this property for query result staleness. Moreover, MOVIES is the first main memory method supporting time-parameterized predictive queries. To support this feature, we present two algorithms: non-predictive MOVIES and predictive MOVIES. We obtain the surprising result that a predictive indexing approach—considered state-of-the-art in an external-memory scenario—does not scale well in a main memory environment. In fact, our results show that MOVIES outperforms state-of-the-art moving object indexes such as a main-memory adapted B ^x -tree by orders of magnitude w.r.t. update rates and query rates. In our experimental evaluation, we index the complete road network of Germany consisting of 40,000,000 road segments and 38,000,000 nodes. We scale our workload up to 100,000,000 moving objects, 58,000,000 updates per second and 10,000 queries per second, a scenario at a scale unmatched by any previous work.     

Optimized algorithms for predictive range and KNN queries on moving objects

There have been many studies on management of moving objects recently. Most of them try to optimize the performance of predictive window queries. However, not much attention is paid to two other important query types: the predictive range query and the predictive k nearest neighbor query. In this article, we focus on these two types of queries. The novelty of our work mainly lies in the introduction of the Transformed Minkowski Sum, which can be used to determine whether a moving bounding rectangle intersects a moving circular query region. This enables us to use the traditional tree traversal algorithms to perform range and kNN searches. We theoretically show that our algorithms based on the Transformed Minkowski Sum are optimal in terms of the number of tree node accesses. We also experimentally verify the effectiveness of our technique and show that our algorithms outperform alternative 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.

     

A scalable constraint-based Q-hash indexing for moving objects

In this paper, we develop a Q-hash index structure to efficiently store the position of moving objects. An environment of moving objects contains continuously changing locations which are hard to index using traditional index structures such as R-trees, QuadTrees and their variants. In order to answer the queries accurately, one of the problems faced in storing these positions is the number of updates that have to be made to the database whenever locations change. The high maintenance overhead on updates leads to performance degradation of these index structures; additionally, it makes the database very bulky which results in very poor performance in terms of query execution time. One of the main objectives of the structure we propose is to minimize the number of updates to the database to an optimal number so that the accuracy and response time of the query result are not compromised and at the same time the number of wireless communications can be reduced. The indexing is done using a hashing technique where the hashing function makes use of a region based QuadTree structure. To improve the efficiency of the query processing our index structure helps us define constraints over speed, direction and location of the moving object at the device level which controls the number of updates. In addition, in order to answer different query types efficiently at all levels we propose a three-tier (moving object, regional server, central repository) architecture. Our extensive performance evaluation and comparison of the proposed technique concludes that our scheme outperforms existing Q + R-tree and QuadTree in terms of range query execution time by a high order of magnitude.     

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.     

Incremental Processing of Continual Range Queries over Moving Objects

Efficient processing of continual range queries over moving objects is critically important in providing location-aware services and applications. A set of continual range queries, each defining the geographical region of interest, can be periodically (re)evaluated to locate moving objects that are currently within individual query boundaries. We study a new query indexing method, called CES-based indexing, for incremental processing of continual range queries over moving objects. A set of containment-encoded squares (CES) are predefined, each with a unique ID. CESs are virtual constructs (VC) used to decompose query regions and to store indirectly precomputed search results. Compared with a prior VC-based approach, the number of VCs visited in a search operation is reduced from (4L²-1)/3 to log(L)+1, where L is the maximal side length of a VC. Search time is hence significantly lowered. Moreover, containment encoding among the CESs makes it easy to identify all those VCs that need not be visited during an incremental query (re)evaluation. We study the performance of CES-based indexing and compare it with a prior VC-based approach     

Nearest and reverse nearest neighbor queries for moving objects

With the continued proliferation of wireless communications and advances in positioning technologies, algorithms for efficiently answering queries about large populations of moving objects are gaining interest. This paper proposes algorithms for k nearest and reverse k nearest neighbor queries on the current and anticipated future positions of points moving continuously in the plane. The former type of query returns k objects nearest to a query object for each time point during a time interval, while the latter returns the objects that have a specified query object as one of their k closest neighbors, again for each time point during a time interval. In addition, algorithms for so-called persistent and continuous variants of these queries are provided. The algorithms are based on the indexing of object positions represented as linear functions of time. The results of empirical performance experiments are reported.     

Real-time continuous intersection joins over large sets of moving objects using graphic processing units

The Multiple Time Bucket Join (MTB-join) algorithm is the state of the art for processing the continuous intersection join (CI-join) query over moving objects. It considerably outperforms alternatives, but still falls short of real-time application performance requirements for large sets of moving objects. In this paper, we achieve real-time performance for the CI-join query over large sets of moving objects by exploiting the computational power of commodity graphics processing units (GPUs). We first analyze how the main characteristics of the MTB-join algorithm make it ill suited to GPUs and identify key challenges in designing efficient GPU-based algorithms for the query. We then address these challenges by developing the multi-layered grid join (MLG-join) algorithm which has the following key features: (i) memory locality friendly indexing, (ii) no dynamic memory allocation, (iii) in-place object updates, (iv) lock-free concurrent updates, and (v) massive parallelism. These features unleash the full potential of the memory bandwidth and parallel processing of GPUs. Furthermore, we conduct a theoretical analysis which can predict the pruning power of the MLG-join algorithm given certain parameter values used in the algorithm. This allows us to select optimal parameter values. Through extensive experimental results, we show that our analysis accurately models the MLG-join algorithm’s sensitivity to parameter values. The proposed MLG-join algorithm outperforms the MTB-join algorithm, and a GPU-based nested-loops join algorithm, by up to two orders of magnitude, and achieves real-time performance for CI-join queries on large sets of moving objects.     

Main Memory Evaluation of Monitoring Queries Over Moving Objects

In this paper we evaluate several in-memory algorithms for efficient and scalable processing of continuous range queries over collections of moving objects. Constant updates to the index are avoided by query indexing. No constraints are imposed on the speed or path of moving objects or fraction of objects that move at any moment in time. We present a detailed analysis of a grid approach which shows the best results for both skewed and uniform data. A sorting based optimization is developed for significantly improving the cache hit-rate. Experimental evaluation establishes that indexing queries using the grid index yields orders of magnitude better performance than other index structures such as R*-trees.     

Efficient Location Updates for Continuous Queries over Moving Objects

The significant overhead related to frequent location updates from moving objects often results in poor performance. As most of the location updates do not affect the query results, the network bandwidth and the battery life of moving objects are wasted. Existing solutions propose lazy updates, but such techniques generally avoid only a small fraction of all unnecessary location updates because of their basic approach (e.g., safe regions, time or distance thresholds). Furthermore, most prior work focuses on a simplified scenario where queries are either static or rarely change their positions. In this study, two novel efficient location update strategies are proposed in a trajectory movement model and an arbitrary movement model, respectively. The first strategy for a trajectory movement environment is the Adaptive Safe Region (ASR) technique that retrieves an adjustable safe region which is continuously reconciled with the surrounding dynamic queries. The communication overhead is reduced in a highly dynamic environment where both queries and data objects change their positions frequently. In addition, we design a framework that supports multiple query types (e.g., range and c-kNN queries). In this framework, our query re-evaluation algorithms take advantage of ASRs and issue location probes only to the affected data objects, without flooding the system with many unnecessary location update requests. The second proposed strategy for an arbitrary movement environment is the Partition-based Lazy Update (PLU, for short) algorithm that elevates this idea further by adopting Location Information Tables (LITs) which (a) allow each moving object to estimate possible query movements and issue a location update only when it may affect any query results and (b) enable smart server probing that results in fewer messages. We first define the data structure of an LIT which is essentially packed with a set of surrounding query locations across the terrain and discuss the mobile-side and server-side processes in correspondence to the utilization of LITs. Simulation results confirm that both the ASR and PLU concepts improve scalability and efficiency over existing methods.     

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.     

VGQ-Vor: extending virtual grid quadtree with Voronoi diagram for mobile k nearest neighbor queries over mobile objects

Performing mobile k nearest neighbor (MkNN) queries whilst also being mobile is a challenging problem. All the mobile objects issuing queries and/or being queried aremobile. The performance of this kind of query relies heavily on the maintenance of the current locations of the objects. The index used for mobile objects must support efficient update operations and efficient query handling. This study aims to improve the performance of the MkNN queries while reducing update costs. Our approach is based on an observation that the frequency of one region changing between being occupied or not by mobile objects is much lower than the frequency of the position changes reported by the mobile objects. We first propose an virtual grid quadtree with Voronoi diagram(VGQ-Vor), which is a two-layer index structure that indexes regions occupied by mobile objects in a quadtree and builds a Voronoi diagram of the regions. Then we propose a moving k nearest neighbor (kNN) query algorithm on the VGQ-Vor and prove the correctness of the algorithm. The experimental results show that the VGQ-Vor outperforms the existing techniques (Bx-tree, Bdual-tree) by one to three orders of magnitude in most cases.     

移动对象XML数据库的存储与索引

如何对移动对象的XML数据记录进行快速的查找,关键在于合理地存储模型与索引结构。为了减少时空条件索引时的文件I/O操作,提出一个移动对象XML数据存储模型（时空XML存储模型）,基于这个模型给出了通过一定时空条件对XML数据记录进行聚集的ATS（Append Track node to Spatial node）算法。针对3DR树的缺点与时态条件在移动对象索引中的重要性,提出了HSTR（Hashing-Spatio-Temporal-Rtree）与HC3DR（Hashing-Changing-3DRtree）两种复合索引结构,能够有效地支持涉及时空条件的查询。实验结果表明,时空XML存储模型与两种索引提高了查询效率。     

路网中移动对象快照K近邻查询处理

扩展了一种支持路网中移动对象的位置相关查询框架的功能,利用存在磁盘上的R树来存储网络连通性和一种基于内存的网格结构来维持移动对象的位置更新,提出了基于范围查询(MNDR)的快照K近邻查询算法(SKNN),对空间中的任意一条边,分析可能受影响的最大数量和最小数量的网格单元格,说明用于快照范围查询处理的搜索空间的最大范围,预估包含查询结果的子空间,使用这个子空间作为范围调用MNDR来有效地计算路网中查询点的KNN POI,降低I/O成本,缩短查询时间。通过实验对比,当规模扩展到数十万的移动对象时,SKNN比种有效查询处理空间网络数据的预计算方法S-GRID有更好大的系统吞吐量。     

基于Quadtree和Hash表的移动对象全时态索引

为解决大量移动对象位置频繁更新所带来的性能下降问题,提出一种基于改进的Quadtree和Hash表的QH全时态索引结构。这种新的索引结构可以支持移动对象全时态索引,在Hash表中通过存储移动对象指针来支持移动对象标识查询,并对Quadtree的叶子节点采用适时合并的方法来防范分支太深而造成的查询效率低下。实验证明,QH索引与TPR-tree相比,移动对象的更新效率更高、对象标识查询较优、范围查询性能相近。     

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

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

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.     

Continuous reverse k nearest neighbor monitoring on moving objects in road networks

Continuous reverse k nearest neighbor (CRkNN) monitoring in road networks has recently received increasing attentions. However, there is still a lack of efficient CRkNN algorithms in road networks up to now. In road networks, moving query objects and data objects are restricted by the connectivity of the road network and both the object–query distance and object–object distance updates affect the result of CRkNN queries. In this paper, we present a novel algorithm for continuous and incremental evaluation of CRkNN queries in road networks. Our method is based on a novel data structure called dual layer multiway tree (DLM tree) we proposed to represent the whole monitoring region of a CRkNN query q. We propose several lemmas to reduce the monitoring region of q and the number of candidate objects as much as possible. Moreover, by associating a variable NN_count with each candidate object, we can simplify the monitoring of candidate objects. There are a large number of objects roaming in a road network and many of them are irrelevant to a specific CRkNN query of a query object q. To minimize the processing extension, for a road in the network, we give an IQL list and an IQCL list to specify the set of query objects and data objects whose location updates should be maintained for CRkNN processing of query objects. Our CRkNN method consists of two phase: the initial result generating phase and incremental maintenance phase. In each phase, algorithms with high performance are proposed to make our CRkNN method more efficient. Extensive simulation experiments are conducted and the result shows that our proposed approach is efficient and scalable in processing CRkNN queries in road networks.