Periodicity testing with sublinear samples and space
Funda Ergün, Subramanian Muthukrishnan, S. Cenk Şahinalp · ACM Transactions on Algorithms · 2010
In this work, we are interested in periodic trends in long data streams in the presence of computational constraints. To this end; we present algorithms for discovering periodic trends in the combinatorial property testing model in a data stream S of length n using o ( n ) samples and space. In accordance with the property testing model, we first explore the notion of being “close” to periodic by defining three different notions of self-distance through relaxing different notions of exact periodicity. An input S is then called approximately periodic if it exhibits a small self-distance (with respect to any one self-distance defined). We show that even though the different definitions of exact periodicity are equivalent, the resulting definitions of self-distance and approximate periodicity are not; we also show that these self-distances are constant approximations of each other. Afterwards, we present algorithms which distinguish between the two cases where S is exactly periodic and S is far from periodic with only a constant probability of error. Our algorithms sample only O (√ n log 2 n ) (or O (√ n log 4 n ), depending on the self-distance) positions and use as much space. They can also find, using o ( n ) samples and space, the largest/smallest period, and/or all of the approximate periods of S . These algorithms can also be viewed as working on streaming inputs where each data item is seen once and in order, storing only a sublinear ( O (√ n log 2 n ) or O (√ n log 4 n )) size sample from which periodicities are identified.