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
