Lin, L., Risch, T., and Badal, D. (1996). Indexing Interpolated Time Sequences. Technical Report LiTH-IDA-R-96-03, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: A time sequence is a discrete sequence of values, e.g. temperature measurements, varying over time. By applying an interpolation function a discrete time sequence can be coerced into a continues function over time, F(t), which we call an interpolated time sequence. Many applications need to deal with querying interpolated time sequences. Simple queries involve finding F(t') for a given time point t', which are easy to support using regular ordered indexes. The main contribution of this paper is a new index structure, the interpolation index (IP-index) which supports efficient retrievals of those time points t where F(t) = v' for a given v', i.e. efficient computation of interpolated inverse queries, F-1(v'). Performance measures show that the IP-index radically improves the search time for interpolated inverse queries. It is also shown that the insertion time of the IP-index for most periodic time sequences has an upper limit, and for largely monotonic sequences it is logarithmic. Keywords: time sequences, indexing, temporal databases.
CS Dept TR Overview