Home Bookmarks Papers Blog

STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects

Cecilia M. Procopiuc, Pankaj K. Agarwal, and Sariel Har-Peled.


We present a new technique called, STAR-tree, based on R*-Tree for indexing a set of moving points so that various queries, including range queries, time-slice queries, and nearest-neighbor queries, based on their current or future positions. The index provides tradeoffs between storage and query performance and between time spent in updating the index and in answering queries, by combining techniques from computational geometry and spatial databases. We present performance studies that compare our methods with the existing ones under a varying type of data sets and queries. Our experiments show that the index proposed here performs considerably better than the previously known ones.
Postscript

Animations


Last updated: Tue Feb 27 22:50:59 CST 2001