Memory-efficient groupby-aggregate using compressed buffer trees

The rapid growth of fast analytics systems, that require data processing in memory, makes memory capacity an increasingly-precious resource. This paper introduces a new compressed data structure called a Compressed Buffer Tree (CBT). Using a combination of techniques in-cluding buffering, compression, and serialization, CBTs improve the memory efficiency and performance of the GroupBy-Aggregate abstraction that forms the basis of not only batch-processing models like MapReduce, but re-cent fast analytics systems too. For streaming workloads, aggregation using the CBT uses 21-42 % less memory than using Google SparseHash with up to 16 % better throughput. The CBT is also compared to batch-mode aggregators in MapReduce runtimes such as Phoenix++ and Metis and consumes 4 × and 5 × less memory with 1.5-2 × and 3-4 × more performance respectively.