范围过滤器是紧凑的数据结构，用于解答近似范围空性查询。它们在许多领域中得到了应用，例如在键值存储中，可以快速排除给定查询范围内键的存在，避免在存储中搜索这些键。然而，所有现有的范围过滤器都表现出以下至少一个缺陷：(1) 它们不提供稳健的误报率和性能保证，(2) 它们不支持可变长度的键和查询范围，(3) 它们不允许插入、删除或扩展等动态操作。我们介绍了Diva，这是第一个同时解决上述所有挑战的范围过滤器。Diva通过取样键并将它们存储在一个缓存高效的前缀树中来学习数据集的分布。它通过移除最长公共前缀并截断后缀对取样之间的键进行压缩，同时保留足够的中间位（即插入）以允许区分按排序顺序的键。它将插入存储在常数时间动态数据块中，这些数据块被拉伸并最终拆分以处理插入和扩展。它通过遍历前缀树并检查目标查询范围内是否包含至少一个插入来处理范围查询。Diva是多伦多大学Orca实验室与KTH和哥本哈根大学合作多年研究过滤器的结晶。本文描述了Diva如何建立在这项工作的基础上，以及它如何解决现有技术的局限性。
Eslami 等人（周四）研究了这个问题。