| Title |
Revolving-bloom Filter: A Bloom Filter Variant for Effective Set Reconciliation |
| Authors |
김규빈(Gyubin Kim) ; 임혜숙(Hyesook Lim) |
| DOI |
https://doi.org/10.5573/ieie.2026.63.6.8 |
| Keywords |
Bloom filter; Revolving bloom filter; Ternary bloom filter; Counting bloom filter; Set reconciliation |
| Abstract |
Maintaining consistency in large-scale distributed database across multiple devices in a distributed system is a fundamental challenge. In large-scale data environments in particular, dataset sizes often reach terabyte scale or beyond, and at such scales, directly transmitting or comparing the entire dataset incurs substantial communication and computational overhead. This problem becomes even more severe in environments with limited bandwidth and memory resources, such as wireless networks, edge computing, and IoT. As a result, set-summarization and set reconciliation techniques have gained increasing attention, which detect differences between sets without directly transmitting individual elements. The Ternary Bloom Filter (TBF) has been used for set summarization, mitigating deletion errors by restricting cell states to {0, 1, X}. However, in a fixed memory environment, the number of X states, where different elements collide by being mapped to the same cell, increases rapidly. This leads to false judgments in the comparison process used to identify subsets with distinct elements, and ultimately causes failures in set reconciliation based on an Invertible Bloom Filter (IBF). To address this issue, this study proposes a Revolving Bloom Filter (R-BF), in which each counter wraps around to zero upon reaching its maximum value. By preventing saturation lock while preserving the expressive power of counter-based representations, R-BF mitigates hash-collision distortion and enhances both the decoding stability of the d-IBF and the accuracy of set reconciliation. |