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

Displayed time zone: Belfast change

10:00 - 11:15
Shared-memory data structuresMain conference at Mallorca+Menorca
Chair(s): Yossi Lev Oracle Labs
10:00
25m
Talk
Adding Approximate Counters
Main conference
Guy L. Steele Jr. Oracle Labs, Jean-Baptiste Tristan Oracle Labs
Link to publication DOI
10:25
25m
Talk
A Wait-Free Queue as Fast as Fetch-and-AddArtifact Evaluation
Main conference
Chaoran Yang Rice University, John Mellor-Crummey Rice University
Link to publication DOI
10:50
25m
Talk
Lease/Release: Architectural Support for Scaling Contended Data Structures
Main conference
Syed Kamran Haider University of Connecticut, William Hasenplaugh MIT, Dan Alistarh Microsoft Research
Link to publication DOI