Techniques for Indexing and Querying Temporal Observations for a Collection of Objects
Files
Publication or External Link
Date
Authors
Advisor
Citation
DRUM DOI
Abstract
We consider the problem of dynamically indexing temporal observations
about a collection of objects, each observation consisting of a key
identifying the object, a list of attribute values and a timestamp
indicating the time at which these values were recorded. We make no
assumptions about the rates at which these observations are collected, nor
do we assume that the various objects have about the same number of
observations. We develop indexing structures that are almost linear in the
total number of observations available at any given time instant, and that
support dynamic insertions in polylogarithmic time. Moreover, these
structures allow the quick handling of queries to identify objects whose
attribute values fall within a certain range at every time instance of a
specified time interval. Provably good bounds are established.
(UMIACS-TR-2003-72)