An Efficient Hardware Architecture for Finding Frequent Items in Data Streams
Ali Ebrahim, Jalal Khlaifat · 2020
This paper presents a novel method for finding frequent items in data streams using a homogeneous counter-based hardware array. The presented array is a close hardware adaptation of the well-known Space-Saving algorithm. The array can identify frequent items with frequencies larger than a specified threshold with a single pass through the input dataset. When implemented on an Intel Arria 10 FPGA, 40% of the FPGA resources are sufficient for 1000+ hardware counters. This is enough to guarantee the identification of all frequent items with frequency thresholds as low as 0.1% of the size of any dataset, regardless of the input distribution. Compared to other hardware implementations, the presented architecture is the fastest on average, and the first to retain the guarantee property of the Space-Saving algorithm on the reported frequent items. In addition, test results on synthetic and real datasets showed that the presented method can achieve more than 11x throughput speedup compared to software implementations of the algorithm and up to 50% better precision compared to other hardware implementations.