Hourglass: An Adaptive Range Filter with Lightweight Hybrid Encoding

Range filters can check whether a queried range is non-empty within a key set, with no false negatives and a low false positive rate. However, existing range filters fail to address recurring false positives in skewed or adversarial queries. In this paper, we propose Hourglass, an adaptive range filter that defends against recurring false positives through lightweight hybrid encoding and semi-sorted adaptivity. Hourglass partitions keys into prefixes, stored in a semi-sorted cuckoo filter, and suffixes, encoded using hybrid encoding schemes based on their sparsity. By preserving the order of fingerprints, the semi-sorted cuckoo filter improves space efficiency. Additionally, Hourglass introduces a new adaptivity strategy that updates fingerprints without violating the semi-sorting order. Further, Hourglass introduces a correlation-aware space allocation model to optimize space across varying key-query correlation degrees. The evaluations show that Hourglass outperforms state-of-the-art range filters under adversarial workloads, achieving a 9.8-35.4X lower false positive rate. Moreover, they demonstrate that Hourglass delivers robust performance on both synthetic and real-world datasets, as well as under varying key-query correlation degrees.