SkiQF

Overview

Adaptive filters keep the observed false-positive rate low on skewed workloads by learning from repeated false positives. However, each adaptation adds disk I/O, which hurts throughput on workloads where false positives do not repeat.

Existing adaptive filters adapt on every detected false positive. Online adaptive filters instead decide, as queries arrive, whether adapting is worth the cost. SkiQF applies ski-rental analysis to this adapt-or-tolerate decision and is 2-competitive on total I/O.

Key features

Run the experiments

./setup.sh      # builds external dependencies (SplinterDB, WiredTiger)
./run_tests     # results are written to ./paper/<experiment-name>/