Subsequence Search in Event-Interval Sequences

Orestis Kostakis, Aristides Gionis

Abstract

We study the problem of subsequence search in databases of event-interval sequences, or e-sequences. In contrast to sequences of instantaneous events, e-sequences contain events that have a duration. In Information Retrieval applications, e-sequences are used for American Sign Language. We show that the subsequence-search problem is NP-hard and provide an exact (worst-case exponential) algorithm. We extend our algorithm to handle different cases of subsequence matching with errors. We then propose the Relation Index, a scheme for speeding up exact retrieval, which we benchmark against several indexing schemes.
BibTeX
@inproceedings{kostakis2015subsequence,
  author = {Orestis Kostakis and Aristides Gionis},
  title = {{Subsequence Search in Event-Interval Sequences}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2015},
  doi = {10.1145/2766462.2767778},
}

Loading related content...

Figure