Concurrent data structures for efficient streaming aggregation

In this paper, we study the problem of streaming multiway aggre-gation, where large data volumes are received from multiple in-put streams. Multiway aggregation is a fundamental computational component in data stream management systems, requiring low-latency and high throughput solutions. We focus on the problem of designing concurrent data structures for achieving low-latency and high throughput multiway aggregation; an issue that has been over-looked in the literature. Data structures act as articulation points between pipeline stages of streaming aggregation, supporting par-allelism and balancing the work between the aggregate stages. By studying the use and limitations of existing aggregate designs and the data structures they use, we motivate the need for new ones. We present two new concurrent data structures and their lock-free linearizable implementations, supporting both order-sensitive and order-insensitive aggregate functions. We also present an exten-sive evaluation, based on a variety of aggregation queries on two large datasets, one with data extracted from SoundCloud, a mu-sic social network, and one with data from a smart grid metering network. In all the experiments, the proposed data structures and methods improved the aggregation performance significantly, up to one order of magnitude, in terms of both processing throughput and latency over the commonly-used techniques based on queues. Keywords data streaming, data structures, lock-free synchronization ∗The research leading to these results has been partially sup-ported by the European Union Seventh Framework Programme (FP7/2007-2013) through the EXCESS Project (www.excess