Identifying frequent items in a network using gossip
We present algorithms for identifying frequently occurring items in a large distributed data set Our algorithms use gossip as the underlying communication mechanism and do not rely on any central control nor on an underlying network structure such as a spanning tree Instead nodes repeatedly select a random partner and exchange data with that 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 identifying frequent items is built by layering a novel small space sketch of data over a gossip-based data dissemination mechanism We prove that the algorithm identifies the frequent items with high probability and provides bounds on the time till convergence To our knowledge this is the first work on identifying frequent items using gossip Published by Elsevier Inc
frequent items gossip sketch