4.5 Article

A Shifting Filter Framework for Dynamic Set Queries

Journal

IEEE-ACM TRANSACTIONS ON NETWORKING
Volume -, Issue -, Pages -

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2023.3247628

Keywords

Information filters; Filtering theory; Data structures; Fingerprint recognition; Distributed databases; Throughput; Task analysis; Dynamic set queries; element deletion; Cuckoo filters; Bloom filters; shifting framework

Ask authors/readers for more resources

This paper introduces a novel sketch framework that is multi-functional, non-parametric, space efficient, and deletable for dynamic set representation and query. The design philosophy involves representing auxiliary information with the offset at the slot and bucket level. Theoretical and experimental results show that the design works well for three types of set queries under small memory.
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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available