ISU Electrical and Computer Engineering Archives

Computing Frequent Elements using Gossip

Lahiri, Bibudh and Tirthapura, Srikanta (2008) Computing Frequent Elements using Gossip. Publisher UNSPECIFIED.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

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.

EPrint Type:Technical Report
Subjects:Computer Engineering > SOFTWARE SYSTEMS > Parallel and Distributed Computing
ID Code:415
Identification Number:Identification Number UNSPECIFIED
Deposited By:Mr. Bibudh Lahiri
Deposited On:09 April 2008

Archive Staff Only: edit this record