## 4 Theoretical Analysis
### Search Failure Probability
#### 4.2.4 Functional Bloom Filter  
Based on the analysis of a functional Bloom filter (FBF) in [22], we compare search failure probability with other hash-based data structures in this paper. Let \(P(F_{b})\) represent the _search failure probability_ of a functional Bloom filter. As the search failure of an FBF is caused by _indeterminable_ or _false positive_, \(P(F_{b})\) can be formulated as follows. \[P(F_{b})=P(I)+P(F_{P}) \tag{28}\]  
where \(P(I)\) represents the probability of _indeterminables_ and \(P(F_{P})\) represents the probability of false positives in a functional Bloom filter. Let \(L\) represent the number of bits in a cell of an FBF. Among \(2^{L}\) possible values in a cell, value \(2^{L}-1\) is reserved to represent _conflict_. Value 0 is reserved for the initial before programming. Therefore, a functional Bloom filter can have \(2^{L}-2\) return values. Let \(S_{q}\) represent the set of elements whose return value is \(q\) with \(S_{q}\subset S\) (\(1\leq q\leq Q\)), where \(Q=2^{L}-2\). Assuming that return values are uniformly distributed, let \(n^{\prime}=\frac{n}{Q}\) be the number of elements in \(S_{q}\) for \(1\leq q\leq Q\). \(\bullet\) Indeterminable Probability  
In the querying procedure, if all the return values of \(k\) cells for input \(y\) are set as \(2^{L}-1\), i.e., conflict, then the functional Bloom filter cannot return a value, termed an _indeterminable_. Conflict occurs when a specific cell that was hashed by any element in \(S_{q}\) is hashed at least once by any other element in \(S-S_{q}\). The probability of _indeterminable_, \(P(I)\), can be formulated as  
\[P(I)=P(S)P(I|S)+P(S^{c})P(I|S^{c}). \tag{29}\]  
In Label (29), \(P(S)\) and \(P(S^{c})\) represent the probability that an input \(y\) is included in \(S\) and \(S^{c}\), respectively, where \(U=S\cup S^{c}\) and \(S\cap S^{c}=\emptyset\). Consider \(P(I|S)\) first. If input \(y\) is included in \(S\) (\(y\in S\)), input \(y\) would be included in one of \(S_{q}\) among \(q=1,\ldots,Q\). Consider a specific cell that is hashed by \(y\in S_{q}\). If the specific cell is hashed at least once by any other element in \(S-S_{q}\), then the cell would set conflict. The probability that the specific cell is not selected (hashed) by \(n-n^{\prime}\) elements in \(S-S_{q}\) with \(k\) hash functions is \((1-\frac{1}{m})^{k(n-n^{\prime})}\). Let \(P_{c,l}\) represent the probability of conflict for an element in set \(S\), which is the event that the specific cell is hashed at least once by \(n-n^{\prime}\) elements with \(k\) hash functions. \[P_{c,i}=1-(1-\frac{1}{m})^{k(n-n^{\prime})} \tag{30}\]There would be \(k\) cells that are hashed by the specific input \(y\) with \(k\) hash functions. An indeterminable event occurs when all \(k\) cells hashed by \(y\) get conflict. \[P(I|S)=(P_{c,i})^{k}=\Big{(}1-(1-\frac{1}{m})^{k(n-n^{\prime})}\Big{)}^{k} \tag{31}\]  
Now we consider \(P(I|S^{c})\). Let \(P_{c,n}\) represent the probability of conflict for input \(y\) which is not in set \(S\) (\(y\
otin S\)). Consider a specific cell that is hashed by \(y\). If the specific cell was hashed by any element in \(S_{q}\) and it was also hashed at least once by any other element in \(S-S_{q}\) in programming, then the specific cell is in conflict. The numbers of elements in \(S_{q}\) and \(S-S_{q}\) are \(n^{\prime}\) and \(n-n^{\prime}\), respectively. \(P_{c,n}\) is calculated as follows. \[P_{c,n}=\Big{(}1-(1-\frac{1}{m})^{k(n^{\prime})}\sum_{q=1}^{Q-1}\Big{(}1-(1- \frac{1}{m})^{k(n-qn^{\prime})}\Big{)} \tag{32}\]  
\(P_{c,n}\) is calculated avoiding duplications for \(q=1,\ldots,Q\). An indeterminable event occurs when all \(k\) cells hashed by \(y\) with \(k\) hash functions get conflict. \[P(I|S^{c})=(P_{c,n})^{k} \tag{33}\]  
For \(3n\) inputs (with \(n\) elements in \(S\) and with \(2n\) elements in \(S^{c}\)), then \(P(S)=\frac{n}{3n}=\frac{1}{3}\) and \(P(S^{c})=\frac{2n}{3n}=\frac{2}{3}\).