Boundary-Based Time Partitioning with Flattened R-Tree for Indexing Ubiquitous Objects

摘要

The advances of wireless communication technologies, personal locator technology, and global positioning systems enable a wide range of location-aware services. To enable the services, a number of spatiotemporal access methods have been proposed for handling timestamp and time interval queries. However, the performance of the existing methods of a single index structure quickly degrades as time progresses. To overcome the problem, we propose to employ time-based partitioning on the R-tree called time boundary-based partitioning with flattened R-tree (BPR-Tree). The proposed scheme employs a new insertion policy to reduce the height of the tree and a time grouping method in order to minimize the search time of various queries. Extensive computer simulation reveals that the proposed scheme significantly outperforms the existing schemes.