Nearest Neighbor （κNN） search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work...Nearest Neighbor （κNN） search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work on κNN retrieval for moving object trajectories. Motivated by this observation, this paper studies the problem of efficiently processing κNN （κ≥ 1） search on R-tree-like structures storing historical information about moving object trajectories. Two algorithms are developed based on best-first traversal paradigm, called BFPκNN and BFTκNN, which handle the κNN retrieval with respect to the static query point and the moving query trajectory, respectively. Both algorithms minimize the number of node access, that is, they perform a single access only to those qualifying nodes that may contain the final result. Aiming at saving main-memory consumption and reducing CPU cost further, several effective pruning heuristics are also presented. Extensive experiments with synthetic and real datasets confirm that the proposed algorithms in this paper outperform their competitors significantly in both efficiency and scalability.展开更多
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 ...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. Extensive experiments are conducted to demonstrate the effectiveness and efficiency of the proposed update strategies.展开更多
文摘Nearest Neighbor （κNN） search is one of the most important operations in spatial and spatio-temporal databases. Although it has received considerable attention in the database literature, there is little prior work on κNN retrieval for moving object trajectories. Motivated by this observation, this paper studies the problem of efficiently processing κNN （κ≥ 1） search on R-tree-like structures storing historical information about moving object trajectories. Two algorithms are developed based on best-first traversal paradigm, called BFPκNN and BFTκNN, which handle the κNN retrieval with respect to the static query point and the moving query trajectory, respectively. Both algorithms minimize the number of node access, that is, they perform a single access only to those qualifying nodes that may contain the final result. Aiming at saving main-memory consumption and reducing CPU cost further, several effective pruning heuristics are also presented. Extensive experiments with synthetic and real datasets confirm that the proposed algorithms in this paper outperform their competitors significantly in both efficiency and scalability.
基金supported by the National Science Council of Taiwan(Nos.NSC-102-2119-M-244-001 and MOST-103-2119-M-244-001)
文摘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. Extensive experiments are conducted to demonstrate the effectiveness and efficiency of the proposed update strategies.
