Lin, L., Risch, T., and Badal, D. (1996). Indexing Values of Time Sequences. Technical Report LiTH-IDA-R-96-29, 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. Conventional indexes for time sequences are built on the time domain and cannot deal with inverse queries on a time sequence (i.e. computing the times when the values satisfy some conditions). To process an inverse query the entire time sequence has to be scanned. This paper presents a dynamic indexing technique on the value domain for large time sequences which can be implemented using regular ordered indexing techniques (e.g. B-trees). Our index (termed IP-index) dramatically improves the query processing time of inverse queries compared to linear scanning. For periodic time sequences that have a limited range and precision on their value domain (most time sequences have this property), the IP-index has an upper bound for insertion time and search time.
CS Dept TR Overview