PPoPP 2016
Sat 12 - Wed 16 March 2016 Barcelona, Spain
Tue 15 Mar 2016 10:00 - 10:25 at Mallorca+Menorca - Shared-memory data structures Chair(s): Yossi Lev

We describe a general framework for adding the values of two approximate counters to produce a new approximate counter value whose expected estimated value is equal to the sum of the expected estimated values of the given approximate counters. (To the best of our knowledge, this is the first published description of any algorithm for adding two approximate counters.) We then work out implementation details for five different kinds of approximate counter and provide optimized pseudocode. For three of them, we present proofs that the variance of a counter value produced by adding two counter values in this way is bounded, and in fact is no worse, or not much worse, than the variance of the value of a single counter to which the same total number of increment operations have been applied. Addition of approximate counters is useful in massively parallel divide-and-conquer algorithms that use a distributed representation for large arrays of counters. We describe two machine-learning algorithms for topic modeling that use millions of integer counters, and confirm that replacing the integer counters with approximate counters is effective, speeding up a GPU-based implementation by over 65% and a CPU-based by nearly 50%, as well as reducing memory requirements, without degrading their statistical effectiveness.

Tue 15 Mar
Times are displayed in time zone: (GMT+01:00) Greenwich Mean Time : Belfast change

10:00 - 11:15: Main conference - Shared-memory data structures at Mallorca+Menorca
Chair(s): Yossi LevOracle Labs
PPoPP-2016-papers10:00 - 10:25
Link to publication DOI
PPoPP-2016-papers10:25 - 10:50
Chaoran YangRice University, John Mellor-CrummeyRice University
Link to publication DOI
PPoPP-2016-papers10:50 - 11:15
Syed Kamran HaiderUniversity of Connecticut, William HasenplaughMIT, Dan AlistarhMicrosoft Research
Link to publication DOI