| Periodicity Testing with Sublinear Samples and Space (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract In this work, we are interested in finding representative trends in long large data streamsin the presence of computational constraints; to this end we present algorithms for discovering periodic trends in a data stream S of length n in the combinatorial property testing model,using o(n) samples and space.In accordance with the property testing model, we first explore the notion of being close to periodic by we relaxing different notions of exact periodicity and obtaining three differentnotions of self-distance. An input S is then 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, approxi-mate periodicity, are not. A close investigation of the self-distances show that they are constant approximations of each other. We then present algorithms which distinguish between the twocases of S being exactly periodic and S being far from periodic with only a constant probabil-ity of error. Our algorithms need to sample only O(pn polylog n) positions and use as muchspace. They can also be used to find, using o(n) samples and space, the largest/smallest period,andn/or all of the approximate periods of S.Our algorithms may be viewed as working on streaming inputs where each data item is | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||