Aeris Filter

Overview

Aeris (Adaptive Expandable Range filter) is a range filter that resolves false positives as it encounters them. It is the first range filter to guarantee a bounded false-positive rate for any query distribution, including skewed and adversarial ones, where existing range filters' false-positive rates are unbounded.

Aeris builds on the Memento filter, a fingerprint-based dynamic range filter, and inherits its dynamic updates, constant-time operations, and false-positive guarantees. It also expands efficiently and is monotonically adaptive, so it never forgets a false positive.

Key features

API

ARQF* arqf = (ARQF*)malloc(sizeof(ARQF));
arqf_init_with_rhm(arqf, db, n_slots, key_size, memento_bits, seed);

qf_insert_memento(arqf->qf, value, 0, &fingerprint);       // insert

result = qf_point_query(arqf->qf, left, QF_NO_LOCK);       // query
result = qf_range_query(arqf->qf, left, right, QF_NO_LOCK);

arqf_adapt_range(arqf, left, right, 0);                     // fix a false positive