Concepedia

Optimal Gossip Algorithms for Exact and Approximate Quantile Computations

Bernhard Haeupler, Jeet Mohapatra, Hsin-Hao Su

2018 · 10 citations · 37 references

Open access

Concepts

ComputingComputer EngineeringComputer ScienceAlgorithmsDistributed SystemsInformation TheoryCommunication ComplexityData SynchronizationDistributed AlgorithmsDistributed ComputingDistributed SynchronizationRandomized ComputationDistributed Approximation AlgorithmsGossip AlgorithmsInference For Quantile FunctionsQuantile ApproximationQuantile ForecastingSample Quantiles

Abstract

This paper gives drastically faster gossip algorithms to compute exact and approximate quantiles.

References

37

TAG

Samuel Madden, Michael J. Franklin, Joseph M. Hellerstein et al. · ACM SIGOPS Operating Systems Review · 2002 · 2.7K citations

Computing, Computer Science, Computer Systems +17

Epidemic algorithms for replicated database maintenance

Alan Demers, Dan Greene, Carl Hauser et al. · 1987 · 1.7K citations · Full text

Computing, Computer Systems, Distributed Systems +14

Gossip-based computation of aggregate information

David Kempe, Alin Dobra, Johannes Gehrke · 2004 · 1.5K citations

Computing, Computer Science, Computer Systems +14

The cougar approach to in-network query processing in sensor networks

Yong Yao, Johannes Gehrke · ACM SIGMOD Record · 2002 · 1.3K citations

Computing, Computer Science, Computer Systems +17

Time bounds for selection

Manuel Blum, Robert W. Floyd, Vaughan Pratt et al. · Journal of Computer and System Sciences · 1973 · 1.2K citations

Natural Sciences, Mathematics, Algorithms +2