Sie sind hier:


FPGA Acceleration for the Frequent Item Problem

Publication Details


FPGA Acceleration for the Frequent Item Problem


Jens Teubner, René Müller, and Gustavo Alonso


Proceedings 26th Int'l Conference on Data Engineering (ICDE), Long Beach, CA, USA, March 2010.


paper (PDF), presentation slides (PDF)


Field-programmable gate arrays (FPGAs) can provide performance advantages with a lower resource consumption (e.g., energy) than conventional CPUs. In this paper, we show how to employ FPGAs to provide an efficient and high-performance solution for the frequent item problem.

We discuss three design alternatives, each one of them exploiting different FPGA features, and we provide an exhaustive evaluation of their performance characteristics. The first design is a one-to-one mapping of the Space-Saving algorithm (shown to be the best approach in software), built on special features of FPGAs: content-addressable memory and dual-ported BRAM. The two other implementations exploit the flexibility of digital circuits to implement parallel lookups and pipelining strategies, resulting in significant improvements in performance. On low-cost FPGA hardware, the fastest of our designs can process 80 million items per second―three times as much as the best known result. Moreover, and unlike in software approaches where performance is directly related to the skew factor of the Zipf distribution, the high throughput is independent of the skew of the distribution of the input. In the paper we discuss as well several design trade-offs that are relevant when implementing database functionality on FPGAs. In particular, we look at resource consumption and the levels of data and task parallelism of three different designs.

Publication Log

October 2009

camera-ready for ICDE 2010

June 2009

submission to ICDE 2010 (accepted as full paper)



Prof. Dr. Jens Teubner
Tel.: 0231 755-6481