Star-tree: An efficient self-adjusting index for moving objects

Conference Paper

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, can be answered efficiently. A novel feature of the index is that it is self-adjusting in the sense that it re-organizes itself locally whenever its query performance deteriorates. The index provides tradeoffs between storage and query performance and between time spent in updating the index and in answering queries. We present detailed performance studies and 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.

Full Text

Duke Authors

Cited Authors

  • Procopiuc, CM; Agarwal, PK; Har-Peled, S

Published Date

  • January 1, 2002

Published In

Volume / Issue

  • 2409 /

Start / End Page

  • 178 - 193

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540439773

Digital Object Identifier (DOI)

  • 10.1007/3-540-45643-0_14

Citation Source

  • Scopus