# Bloom Filter Approach for Autonomous Data Acquisition in the Edge-Based MCS Scenario +
## 3 Materials and Methods
### Bloom Filter  
To enable autonomous decision-making of a mobile device regarding its participation in sensor data acquisition, processing, and transmission to both edge and cloud servers, we have used a well-known Bloom filter (BF) approach. BF is a probabilistic data structure invented by [PERSON] in 1970 and is used to determine whether an element belongs to a set or not [49]. The fundamental feature of this structure is that it has a low rate of false positives, claiming that an element is part of the set when it is not, but never false negatives, stating that an element was not in the set when it was inserted [50]. A BF is an array of \(m\) bits that represents a set \(S=\{r_{1},r_{2},\ldots,r_{n}\}\) of \(n\) elements, which are all initially set to 0. The idea is to evenly map elements of a set to random integers in the range \(1,\ldots m\) by using \(k\) independent hash functions, \(h_{i}(r),1\leq i\leq k\). In the context of MCS, an element is each data reading produced by the end-user device, and the set represents readings created by all devices in an \(km\) MGRS area. To encode data reading in the BF, we use the information about a measured property and location where this reading was produced. We need to discover the bits \(h_{i}(r)\) that should be set to one for \(1\leq i\leq k\) to add a reading (i.e., an element) \(r\) in a filter (and submit it to the ME host, so that the host can process it and disseminate it to all interested requesters). To test whether reading has previously been submitted to the ME host, we need to see if it has been encoded in a BF. To phrase it another way, we need to compute the \(k\) hash functions over the element and check if all bits in the array's relevant places are set to 1. If at least one bit is set to 0, the reading \(r\) is valuable as it almost certainly does not exist in the ME host. If all bits are 1, either \(r\) is already sent to the ME host, or bits were set to 1 during the insertion of other elements, resulting in a false positive. The number of hash functions determines the likelihood of a false positive \(p\), the number of added elements, and the length of the BF, where \(k\) is typically a constant much smaller than \(m\) and proportional to \(n\). To calculate \(p\), we first assume that each array position is chosen with equal probability by a hash function. As a result, if a BF has \(m\) bits and \(k\) hash functions, the probability that a bit is not set to 1 by any of the hash functions is (see Equation (1)):  
\[p_{(b=0)}=(1-\frac{1}{m})^{k}, \tag{1}\]  
where \(p_{(b=0)}\) is the probability that a bit is 0, \(m\) is the number of bits, and \(k\) is the number of independent hash functions in a BF structure. After inserting \(n\) elements to the filter, the probability that a certain bit is still 0 is (see Equation (2)):  
Figure 1: Decentralized edge-enabled MCS architecture. \[p^{\prime}_{b=0}=(1-\frac{1}{m})^{kn}, \tag{2}\]  
where \(p^{\prime}_{(b=0)}\) is the probability that a bit is 0 after the insertion of \(n\) elements, while the probability that it is 1 is 1 (see Equation (3)):  
\[p^{\prime}_{b=1}=1-(1-\frac{1}{m})^{kn}, \tag{3}\]  
where \(p^{\prime}_{(b=1)}\) is the probability that a bit is 1 after the insertion of \(n\) elements. To decide if a reading has already been produced (i.e., an element belongs to a set), we must determine whether or not all of the \(k\) array positions in the filter computed by the hash functions are set to 1. When the element is not part of the set, the probability of this happening is (see Equation (4)):  
\[p=(1-(1-\frac{1}{m})^{kn})^{k}\approx(1-e^{-kn/m})^{k}, \tag{4}\]  
where \(p\) is the probability of false positives, i.e., all of the \(k\) array positions in BF are set to 1. That is, as the number of bits \(m\) increases, the chance of false positives drops and grows when the number of inserted items \(n\) increases. We have to minimize Equation (4) to get the optimal number of hash functions \(k\).