Subsequence Search in Event-Interval Sequences
Lists
Only you see this
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...