Communication Efficient Algorithms for Bounding and Approximating the Empirical Entropy in Distributed Systems
Open Access
Abstract
The empirical entropy is a key statistical measure of data frequency vectors, enabling one to estimate how diverse the data are. From the computational point of view, it is important to quickly compute, approximate, or bound the entropy. In a distributed system, the representative (“global”) frequency vector is the average of the “local” frequency vectors, each residing in a distinct node. Typically, the trivial solution of aggregating the local vectors and computing their average incurs a huge communication overhead. Hence, the challenge is to approximate, or bound, the entropy of the global vector, while reducing communication overhead. In this paper, we develop algorithms which achieve this goal.Keywords
This publication has 13 references indexed in Scilit:
- Distributed Spanner ApproximationSIAM Journal on Computing, 2021
- Optimal Compression of Approximate Inner Products and Dimension Reduction2017
- Anarchists, Unite2017
- Monitoring Properties of Large, Distributed, Dynamic Graphs2017
- Data Stream Management2016
- The continuous distributed monitoring modelACM SIGMOD Record, 2013
- Sketching and Streaming Entropy via Approximation Theory2008
- A geometric approach to monitoring threshold functions over distributed data streamsACM Transactions on Database Systems, 2007
- DDoS Attack Detection Algorithms Based on Entropy Computing2007
- Face recognition using eigenfaces2002