.png){kind=icon}
返回
A Shifting Filter Framework for Dynamic Set Queries
.png){kind=icon}
OA
AI
DOI：10.1109/TNET.2023.3247628.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Information filters
Filtering theory
Data structures
Fingerprint recognition
Distributed databases
Throughput
Task analysis
Dynamic set queries
element deletion
Cuckoo filters
Bloom filters
shifting framework
期刊
I
IF:
3.6
论文数:
4.4K
被引数:
9.5K
机构
引用论文
.png){kind=icon}
Metal carbonyls—II Carbon monoxide and chloride exchange with some cyclopentadienyl metal carbonyls
PREAI
分享收藏
查看更多内容