License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2022.4
URN: urn:nbn:de:0030-drops-161312
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16131/
Bille, Philip ;
Gørtz, Inge Li ;
Mozes, Shay ;
Steiner, Teresa Anna ;
Weimann, Oren
The Fine-Grained Complexity of Episode Matching
Abstract
Given two strings S and P, the Episode Matching problem is to find the shortest substring of S that contains P as a subsequence. The best known upper bound for this problem is Õ(nm) by Das et al. (1997), where n,m are the lengths of S and P, respectively. Although the problem is well studied and has many applications in data mining, this bound has never been improved. In this paper we show why this is the case by proving that no O((nm)^{1-ε}) algorithm (even for binary strings) exists, unless the Strong Exponential Time Hypothesis (SETH) is false.
We then consider the indexing version of the problem, where S is preprocessed into a data structure for answering episode matching queries P. We show that for any τ, there is a data structure using O(n+(n/(τ)) ^k) space that answers episode matching queries for any P of length k in O(k⋅ τ ⋅ log log n) time. We complement this upper bound with an almost matching lower bound, showing that any data structure that answers episode matching queries for patterns of length k in time O(n^δ), must use Ω(n^{k-kδ-o(1)}) space, unless the Strong k-Set Disjointness Conjecture is false. Finally, for the special case of k = 2, we present a faster construction of the data structure using fast min-plus multiplication of bounded integer matrices.
BibTeX - Entry
@InProceedings{bille_et_al:LIPIcs.CPM.2022.4,
author = {Bille, Philip and G{\o}rtz, Inge Li and Mozes, Shay and Steiner, Teresa Anna and Weimann, Oren},
title = {{The Fine-Grained Complexity of Episode Matching}},
booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
pages = {4:1--4:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-234-1},
ISSN = {1868-8969},
year = {2022},
volume = {223},
editor = {Bannai, Hideo and Holub, Jan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16131},
URN = {urn:nbn:de:0030-drops-161312},
doi = {10.4230/LIPIcs.CPM.2022.4},
annote = {Keywords: Pattern matching, fine-grained complexity, longest common subsequence}
}
|
Keywords: |
|
Pattern matching, fine-grained complexity, longest common subsequence |
|
Collection: |
|
33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
22.06.2022 |
