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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithm Engineering and Experiments
Subtitle of host publication4th InternationalWorkshop, ALENEX 2002, Revised Papers
EditorsDavid M. Mount, Clifford Stein
Number of pages16
ISBN (Electronic)3540439773
StatePublished - 2002
Event4th International Workshop on Algorithm Engineering and Experiments, ALENEX 2002 - San Francisco, United States
Duration: Jan 4 2002Jan 5 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other4th International Workshop on Algorithm Engineering and Experiments, ALENEX 2002
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Star-tree: An efficient self-adjusting index for moving objects'. Together they form a unique fingerprint.

Cite this