时空数据库中多个最近邻对象的查询算法

在时空数据库中,最近邻查询用于对某个查询对象,在被查询对象中找出离它最近的一个或多个对象。该文在TPR树这一时空索引的基础上,提出了一种高效的最近邻查询算法,能够支持移动对象的多个最近邻对象的查询,并在性能上也有所提高。     

An adaptive hashing technique for indexing moving objects

Although hashing techniques are widely used for indexing moving objects, they cannot handle the dynamic workload, e.g. the traffic at peak hour vs. that in the night. This paper proposes an adaptive hashing technique to support the dynamic workload efficiently. The proposed technique maintains two levels of the hashes, one for fast moving objects and the other for quasi-static objects. A moving object changes its level adaptively according to the degree of its movement. We also present the theoretical analysis and experimental results which show that the proposed approach is more suitable than the basic hashing under the dynamic workload.     

Designing a location update strategy for free-moving and network-constrained objects with varying velocity

Spatio-temporal databases aim at appropriately managing moving objects so as to support various types of queries. While much research has been conducted on developing query processing techniques, less effort has been made to address the issue of when and how to update location information of moving objects. Previous work shifts the workload of processing updates to each object which usually has limited CPU and battery capacities. This results in a tremendous processing overhead for each moving object. In this paper, we focus on designing efficient update strategies for two important types of moving objects, free-moving objects （FMOs） and network-constrained objects （NCOs）, which are classified based on object movement models. For FMOs, we develop a novel update strategy, namely the FMO update strategy （FMOUS）, to explicitly indicate a time point at which the object needs to update location information. As each object knows in advance when to update （meaning that it does not have to continuously check）, the processing overhead can be greatly reduced. In addition, the FMO update procedure （FMOUP） is designed to efficiently process the updates issued from moving objects. Similarly, for NCOs, we propose the NCO update strategy （NCOUS） and the NCO update procedure （NCOUP） to inform each object when and how to update location information. Exten- sive experiments are conducted to demonstrate the effectiveness and efficiency of the proposed update strategies.     

An efficient location update mechanism for continuous queries over moving objects

In a moving-object database system that supports continuous queries (CQ), an important problem is to keep the location data consistent with the actual locations of the entities being monitored, in order to produce correct query results. This goal is often difficult to achieve due to limited network resources. However, if an object is not required by any query, its value need not be refreshed. Based on this observation, we redefine the notion of temporal consistency of data items with respect to the query result, where only data items that are relevant to the CQs need to be fresh. To exploit this correctness definition, we develop an adaptive time-based update technique called query-result update (QRU). The advantage of this technique is that it identifies objects with different levels of significance to the correctness of query results. Locations of objects that have more impact to the query result are acquired more frequently than the ones that do not.     

Efficient mutual nearest neighbor query processing for moving object trajectories

Given a set D of trajectories, a query object q, and a query time extent Γ, a mutual (i.e., symmetric) nearest neighbor (MNN) query over trajectories finds from D, the set of trajectories that are among the k₁ nearest neighbors (NNs) of q within Γ, and meanwhile, have q as one of their k₂ NNs. This type of queries is useful in many applications such as decision making, data mining, and pattern recognition, as it considers both the proximity of the trajectories to q and the proximity of q to the trajectories. In this paper, we first formalize MNN search and identify its characteristics, and then develop several algorithms for processing MNN queries efficiently. In particular, we investigate two classes of MNN queries, i.e., MNN_P and MNN_T queries, which are defined with respect to stationary query points and moving query trajectories, respectively. Our methods utilize the batch processing and reusing technology to reduce the I/O cost (i.e., number of node/page accesses) and CPU time significantly. In addition, we extend our techniques to tackle historical continuous MNN (HCMNN) search for moving object trajectories, which returns the mutual nearest neighbors of q (for a specified k₁ and k₂) at any time instance of Γ. Extensive experiments with real and synthetic datasets demonstrate the performance of our proposed algorithms in terms of efficiency and scalability.     

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.     

Using compressed index structures for processing moving objects in large spatio-temporal databases

This paper develops a novel, compressed B⁺-tree based indexing scheme that supports the processing of moving objects in one-, two-, and multi- dimensional spaces. The past, current, and anticipated future trajectories of movements are fully indexed and well organized. No parameterized functions and geometric representations are introduced in our data model so that update operations are not required and the maintenance of index structures can be accomplished by basic insertion and deletion operations. The proposed method has two contributions. First, the spatial and temporal attributes of trajectories are accurately preserved and well organized into compact index structures with very efficient memory space utilization and storage requirement. Second, index maintenance overheads are more economical and query performance is more responsive than those of conventional methods. Both analytical and empirical studies show that our proposed indexing scheme outperforms the TPR-tree.     

Optimal subspace dimensionality for k-nearest-neighbor queries on clustered and dimensionality reduced datasets with SVD

Content based image retrieval represents images as N- dimensional feature vectors. The k images most similar to a target image, i.e., those closest to its feature vector, are determined by applying a k-nearest-neighbor (k-NN) query. A sequential scan of the feature vectors for k-NN queries is costly for a large number of images when N is high. The search space can be reduced by indexing the data, but the effectiveness of multidimensional indices is poor for high dimensional data. Building indices on dimensionality reduced data is one method to improve indexing efficiency. We utilize the Singular Value Decomposition (SVD) method to attain dimensionality reduction (DR) with minimum information loss for static data. Clustered SVD (CSVD) combines clustering with SVD to attain a lower normalized mean square error (NMSE) by taking advantage of the fact that most real-world datasets exhibit local rather than global correlations. The Local Dimensionality Reduction (LDR) method differs from CSVD in that it uses an SVD-friendly clustering method, rather than the k-means clustering method. We propose a hybrid method which combines the clustering method of LDR with the DR method of CSVD, so that the vector of the number of retained dimensions of the clusters is determined by varying the NMSE. We build SR-tree indices based on the vectors in the clusters to determine the number of accessed pages for exact k-NN queries (Thomasian et al., Inf Process Lett - IPL 94(6):247–252, 2005) (see Section A.3 versus the NMSE. Varying the NMSE a minimum cost can be found, because the lower cost of accessing a smaller index is offset with the higher postprocessing cost resulting from lower retrieval accuracy. Experimenting with one synthetic and three real-world datasets leads to the conclusion that the lowest cost is attained at NMSE ≈ 0.03 and between 1/3 and 1/2 of the number of dimensions are retained. In one case doubling the number of dimensions cuts the number of accessed pages by one half. The Appendix provides the requisite background information for reading this paper.

An approach to process continuous location-dependent queries on moving objects with support for location granules

Location-based services have attracted the attention of important research in the field of mobile computing. Specifically, different mechanisms have been proposed to process location-dependent queries. In the above mentioned context, it is usually assumed that the location data are expressed at a fine geographic precision. However, a different granularity may be more appropriate in certain situations. Thus, a location resolution higher than required may even be inconvenient or not understandable by the user (for example, if the user expects a city name as an answer and instead the system provides the latitude/longitude coordinates). Moreover, if the locations presented to the user need to be refreshed automatically as the objects move, it is obvious that maintaining up-to-date GPS-like geographic coordinates would be more expensive in terms of processing and communication. Unfortunately, the existing approaches assume queries whose locations are always given with maximum precision (i.e., GPS locations).In this paper, a distributed query processing approach that adapts itself to the level of the location resolution required is presented. Thus, it supports continuous location-dependent queries based on the required terminology for the locations, depending on the granularity used (e.g., GPS, cities, states, provinces, or any other predefined geographic area). For the above mentioned purpose, location granules can be defined to specify the semantics appropriate for the queries and/or the way the results should be presented. A prototype showing the functionality and benefits of the approach has been implemented and used in an extensive experimental evaluation. The proposal not only increases the flexibility and expressive power of the queries considerably but also performs efficiently.     

移动对象数据库中时空索引技术的研究

提出了基于移动对象运动轨迹的时空立方体模型,在该模型中,移动对象的运动轨迹按一定时间间隔划分,每段运动轨迹对应一个最小外接时空长方体,它是存储,访问的一个基本单位.基于该模型设计了相应的时空索引和时空查询算法.验证表明,模型在减少数据冗余和时空查询性能方面有较大提高.