@TECHREPORT{R-96-03,
PSURL = {/publications/cgi-bin/tr-fetch.pl?r-96-03+ps},
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-96-03+abstr},
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.
},
NUMBER = {R-96-03},
INSTITUTION = ida,
ADDRESS = idaaddr,
YEAR = {1996},
AUTHOR = {Lin, Ling and Risch, Tore and Badal, Dushan},
EMAIL = {linli@ida.liu.se},
TITLE = {Indexing Interpolated Time Sequences
}