Streaming periodicity with mismatches, wildcards, and edits
Taha El Ghazi, Tatiana Starikovskaya · 2025
Read Streaming periodicity with mismatches, wildcards, and edits by Taha El Ghazi, Tatiana Starikovskaya (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-14898.txt.
Introduction
Taha El Ghazi and Tatiana Starikovskaya detect repeating patterns in data streams that arrive once and cannot be stored, in a 2025 theoretical computer science paper. Real data is noisy, so repetitions come with mismatches, wildcards, and small edits. Their problem: given a long string, find shifts where the prefix and suffix of matching length are close under a chosen distance.
Earlier streaming work handled Hamming distance, which counts mismatched positions. The authors combine a compact Hamming-distance sketch with a structural description of near-matches between a pattern and a text. The combination yields a leaner streaming method for finding periods under Hamming distance. As a corollary, periods can also be detected when the string contains wildcards, symbols that match anything. The results tighten what streaming algorithms can certify about noisy repetitions.
Catalog record
| CREATOR | Taha El Ghazi, Tatiana Starikovskaya |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-14898
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Streaming periodicity with mismatches, wildcards, and edits Taha El Ghazi, Tatiana Starikovskaya Abstract In this work, we study the problem of detecting periodic trends in strings. While detecting exact periodicity has been studied extensively, real-world data is often noisy, where small deviations or mismatches occur between repetitions. This work focuses on a generalized approach to period detection that efficiently handles noise. Given a string S S of length n n , the task is to identify integers p p such that the prefix and the suffix of S S , each of length n − p + 1 n-p+1 , are similar under a given distance measure. Ergün et al. [APPROX-RANDOM 2017] were the first to study this problem in the streaming model under the Hamming distance. In this work, we combine, in a non-trivial way, the Hamming distance sketch of Clifford et al. [SODA 2019] and the structural description of the k k -mismatch occurrences of a pattern in a text by Charalampopoulos et al. [FOCS 2020] to present a more efficient streaming algorithm for period detection under the Hamming distance. As a corollary, we derive a streaming algorithm for detecting periods of strings which may contain wildcards, a special symbol that match any character of the alphabet. Our algorithm is not only more efficient than that of Ergün et al. [TCS 2020], but it also operates without their assumption that the string must be free of wildcards in its final characters. Additionally, we introduce the first two-pass streaming algorithm for computing periods under the edit distance by leveraging and extending the Bhattacharya–Koucký’s grammar decomposition technique [STOC 2023]. DIENS, École normale supérieure de Paris, PSL Research University, France DIENS, École normale supérieure de Paris, PSL Research University, [email protected] ccs Theory of computation Pattern matching keywords approximate periods, pattern matching, streaming algorithms † † runningauthor: T. El Ghazi and T. Starikovskaya † † copyright: Taha El Ghazi and Tatiana Starikovskaya † † funding: Partially supported by the grant ANR-20-CE48-0001 from the French National Research Agency (ANR) and a Royal Society International Exchanges Award. † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction In this work, we consider the problem of computing periodic trends in strings. Informally, a string has period p if its prefix of length n-p+1 equals its suffix of length n-p+1 . Alternatively, a string has period p if it equals its prefix of length p repeated a (possibly, fractional) number of times. The problem of detecting periodic trends in strings has numerous practical applications, including fields like astronomy, financial analytics, and meteorology (see e.g. [ 11 ] ). The nature and the volume of the data in the applications ask for algorithms able to process the input in very little space and in (almost) real time, such as streaming algorithms. In the streaming setting, we assume that the input string arrives one character at a time and account for all space used, even for the space used to store information about the input data, which results in ultra-efficient algorithms. The first streaming algorithm for detecting exact periods of a stream of length n was given by Ergün, Jowhari, and Sağlam [ 14 ] , who presented an algorithm with O(\log^{2}n) space. 1 1 1 Hereafter, the space is measured in bits. While the problem of detecting exact periodicity is fundamental to string processing, in practice data is rarely exactly periodic. For example, a string abcabcabaabaaba is clearly repetitive, but does not have a small exact period in the sense above. To account for these variations in natural data, Ergün, Jowhari, and Sağlam [ 14 ] proposed another streaming algorithm, which allows for approximately computing the Hamming distance (the number of mismatches) between a stream and a string with period p , for a given integer p . Their algorithm computes the distance with an approximation factor 2+\varepsilon in space \tilde{O}(1/\varepsilon^{2}) . A disadvantage of this algorithm is that p must be known in advance, and knowing p approximately will not suffice. Later, Ergün, Grigorescu, Azer, and Zhou [ 12 ] suggested a different version of this problem: given a string of length n and an integer k , they asked for all integer p such that the Hamming distance between the string and its copy shifted by p is at most k (see Section 2 for a definition). They called such p k -mismatch periods . They proved that for computing all k -mismatch periods of a streaming string of length n one needs \Omega(n) space and that for computing all k -mismatch periods in [1,n/2] , one needs \Omega(k\log n) space. On the other hand, prior work [ 12 , 15 ] claimed a streaming algorithm that, given a string of length n , computes all its k -mismatch periods in [1,n/2] using only O(k^{4}\log^{9}n) space. However, we found significant gaps in the proof of correctness. Many key arguments are only briefly outlined in both the conference version [ 12 ] and the longer arXiv manuscript [ 15 ] , and as confirmed in private communication with the authors, a full journal version of the paper has not been published. In particular, [ 15 , Theorem 28] is proved only for the case when the string has two distinct k -mismatch periods, and is stated to generalize easily to the case when the string has more than two distinct periods. We believe this generalization does not hold; see Appendix C for a detailed explanation. Finally, in a different work [ 13 ] Ergün, Grigorescu, Azer, and Zhou considered the problem of computing periods of incomplete streaming data, where some characters are replaced with wildcards, a special symbol that matches each character of the alphabet. We say that a wildcard-containing string T has an integer period p if T shifted by p positions matches itself. They showed that a streaming algorithm which computes all periods of an n -length string with wildcards requires \Omega(n) space. Conversely, they demonstrated a streaming algorithm which given a string T with k wildcards computes all its periods p\leq n/2 under condition that there are no wildcards in the last p characters of T . The algorithm uses O(k^{3}\polylog n) space. They also showed that for k=o(\sqrt{n}) , such an algorithm must use \Omega(k\log n) space. Our results. In this work, we continue the study initiated by Ergün, Grigorescu, Azer, and Zhou [ 12 ] . We first give a streaming algorithm for computing the k -mismatch periods of a string ( Theorem 10 ), providing full details and improving over the claimed space bound of Ergün, Grigorescu, Azer, and Zhou [ 12 ] by a factor of k^{2}\log^{5}n . As an almost immediate corollary, and our second contribution, we obtain a similar result for computing periods of a string with few wildcards ( Theorem 2 ). Specifically, we both improve the complexity of the algorithm by Ergün, Grigorescu, Azer, and Zhou [ 13