A Shifting Filter Framework for Dynamic Set Queries
A Shifting Filter Framework for Dynamic Set Queries
复制标题
DOI：
10.1109/tnet.2023.3247628
复制
发表时间：
2023-10
期刊：
影响因子：
--
通讯作者：
Pengtao Fu;Lailong Luo;Deke Guo;Shangsen Li;Yun Zhou
中科院分区：
文献类型：
--
作者：
Pengtao Fu;Lailong Luo;Deke Guo;Shangsen Li;Yun Zhou
集合查询是计算机系统中的一个基本问题。大量的应用依赖于成员关系、关联性和多重性的查询结果。解决这样一个基本问题的传统方法是从Bloom Filter衍生出来的。然而，这样的方法可能不支持元素删除，需要额外的过滤器或先验知识，使得它们不适合用于动态集合表示和查询的高性能实现。在本文中，我们设想了一种新型的草图框架，该框架具有多功能、非参数、空间高效和可删除的特点。据我们所知，现有的设计都不能同时保证这些功能。为此，我们提出了一个通用的移位框架来表示带有偏移量的辅助信息(如重数、关联性)。此后，我们将在槽级别水平以及在桶级别垂直地为哈希表指定这样的设计理念。理论和实验结果共同证明，我们的设计在小内存的情况下对三种类型的集合查询都有很好的效果。
Set query is a fundamental problem in computer systems. Plenty of applications rely on the query results of membership, association, and multiplicity. A traditional method that addresses such a fundamental problem is derived from Bloom filter. However, such methods may fail to support element deletion, require additional filters or apriori knowledge, making them unamenable to a high-performance implementation for dynamic set representation and query. In this paper, we envision a novel sketch framework that is multi-functional, non-parametric, space efficient, and deletable. As far as we know, none of the existing designs can guarantee such features simultaneously. To this end, we present a general shifting framework to represent auxiliary information (such as multiplicity, association) with the offset. Thereafter, we specify such design philosophy for a hash table horizontally at the slot level, as well as vertically at the bucket level. Theoretical and experimental results jointly demonstrate that our design works exceptionally well with three types of set queries under small memory.