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

Prashant Pandey, Alex Conway, Joe Durie, Michael A. Bender, Martin Farach-Colton, Rob Johnson

Research output: Contribution to journalConference articlepeer-review

Abstract

Today's filters, such as quotient, cuckoo, and Morton, have a trade-off between space and speed; even when moderately full (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). Locally, the VQF is based on Robin Hood hashing, like 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 simpler design and implementation. The vector quotient filter has minimal performance decline at high load factors, a problem that has plagued modern filters, including quotient, cuckoo, and Morton. Furthermore, we give a thread-safe version of the vector quotient filter and show that insertion throughput scales 3× with four threads compared to a single thread.

Original languageEnglish (US)
Pages (from-to)1386-1399
Number of pages14
JournalProceedings of the ACM SIGMOD International Conference on Management of Data
DOIs
StatePublished - 2021
Event2021 International Conference on Management of Data, SIGMOD 2021 - Virtual, Online, China
Duration: Jun 20 2021Jun 25 2021

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems

Keywords

  • dictionary data structure
  • filters
  • membership query

Fingerprint

Dive into the research topics of 'Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design'. Together they form a unique fingerprint.

Cite this