Periodicity and Cyclic Shifts via Linear Sketches

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].