Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design

Abstract

Today’s filters, such as quotient, cuckoo, and Morton, have a trade-off between space and speed; even at moderate load factors (e.g., 50%-75% full), their performance degrades nontrivially. The result is that today’s systems designers are forced to choose between speed and space usage.

In this paper, we present the vector quotient filter (VQF). The VQF is based on Robin Hood hashing similar to the quotient filter but uses power-of-two-choices hashing to reduce the variance of runs, and thus offers consistent, high throughput across load factors. Power-of-two-choices hashing also makes it more amenable to concurrent updates, compared to the cuckoo filter and variants. Finally, the vector quotient filter is designed to exploit SIMD instructions so that all operations have O(1) cost, independent of the size of the filter or its load factor.

We show that the vector quotient filter is 2× faster for inserts compared to the Morton filter (a cuckoo filter variant and state-of-the-art for inserts) and has similar lookup and deletion performance as the cuckoo filter (which is fastest for queries and deletes), despite having a much simpler design and implementation. The vector quotient filter has minimal performance decline at high load factors, a problem that has plagued all modern filters, including quotient, cuckoo, and Morton. Furthermore, we give a thread-safe implementation of the vector quotient filter and show that the insertion throughput scales 3× with four threads compared to a single thread.