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

Abstract

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
PublisherSpringer
Pages178-193
Number of pages16
ISBN (Electronic)3540439773
DOIs
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)
Volume2409
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th International Workshop on Algorithm Engineering and Experiments, ALENEX 2002
CountryUnited States
CitySan Francisco
Period1/4/021/5/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this