Content Tags

There are no tags.

Periodicity in Data Streams with Wildcards.

RSS Source
Authors
Funda Ergun, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou

We investigate the problem of detecting periodic trends within a string $S$of length $n$, arriving in the streaming model, containing at most $k$ wildcardcharacters, where $k=o(n)$. A wildcard character is a special character thatcan be assigned any other character. We say $S$ has wildcard-period $p$ ifthere exists an assignment to each of the wildcard characters so that in theresulting stream the length $n-p$ prefix equals the length $n-p$ suffix. Wepresent a two-pass streaming algorithm that computes wildcard-periods of $S$using $\mathcal{O}(k^3\,\mathsf{polylog}\,n)$ bits of space, while we also showthat this problem cannot be solved in sublinear space in one pass. We then givea one-pass randomized streaming algorithm that computes all wildcard-periods$p$ of $S$ with $p<\frac{n}{2}$ and no wildcard characters appearing in thelast $p$ symbols of $S$, using $\mathcal{O}(k^3\mathsf{polylog}\, n)$ space.

Stay in the loop.

Subscribe to our newsletter for a weekly update on the latest podcast, news, events, and jobs postings.