沙漏算法：一种采用轻量级混合编码的自适应范围滤波器

《Proceedings of the ACM on Management of Data》：Hourglass: An Adaptive Range Filter with Lightweight Hybrid Encoding

本文提出自适应范围过滤器Hourglass，通过轻量级混合编码和半排序自适应机制解决 skewed 或 adversarial 查询中的反复假阳性问题。其创新点包括前缀半排序布谷鸟过滤器、后缀混合编码及相关性感知空间分配模型，实验表明在对抗负载下性能提升达9.8-35.4倍，且在合成与真实数据集上表现稳健。

　　

摘要

范围过滤器可以检查查询范围内的键集是否非空，同时保证没有误报（false negatives）且误报率较低。然而，现有的范围过滤器无法解决在数据分布不均或存在攻击性查询（adversarial queries）情况下频繁出现的误报问题。在本文中，我们提出了Hourglass这一自适应范围过滤器，它通过轻量级的混合编码技术和半排序（semi-sorted）适应性机制来防御重复的误报。Hourglass将键分为前缀部分（存储在半排序的Cuckoo过滤器中）和后缀部分（根据键的稀疏性采用混合编码方案进行编码）。通过保持指纹（fingerprints）的顺序，半排序的Cuckoo过滤器提高了空间效率。此外，Hourglass还引入了一种新的适应性策略，可以在不破坏半排序顺序的情况下更新指纹数据。同时，它还采用了基于键查询相关性程度的空间分配模型来优化空间利用。评估结果显示，在具有攻击性的工作负载下，Hourglass的性能优于现有的最先进范围过滤器，误报率降低了9.8至35.4倍。此外，实验证明Hourglass在合成数据集和真实世界数据集上均表现出良好的性能，并且能够适应不同的键查询相关性程度。