# A Distance-Encoded Bloom Filter for Fast NDN Name Lookup
## 3 Proposed Scheme
### Query  
The Bloom filter access for a node provides both distance information and the membership test result simultaneously. If valid \(sd\) and \(ld\) values are obtained, the membership test result for that node is positive. For a query on node \(t\), a total of \(k\) words are retrieved from the Bloom filter. Each of these words contains a bit pointed to by the hash functions, \(h_{1}\left(t\right)\), \(h_{2}\left(t\right)\), \(\ldots\), \(h_{k}\left(t\right)\). If multiple hash functions point to the same word, the total number of retrieved words may be less than \(k\). In each word, the bit position pointed to by \(h_{i}\left(t\right)\) varies. However, for ease of processing, these bit positions are aligned so that the designated bit is positioned at the center. Specifically, a circular shift is applied to ensure that, in all words, the bit specified by \(h_{i}\left(t\right)\) is located at the bit position \((w/2-1)\). Figure 10 illustrates the process of obtaining \(sd\) and \(ld\) values from these aligned words. Figure 8: Comparison of a conventional Bloom filter and a distance-encoded Bloom filter: (a) conventional Bloom filter; (b) distance-encoded Bloom filter. Figure 9: Representation of \(sd\) and \((ld-sd)\) within the same word. The candidate vector is obtained by simply performing a bitwise-AND operation on \(k\) words. In this vector, the left half represents candidate values for \(sd\), while the right half represents candidate values for \((ld-sd)\). Since the candidate vector may contain bits that were set when other nodes were inserted into the Bloom filter, it can include spurious values. To obtain a valid next search range, \(sd\) must be interpreted as the smallest value, while \(ld\) must be the largest value. For a given node \(t\), the Bloom filter output, BF(\(t\)), produces \(\langle sd,ld\rangle\). These values are computed from candidate values for \(sd\) and \((ld-sd)\) as follows:  
\[max\_sd=\max\{x_{0},x_{1},\ldots,x_{c}\}\]  
\[sd=\min\{x_{0},x_{1},\ldots,x_{c}\}\]  
\[ld=\max\{y_{0},y_{1},\ldots,y_{d}\}+max\_sd\]  
where \(x_{i}\) and \(y_{i}\) are candidate values for \(sd\) and \((ld-sd)\), respectively. In Figure 10, the candidate values extracted from the set bit positions in the candidate vector are \(\{2,3\}\) for \(sd\) and \(\{1,2\}\) for \((ld-sd)\). The \(sd\) value is chosen as \(2\), the smallest value in \(\{2,3\}\), while \(ld\) is computed as the sum of the largest value in \(\{2,3\}\) and the largest value in \(\{1,2\}\), resulting in \(5\). Thus, the Bloom filter output for N\({}_{3}\), denoted as BF (N\({}_{3}\)), is \(\langle 2,5\rangle\). Since a valid \(\langle sd,ld\rangle\) pair has been obtained, the presence of N\({}_{3}\) is regarded as positive. Due to other nodes inserted into the Bloom filter, spurious values may appear. The result of BF (N\({}_{3}\)) may cover a larger range than the actual \(\langle sd,ld\rangle\) of N\({}_{3}\), but this range always encompasses the required search range. Let a node \(t\) have the actual distance range \([a,b]\), meaning that all of \(t^{\prime}s\) descendant prefixes in the trie lie at distance \(d\) satisfying \(a\leq d\leq b\). Suppose the Bloom filter returns BF(t) = \(\langle sd,ld\rangle\). The returned range \([sd,ld]\) always covers \([a,b]\), i.e., \(sd\leq a\) and \(ld\geq b\). A search range that fully covers the length range of all the prefixes to be searched is called a valid search range. If the Bloom filter output for a node \(t\), BF(t), is \(\langle sd,ld\rangle\), then the interval \([sd,ld]\) is always a valid search range and a positive membership result is indicated for \(t\). On the other hand, if BF(t) produces no output, meaning that there is no candidate value for \(sd\), then a negative membership result is indicated for \(t\). The decoding process to obtain the Bloom filter output, BF(t), can be efficiently performed with specialized hardware support. First, \(k\) words are fetched from on-chip memory based on \(k\) hash functions, as in a conventional Bloom filter.