Time responsive external data structures for moving points


Conference Paper

© Springer-Verlag Berlin Heidelberg 2001. We develop external data structures for storing points in one or two dimensions, each moving along a linear trajectory, so that a range query at a given time tq can be answered efficiently. The novel feature of our data structures is that the number of I/Os required to answer a query depends not only on the size of the data set and on the number of points in the answer but also on the difference between tq and the current time; queries close to the current time are answered fast, while queries that are far away in the future or in the past may take more time.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Arge, L; Vahrenhold, J

Published Date

  • January 1, 2001

Published In

Volume / Issue

  • 2125 /

Start / End Page

  • 50 - 61

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540424237

International Standard Book Number 13 (ISBN-13)

  • 9783540424239

Digital Object Identifier (DOI)

  • 10.1007/3-540-44634-6_6

Citation Source

  • Scopus