  Data sketches are a set of widely used approximated data summarizing
techniques. Their fundamental property is sub-linear memory complexity on the
input cardinality, an important aspect when processing streams or data sets
with a vast base domain (URLs, IP addresses, user IDs, etc.). Among the many
data sketches available, HyperLogLog has become the reference for cardinality
counting (how many distinct data items there are in a data set). Although it
does not count every data item (to reduce memory consumption), it provides
probabilistic guarantees on the result, and it is, thus, often used to analyze
data streams. In this paper, we explore how to implement HyperLogLog on an FPGA
to benefit from the parallelism available and the ability to process data
streams coming from high-speed networks. Our multi-pipelined high-cardinality
HyperLogLog implementation delivers 1.8x higher throughput than an optimized
HyperLogLog running on a dual-socket Intel Xeon E5-2630 v3 system with a total
of 16 cores and 32 hyper-threads.
