Concurrent data structures for efficient streaming aggregation
Daniel Cederman, Vincenzo Massimiliano Gulisano, Yiannis Nikolakopoulos, Marina Papatriantafilou, Philippas Tsigas · 2014
We briefly describe our study on the problem of streaming multiway aggregation, where large data volumes are received from multiple input 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 enabling for low-latency and high-throughput multiway aggregation; an issue that has been overlooked in the literature. We propose two new concurrent data structures and their lock-free linearizable implementations, supporting both order-sensitive and order-insensitive aggregate functions.Results from an extensive evaluation show significant improvement in the aggregation performance,in terms of both processing throughput and latency over the commonly-used techniques based on queues.