Vector Quotient Filter · SALT Systems Lab

Overview

The Vector Quotient Filter (VQF) supports approximate membership testing. Like the quotient filter, it is based on Robin Hood hashing. Unlike the quotient filter, it uses power-of-two-choices hashing to reduce the variance of runs.

As a result, the VQF delivers consistent, high throughput across load factors, and power-of-two-choices hashing also makes it more amenable to concurrent updates. It uses AVX-512 instructions, with an AVX2 fallback.

Key features

Consistent throughput

Power-of-two-choices hashing keeps performance steady across load factors.

SIMD

AVX-512 operations, with an AVX2 implementation as a fallback.

Concurrent inserts

A thread-safe build is available.

Simple API

vqf_insert, vqf_is_present, and vqf_remove.

API and build

vqf_insert(item);        // insert an item
vqf_is_present(item);    // membership (may return false positives)
vqf_remove(item);        // remove an item

$ make main && ./main 24
$ make THREAD=1 main_tx && ./main_tx 24 4    # thread-safe inserts

Citation

@inproceedings{PandeyCDB21,
  author    = {Prashant Pandey and Alex Conway and Joe Durie and Michael A. Bender
               and Martin Farach-Colton and Rob Johnson},
  title     = {Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design},
  booktitle = {Proceedings of the 2021 ACM International Conference on Management of Data (SIGMOD)},
  year      = {2021}
}