Scientific article
English

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

Published inFuture Generation Computer Systems, vol. 75, p. 108-127
Publication date2017
Abstract

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 insert 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.

Keywords
  • Distributed event-based system
  • Bloom filter
  • Wireless sensor network
  • Iterated hash function
  • Compressed bloom filter
Citation (ISO format)
MUNOZ ILLESCAS, Cristina, LEONE, Pierre. A Distributed Event-Based System based on Compressed Fragmented-Iterated Bloom Filters. In: Future Generation Computer Systems, 2017, vol. 75, p. 108–127. doi: 10.1016/j.future.2017.02.021
Main files (1)
Article (Published version)
accessLevelRestricted
Identifiers
Journal ISSN0167-739X
459views
1downloads

Technical informations

Creation16/03/2018 17:13:00
First validation16/03/2018 17:13:00
Update07/01/2025 07:38:23
Status update07/01/2025 07:38:23
Last indexation07/01/2025 07:39:28
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack