Periodicity in Data Streams with Wildcards
| Autor: | Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou, Funda Ergün |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Sublinear function
String (computer science) Wildcard character 0102 computer and information sciences 02 engineering and technology computer.file_format Space (mathematics) 01 natural sciences Theoretical Computer Science Combinatorics Character (mathematics) Computational Theory and Mathematics 010201 computation theory & mathematics Theory of computation 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Suffix computer Streaming algorithm Mathematics |
| Zdroj: | Theory of Computing Systems. 64:177-197 |
| ISSN: | 1433-0490 1432-4350 |
| DOI: | 10.1007/s00224-019-09950-y |
| Popis: | We investigate the problem of detecting periodic trends within a string S of length n, arriving in the streaming model, containing at most k wildcard characters, where k = o(n). A wildcard character is a special character that can be assigned any other character. We say that S has wildcard-period p if there exists an assignment to each of the wildcard characters so that in the resulting stream the prefix of length n − p equals the suffix of length n − p. We present a two-pass streaming algorithm that computes wildcard-periods of S using $\mathcal {O}(k^{3} \text {polylog} n)$ bits of space, while we also show that this problem cannot be solved in sublinear space in one pass. We also give a one-pass randomized streaming algorithm that computes all wildcard-periods p of S with $p |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink