# A Distance-Encoded Bloom Filter for Fast NDN Name Lookup
## 3 Proposed Scheme
### Analysis  
In a conventional standard Bloom filter, if the number of hash functions is \(k\), each inserted element sets \(k\) bits. Given a Bloom filter of size \(m\) bits with \(n\) elements, the probability \(p_{1}\) that a particular bit remains unset can be approximately calculated as follows:  
\[p_{1}=\left(1-\frac{1}{m}\right)^{kn}\approx e^{-kn/m} \tag{1}\]  
The probability that all the bits pointed to by \(k\) hash functions are set to \(1\) is \(\left(1-p_{1}\right)^{k}\). Therefore, the false positive probability \(FPP_{S}\) of the standard Bloom filter is given as follows [34]. \[FPP_{S}=\left(1-p_{1}\right)^{k}=\left(1-\left(1-\frac{1}{m}\right)^{kn} \right)^{k} \tag{2}\]  
In the distance-encoded Bloom filter, two bits for \(sd\) and (\(ld\)-\(sd\)) are set based on the hash value of a given element. If \(ld\) and \(sd\) are equal, meaning (\(ld\)-\(sd\)) = 0, then the (\(ld\)-\(sd\)) bit is not set, and only the \(sd\) bit is set. For each given \(ld\) and \(sd\), the expected number of set bits, \(s\), is given by \(s\) = \(r\cdot 1+\left(1-r\right)2\), where \(r\) is the probability that \(sd\) is equal to \(ld\). The probability \(p_{2}\) that a particular bit remains unset is approximated as follows:  
\[p_{2}=\left(1-\frac{s}{m}\right)^{kn}\approx e^{-kns/m} \tag{3}\]  
The probability that all bits pointed to by \(k\) hash functions are set to \(1\) is given by \(\left(1-p_{2}\right)^{k}\). Let \(p_{0}\) be the probability that at least one of the \(k\) bits is not set. Then, \(p_{0}\) = \(1-\left(1-p_{2}\right)^{k}\). The distance-encoded Bloom filter returns a negative result if there is no \(sd\) candidate at all. The maximum number of \(sd\) candidates is \(h\) = \(w/2\), where \(w\) is the word size. The probability of failing to reach a consensus from \(k\) bits for all the \(h\) bits is \({p_{0}}^{h}=\left[1-\left(1-p_{2}\right)^{k}\right]^{h}\). Thus, the false positive probability \(FPP_{D}\) of the distance-encoded Bloom filter that at least one \(sd\) candidate exists is given as follows:  
\[FPP_{D}=1-{p_{0}}^{h}=1-\left[1-\left(1-p_{2}\right)^{k}\right]^{h} \tag{4}\]  
For a given [\(L\), \(U\)] range, the next search should be conducted within the range \(\left[c+sd,c+ld\right]\), where \(c\) represents the current component level. If \(c+sd>U\), then the search cannot proceed further. In such a case, the distance-encoded Bloom filter returns a negative result instead of a positive one. Assuming \(c\) = 0 for simplicity, if \(U\) = 0, the only possible value for \(sd\) is 0. In this scenario, the probability of failing to yield a valid \(sd\) value, denoted as \(p_{f}\), is \(p_{0}\). For an arbitrary \(i\) representing \(U\), there are \(i+1\) possible valid \(sd\) values. Thus,the probability that all of them fail, \(p_{f}\), is given by \({p_{0}}^{i+1}\). Assuming \(U\) follows a uniform distribution, the overall failure probability \(p_{f}\) is as follows:  
\[p_{f}=\frac{1}{h}\cdot\sum_{U=0}^{h-1}{p_{0}}^{U+1}=\frac{1}{h}\cdot\left[\frac {{p_{0}}\left({1-{p_{0}}^{h}}\right)}{{1-{p_{0}}}}\right] \tag{5}\]  
In Equation (4), \(FPP_{D}\) denotes the probability that at least one \(sd\) candidate exists. The effective false positive probability \(eFPP_{D}\) corresponds to the probability that such \(sd\) exists within the specified [\(L\), \(U\)] range. \[eFPP_{D}=1-p_{f}=1-\frac{1}{h}\cdot\sum_{U=0}^{h-1}{p_{0}}^{U+1}=1-\frac{1}{h} \cdot\left[\frac{{p_{0}}\left({1-{p_{0}}^{h}}\right)}{{1-{p_{0}}}}\right] \tag{6}\]  
\(eFPP_{D}\) in Equation (6) is still higher than the \(FPP_{S}\) of Equation (4). However, the distance-encoded Bloom filter can predict the existence of a matching prefix at the current level based on whether the \(sd\) value is 0. The false positive probability of _prefix prediction_, \(FPP_{p_{f}x}\) is calculated as follows:  
\[FPP_{p_{f}x}=1-p_{0}=1-\left[1-(1-p_{2})^{k}\right]=\left(1-p_{2}\right)^{k} =\left(1-\left(1-\frac{s}{m}\right)^{kn}\right)^{k} \tag{7}\]  
If \(s\) approaches 1, \(FPP_{p_{f}x}\) gets closer to \(FPP_{S}\).