A General-Purpose Counting Filter

TLDR

Approximate Membership Query data structures such as Bloom, quotient, and cuckoo filters are widely used in databases, storage, networking, and computational biology, yet many lack deletion, counting, compactness, speed, resizability, mergeability, or good SSD locality. This work introduces the counting quotient filter (CQF) as a new general‑purpose AMQ. The CQF provides approximate membership testing and item counting while remaining small, fast, SSD‑friendly, and supporting deletions, skew‑tolerant counting, resizing, merging, and concurrent access. Experimental results show that the CQF performs competitively on both synthetic and application‑generated datasets.

Abstract

Approximate Membership Query (AMQ) data structures, such as the Bloom filter, quotient filter, and cuckoo filter, have found numerous applications in databases, storage systems, networks, computational biology, and other domains. However, many applications must work around limitations in the capabilities or performance of current AMQs, making these applications more complex and less performant. For example, many current AMQs cannot delete or count the number of occurrences of each input item, take up large amounts of space, are slow, cannot be resized or merged, or have poor locality of reference and hence perform poorly when stored on SSD or disk. This paper proposes a new general-purpose AMQ, the counting quotient filter (CQF). The CQF supports approximate membership testing and counting the occurrences of items in a data set. This general-purpose AMQ is small and fast, has good locality of reference, scales out of RAM to SSD, and supports deletions, counting (even on skewed data sets), resizing, merging, and highly concurrent access. The paper reports on the structure's performance on both manufactured and application-generated data sets.