2023/08/25 by Haoyu Li, Liuhui Wang, Li, Haoyu +13
Computer Science · Materials Science · Mathematics · #Algorithm #Bloom filter #Caching and Content Delivery #Chain (unit) #Computer science #Computer security #Covalent Organic Framework Applications #Data Structures and Algorithms (cs.DS) #Data compression #Data mining #Databases (cs.DB) #FOS: Computer and information sciences #Filter (signal processing) #Hash function #Information Theory (cs.IT) #Internet Traffic Analysis and Secure E-voting #Lossless compression #Mathematics #Theoretical computer science #Upper and lower bounds
paper · pdf · doi:10.48550/arxiv.2308.13632
openalex publication_date 2023/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Membership (membership query / membership testing) is a fundamental problem across databases, networks and security. However, previous research has primarily focused on either approximate solutions, such as Bloom Filters, or exact methods, like perfect hashing and dictionaries, without attempting to develop a an integral theory. In this paper, we propose a unified and complete theory, namely chain rule, for general membership problems, which encompasses both approximate and exact membership as extreme cases. Building upon the chain rule, we introduce a straightforward yet versatile algorithm framework, namely ChainedFilter, to combine different elementary filters without losing information. Our evaluation results demonstrate that ChainedFilter performs well in many applications: (1) it requires only 26% additional space over the theoretical lower bound for implicit static dictionary, (2) it requires only 0.22 additional bit per item over the theoretical lower bound for lossless data compression, (3) it reduces up to 31% external memory access than raw Cuckoo Hashing, (4) it reduces up to 36% P99 tail point query latency than Bloom Filter under the same space cost in RocksDB database, and (5) it reduces up to 99.1% filter space than original Learned Bloom Filter.