A Distributed Event-Based System based on Compressed Fragmented-Iterated Bloom Filters

摘要

In this research, we propose the construction of a new architecture of Fragmented-Iterated Bloom Filters to redirect events of a distributed event-based system. We introduce two novel structures of Bloom Filters: Fragmented Bloom Filters and Iterated Bloom Filters. The aim of Iterated Bloom Filters is to discard single events that do not match any subscription. Then, Fragmented Bloom Filters deal with conjunctive and disjunctive set of events. Whether a match is found at the Fragmented Bloom Filters the publication is forwarded. Our strategy is compared to the alternative one relying on Standard Bloom Filters. The results show that Fragmented Bloom Filters lead to save memory and computational resources at the membership test. Moreover, we show that there is no memory cost for dividing a Bloom Filter in smaller Bloom Filters using the same: (1) number of elements to insen and (2) probability of false positives. Then, we prove that fast hash functions required for Fragmented Bloom Filters present a lower complexity that those required for Standard Bloom Filters. Additionally, we determine that the double hashing technique does not result in a lower complexity. Afterwards, we show that the construction of a structure of Iterated Bloom Filters using an Iterated Hash Function reduces the complexity because smaller filters and less hash functions are required. Furthermore, if information is structured in a tree Iterated Bloom Filters decrease the probability of false positives. We also focus on the improvement of data exchange for updating Fragmented-Iterated Bloom Filters between nodes. The goal is to reduce data transmitted. For this purpose, we study the effect of compressing Fragmented-Iterated Bloom Filters. The main benefit of Compressed Bloom Filters is that they transmit less bits. Therefore, less bandwidth is required and the latency of the network is reduced. The choice of Compressed Fragmented Bloom Filters preserves all these positive effects by limiting the number of transmitted bits due to its flexible structure. Besides, Compressed Iterated Bloom Filters also decrease computation.