direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

Distributed Computation of the Mode
Zitatschlüssel KLS-DCM-08
Autor Fabian Kuhn and Thomas Locher and Schmid, Stefan
Buchtitel 27th ACM Symposium on Principles of Distributed Computing (PODC)
Seiten 15–24
Jahr 2008
ISBN 978-1-59593-989-0
DOI http://dx.doi.org/10.1145/1400751.1400756
Ort Toronto, Canada
Monat August
Zusammenfassung 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 zur Publikation [1] Download Bibtex Eintrag [2]

Under Construction

This page/section is
still under construc-
tion. Please try again
------ Links: ------

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Copyright TU Berlin 2008