Distributed computation of the mode

ABSTRACT

This paper studies the problem of computing the most frequent element (the mode) by means of a distributed algorithm where the elements are located at the nodes of a network. Let k denote the number of distinct elements and further let m_i be the number of occurrences of the element e_i in the ordered list of occurrences m₁m₂≥ ... ≥ m_k. We give a deterministic distributed algorithm with time complexity O(D+k) where D denotes the diameter of the graph, which is essentially tight. As our main contribution, a Monte Carlo algorithm is presented which computes the mode in O(D + F₂/m₁²*log k) time with high probability, where the frequency moment F_t is defined as F_t = sum_i=1^k m_i^t. This algorithm is substantially faster than the deterministic algorithm for various relevant frequency distributions. Moreover, we provide a lower bound of Omega(D+F₅/(m₁⁵B)), where B is the maximum message size, that captures the effect of the frequency distribution on the time complexity to compute the mode.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web Caching and Zipf-like Distributions: Evidence and Implications. In Proc. 18th Annual IEEE Conference on Computer Communications (INFOCOM), 1999.
• 3: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004 [doi>10.1016/S0304-3975(03)00400-6]
• 4: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 5: D. Dobkin and J. I. Munro. Determining the Mode. Theoretical Computer Science, 12:255--263, 1980.
• 6: M. Durand and P. Flajolet. LogLog Counting of Large Cardinalities. In Proc. 11th Annual European Symposium on Algorithms (ESA), 2003.
• 7: A. Farzan, P. Ferragina, G. Franceschini, and J. J. Munro. Cache-Oblivious Comparison-Based Algorithms on Multisets. In Proc. 13th Annual European Sympoisum on Algorithms (ESA), 2005.
• 8: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 9: Bala Kalyanasundaram , Georg Schintger, The probabilistic communication complexity of set intersection, SIAM Journal on Discrete Mathematics, v.5 n.4, p.545-557, Nov. 1992 [doi>10.1137/0405044]
• 10: Fabian Kuhn , Thomas Locher , Roger Wattenhofer, Tight bounds for distributed selection, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248401]
• 11: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 12: M. Mitzenmacher. A Brief History of Generative Models for Power Law and Lognormal Distributions. Internet Mathematics, 1:226--251, 2003.
• 13: J. I. Munro and P. M. Spira. Sorting and Searching in Multisets. SIAM Journal of Computing (SICOMP), 5(1):1--8, 1976.
• 14: Boaz Patt-Shamir, A note on efficient aggregate queries in sensor networks, Theoretical Computer Science, v.370 n.1-3, p.254-264, February, 2007 [doi>10.1016/j.tcs.2006.10.032]
• 15: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 16: A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, v.106 n.2, p.385-390, Dec. 1992 [doi>10.1016/0304-3975(92)90260-M]
• 17: H. Simon. On a Class of Skew Distribution Functions. Biometrika, 42:425--440, 1955.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems

General Terms:
Algorithms, Theory

Keywords:
aggregation, distributed algorithms, mode, most frequent element