**Dept. of Computer and Information science, Linköping University**

## IDA Technical Reports: abstract

*Generated: Thu, 03 Sep 2015 08:52:10 *

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.

**Goto (at Linköping University):**
```
CS Dept
TR Overview
```

*<webmaster@ida.liu.se>*