One table to count them all: parallel frequency estimation on single-board computers

Taşyaran, Fatih and Yıldırır, Kerem and Taş, Mustafa Kemal and Kaya, Kamer (2019) One table to count them all: parallel frequency estimation on single-board computers. In: 25th International European Conference on Parallel and Distributed Computing, Euro-Par 2019, Göttingen, Germany

This is the latest version of this item.

Full text not available from this repository. (Request a copy)


Sketches are probabilistic data structures that can provide approximate results within mathematically proven error bounds while using orders of magnitude less memory than traditional approaches. They are tailored for streaming data analysis on architectures even with limited memory such as single-board computers that are widely exploited for IoT and edge computing. Since these devices offer multiple cores, with efficient parallel sketching schemes, they are able to manage high volumes of data streams. However, since their caches are relatively small, a careful parallelization is required. In this work, we focus on the frequency estimation problem and evaluate the performance of a high-end server, a 4-core Raspberry Pi and an 8-core Odroid. As a sketch, we employed the widely used Count-Min Sketch. To hash the stream in parallel and in a cache-friendly way, we applied a novel tabulation approach and rearranged the auxiliary tables into a single one. To parallelize the process with performance, we modified the workflow and applied a form of buffering between hash computations and sketch updates. Today, many single-board computers have heterogeneous processors in which slow and fast cores are equipped together. To utilize all these cores to their full potential, we proposed a dynamic load-balancing mechanism which significantly increased the performance of frequency estimation.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Parallel algorithms; Single board computers; Streaming data
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 30 Jul 2023 11:21
Last Modified: 30 Jul 2023 11:21

Available Versions of this Item

Actions (login required)

View Item
View Item