A New Framework for Addressing Temporal Range Queries and Some Preliminary Results

Abstract

Given a set of $n$ objects, each characterized by $d$ attributes specified at $m$ fixed time instances, we are interested in the problem of designing space efficient indexing structures such that arbitrary temporal range search queries can be handled efficiently. When $m=1$, our problem reduces to the $d$-dimensional orthogonal search problem. We establish efficient data structures to handle several classes of the general problem. Our results include a linear size data structure that enables a query time of $O( \log n\log m/\log\log n + f)$ for one-sided queries when $d=1$, where $f$ is the number of objects satisfying the query. A similar result is shown for counting queries. We also show that the most general problem can results include a linear size data structure that enables a query time of $O( \log n\log m/\log\log n + f)$ for one-sided queries when $d=1$, where $f$ is the number of objects satisfying the query. A similar result is shown for counting queries. We also show that the most general problem can be solved with a polylogarithmic query time using nonlinear space data structures. Also UMIACS-TR-2003-08