ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Indexing Values of Time Sequences.

Ling Lin, Tore Risch, Martin Sköld, Dushan Z. Badal: Indexing Values of Time Sequences. CIKM 1996: 223-232
@inproceedings{DBLP:conf/cikm/LinRSB96,
  author    = {Ling Lin and
               Tore Risch and
               Martin Sk{\"o}ld and
               Dushan Z. Badal},
  title     = {Indexing Values of Time Sequences},
  booktitle = {CIKM '96, Proceedings of the Fifth International Conference on
               Information and Knowledge Management, November 12 - 16, 1996,
               Rockville, Maryland, USA},
  publisher = {ACM},
  year      = {1996},
  pages     = {223-232},
  ee        = {db/conf/cikm/LinRSB96.html, http://doi.acm.org/10.1145/238355.238500},
  crossref  = {DBLP:conf/cikm/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
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 the time sequences (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.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

CIKM '96, Proceedings of the Fifth International Conference on Information and Knowledge Management, November 12 - 16, 1996, Rockville, Maryland, USA. ACM 1996
Contents BibTeX

Online Edition

Citation Page BibTeX

Referenced by

  1. Ling Lin, Tore Risch: Querying Continuous Time Sequences. VLDB 1998: 170-181
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
CIKM 1996 Proceedings, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:01:53 2009