String Indexing for Top-k Close Consecutive Occurrences
| Autor: | Bille, Philip, Gørtz, Inge Li, Pedersen, Max Rishøj, Rotenberg, Eva, Steiner, Teresa Anna |
|---|---|
| Přispěvatelé: | Saxena, Nitin, Simon, Sunil |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science pattern matching Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) Consecutive occurrences String indexing Theory of computation → Pattern matching Pattern matching Theoretical Computer Science consecutive occurrences Theory of computation → Data structures design and analysis |
| Zdroj: | Bille, P, Gørtz, I L, Pedersen, M R, Rotenberg, E & Steiner, T A 2020, String indexing for top-k close consecutive occurrences . in N Saxena & S Simon (eds), Proceedings of 40 th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science ., 14, Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Virtual, Goa, India, 14/12/2020 . https://doi.org/10.4230/LIPIcs.FSTTCS.2020.14 Bille, P, Gørtz, I L, Pedersen, M R, Rotenberg, E & Steiner, T A 2022, ' String indexing for top-k close consecutive occurrences ', Theoretical Computer Science, vol. 927, pp. 133-147 . https://doi.org/10.1016/j.tcs.2022.06.004 |
| DOI: | 10.4230/lipics.fsttcs.2020.14 |
| Popis: | The classic string indexing problem is to preprocess a string $S$ into a compact data structure that supports efficient subsequent pattern matching queries, that is, given a pattern string $P$, report all occurrences of $P$ within $S$. In this paper, we study a basic and natural extension of string indexing called the string indexing for top-$k$ close consecutive occurrences problem (SITCCO). Here, a consecutive occurrence is a pair $(i,j)$, $i < j$, such that $P$ occurs at positions $i$ and $j$ in $S$ and there is no occurrence of $P$ between $i$ and $j$, and their distance is defined as $j-i$. Given a pattern $P$ and a parameter $k$, the goal is to report the top-$k$ consecutive occurrences of $P$ in $S$ of minimal distance. The challenge is to compactly represent $S$ while supporting queries in time close to length of $P$ and $k$. We give two time-space trade-offs for the problem. Let $n$ be the length of $S$, $m$ the length of $P$, and $\epsilon\in(0,1]$. Our first result achieves $O(n\log n)$ space and optimal query time of $O(m+k)$, and our second result achieves linear space and query time $O(m+k^{1+\epsilon})$. Along the way, we develop several techniques of independent interest, including a new translation of the problem into a line segment intersection problem and a new recursive clustering technique for trees. Comment: Fixed typos, minor changes |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|