Finding Frequent Elements in non-bursty Streams

Full textClick to download.
CitationProceedings of the 2007 European Symposium on Algorithms
AuthorsRina Panigrahy
Dilys Thomas


We present an algorithm for finding frequent elements in a stream where the arrivals are not bursty. Depending on the burstiness in the stream our algorithm detects elements with frequency at least t with space between O(F1/t^2)and O(F2/t^2), where the latter applies when the stream is completely bursty; i.e., most elements arrive in contiguous groups; the former bound is attained when the arrival order is random. Our space complexity is ~O(@F1/t^2) where @ is a parameter that captures the burstiness of a stream and lies between 1 and F2/F1. A major advantage of our algorithm is that even if the relative frequencies of the different elements is fixed, the space complexity decreases with the length of the stream if the stream is not bursty. To our knowledge this is the only algorithm with such property.

Back to publications
Back to previous page