Panigrahy, Rina and Thomas, Dilys (2007) Finding Frequent Elements in Non-bursty Streams. In: European Symposium of Algorithms, October 8-10, 2007, Eilat, Israel.
|PDF (Frequent Elements Algorithm for Data Streams ) - Accepted Version|
Official URL: http://esa-symposium.org/symposia.php
We present an algorithm for finding frequent elements in a stream where the arrivals are not bursty. Depending on the amount of burstiness in the stream our algorithm detects elements with frequency at least t with space between ˜O(F1/t2) and ˜O(F2/t2) where F1 and F2 are the first and the second frequency moments of the stream respectively. The latter space complexity is achieved when the stream is completely bursty; i.e., most elements arrive in contiguous groups, and the former is attained when the arrival order is random. Our space complexity is ˜O(αF1/t2) 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.
|Item Type:||Conference or Workshop Item (Paper)|
|Uncontrolled Keywords:||data stream, frequent elements|
|Related URLs:||Author Homepage, Project Homepage||http://research.microsoft.com/~rina/, http://infolab.stanford.edu/stream|
|Deposited By:||Dilys Thomas|
|Deposited On:||08 Dec 2008 08:11|
|Last Modified:||08 Dec 2008 08:11|
Repository Staff Only: item control page