2011 | OriginalPaper | Chapter
Periodicity and Cyclic Shifts via Linear Sketches
Authors : Michael S. Crouch, Andrew McGregor
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the problem of identifying periodic trends in data streams. We say a signal
${\mathbf a} \in \ensuremath{\mathbb{R}} ^n$
is
p
-periodic if
a
i
=
a
i
+
p
for all
i
∈ [
n
−
p
]. Recently, Ergün et al. [4] presented a one-pass,
O
(
polylog
n
)-space algorithm for identifying the smallest period of a signal. Their algorithm required
${\mathbf a}$
to be presented in the
time-series
model, i.e.,
a
i
is the
i
th element in the stream. We present a more general linear sketch algorithm that has the advantages of being applicable to a) the
turnstile stream model
, where coordinates can be incremented/decremented in an arbitrary fashion and b) the
parallel
or
distributed
setting where the signal is distributed over multiple locations/machines. We also present sketches for (1 +
ε
) approximating the ℓ
2
distance between
${\mathbf a}$
and the nearest
p
-periodic signal for a given
p
. Our algorithm uses
O
(
ε
− 2
polylog
n
) space, comparing favorably to an earlier time-series result that used
$O(\epsilon^{-5.5} \sqrt{p} polylog n)$
space for estimating the Hamming distance to the nearest
p
-periodic signal. Our last periodicity result is an algorithm for estimating the periodicity of a sequence in the presence of noise. We conclude with a small-space algorithm for identifying when two signals are exact (or nearly) cyclic shifts of one another. Our algorithms are based on bilinear sketches [10] and combining Fourier transforms with stream processing techniques such as ℓ
p
sampling and sketching [13, 11].