| Autor: |
Dissler, Benjamin, Holzer, Stephan, Wattenhofer, Roger |
| Rok vydání: |
2016 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We study local aggregation and graph analysis in distributed environments using the message passing model. We provide a flexible framework, where each of the nodes in a set $S$--which is a subset of all nodes in the network--can perform a large range of common aggregation functions in its $k$-neighborhood. We study this problem in the CONGEST model, where in each synchronous round, every node can transmit a different (but short) message to each of its neighbors. While the $k$-neighborhoods of nodes in $S$ might overlap and aggregation could cause congestion in this model, we present an algorithm that needs time $O(|S|+k)$ even when each of the nodes in $S$ performs a different aggregation on its $k$-neighborhood. The framework is not restricted to aggregation-trees such that it can be used for more advanced graph analysis. We demonstrate this by providing efficient approximations of centrality measures and approximation of minimum routing cost trees. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
