Computing Frequent Elements using Gossip
Lahiri, Bibudh and Tirthapura, Srikanta (2008) Computing Frequent Elements using Gossip. Publisher UNSPECIFIED.
Full text available as:
We present algorithms for identifying frequently occurring elements in a large distributed data set using em gossip. Our algorithms do not rely on any central control, or on an underlying network structure, such as a spanning tree. Instead, nodes repeatedly select a random partner and exchange data with the partner -- if this process continues for a (short) period of time, the desired results are computed, with probabilistic guarantees on the accuracy. Our algorithm for frequent elements is built by layering a novel small space ``sketch'' of data over a gossip-based data dissemination mechanism. We prove that the algorithm converges to the approximate frequent elements with high probability, and provide bounds on the time till convergence. To our knowledge, this is the first work on computing frequent elements using gossip.
Archive Staff Only: edit this record