direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Stefan Schmid's Publications

Distributed Computation of the Mode
Citation key KLS-DCM-08
Author Fabian Kuhn and Thomas Locher and Schmid, Stefan
Title of Book 27th ACM Symposium on Principles of Distributed Computing (PODC)
Pages 15–24
Year 2008
ISBN 978-1-59593-989-0
DOI http://dx.doi.org/10.1145/1400751.1400756
Location Toronto, Canada
Month August
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_1>m_2>=...>=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_2/m_1^2 log k) time with high probability, where the frequency moment F_l is defined as F_l = Sum_(i=1)^k m_i^l. This algorithm is substantially faster than the deterministic algorithm for various relevant frequency distributions. Moreover, we provide a lower bound of Ω(D + F_5/(m_1^5 B)), where B is the maximum message size, that captures the eect of the frequency distribution on the time complexity to compute the mode.
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions