---
res:
bibo_abstract:
- We consider the problem of aggregation in overlay networks. We use a synchronous
time model in which each node has polylogarithmic memory and can send at most
a polylogarithmic number of messages per round. We investigate how to quickly
compute the result of an aggregate functionf over elements that are distributed
among the nodes of the network such that the result is eventually known by a selected
root node. We show how to compute distributive aggregate functions such as SUM,
MAX, and OR in time $O(\log n / \log\log n)$ using a tree that is created in a
pre-processing phase. If only a polylogarithmic number of data items need to be
aggregated, we show how to compute the result in time $O(\sqrt{\log n / \log\log
n})$. Furthermore, we show how to compute holistic aggregate functions such as
DISTINCT, SMALLEST(k) and MODE(k) in time $O(\log n / \log\log n)$. Finally, we
show a lower bound of $\Omega(\sqrt{\log n / \log\log n})$ for deterministic algorithms
that compute any of the aggregate functions in the scope of the thesis.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Kristian
foaf_name: Hinnenthal, Kristian
foaf_surname: Hinnenthal
foaf_workInfoHomepage: http://www.librecat.org/personId=32229
dct_date: 2016^xs_gYear
dct_language: eng
dct_publisher: Universität Paderborn@
dct_title: Aggregation in Overlay Networks@
...