Please use this identifier to cite or link to this item:
Title: IMPACT: A twin-index framework for efficient moving object query processing
Authors: Cui, B.
Lin, D.
Tan, K.-L. 
Keywords: Index
KNN query
Main memory
Moving object
Range query
Issue Date: 2006
Citation: Cui, B., Lin, D., Tan, K.-L. (2006). IMPACT: A twin-index framework for efficient moving object query processing. Data and Knowledge Engineering 59 (1) : 63-85. ScholarBank@NUS Repository.
Abstract: With the rapid advancement in wireless communications and positioning techniques, it is now feasible to track the positions of moving objects. However, existing indexes and associated algorithms, which are usually disk-based, are unable to keep up with the high update rate while providing speedy retrieval at the same time. Since main memory is much faster than disk, efficient management of moving-object database can be achieved through aggressive use of main memory. In this paper, we propose an integrated memory partitioning and activity conscious twin-index (IMPACT) framework where the moving object database is indexed by a pair of indexes based on the properties of the objects' movement-a main-memory structure manages active objects while a disk-based index handles inactive objects. As objects become active (or inactive), they dynamically migrate from one structure to the other. In the worst case that each time an object need to be migrated to the disk, which means each update may incur a disk access, the performance of IMPACT degrades to be the same as the disk-based index structures. Moreover, the main memory is also organized into two partitions-one for the main memory index, and the other as buffers for the frequently accessed nodes of the disk-based index. We also presented the detailed algorithms for different operations and a cost model to estimate the optimal memory allocation. Our analytical and experimental results show that the proposed IMPACT framework achieves significant performance improvement over the traditional indexing scheme. © 2005 Elsevier B.V. All rights reserved.
Source Title: Data and Knowledge Engineering
ISSN: 0169023X
DOI: 10.1016/j.datak.2005.07.008
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 12, 2019


checked on Feb 12, 2019

Page view(s)

checked on Dec 29, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.