# A Distance-Encoded Bloom Filter for Fast NDN Name Lookup
## 3 Proposed Scheme
### Name Lookup Using a Distance-Encoded Bloom Filter  
Similar to binary search, name lookup using the distance-encoded Bloom filter advances to a longer range if the current level passes the membership test, and otherwise, shifts to a shorter range.  
Figure 11 illustrates the name lookup process using a distance-encoded Bloom filter. Given a name \(t\) and an initial search range [\(L\), \(U\)], the process first pre-checks whether the name at level \(m\), denoted as \(t\) [1:\(m\)], is a matching node where \(m=(L+U)/2\), or any initial starting level. Two distance values, \(\langle sd,ld\rangle\), are obtained as the output of the Bloom filter, BF (\(t\) [1:\(m\)]). If the \(sd\) value exists in the output, it means the Bloom filter indicates a positive match. In this case, the search should continue to find a longer matching node. The new search range is the intersection of the interval derived from \(\langle sd,ld\rangle\), and the right half of the current range, i.e., \([m+sd,m+ld]\cap[m+1,U]\).  
If the search in the longer range fails, meaning that there is no longer a matching node, then the name at the current level \(m\) can be the LMP. In the earlier step, the Bloom filter indicated there is a matching node at level m. If \(sd=0\), the node is considered a prefix since the closest prefix is at distance 0. At this point, a hash table search is performed using \(t\) [1:\(m\)] to find the LMP. Note that the hash table search is only performed when the distance-encoded Bloom filter indicates the presence of a matching prefix at the current level and that prefix is the longest one. If the search fails both at the current level \(m\) and in the longer range, the search proceeds in the shorter range [\(L\), \(m-1\)].  
Figure 11: Name lookup algorithm using a distance-encoded Bloom filter.  
Figure 12 compares the distance-encoded Bloom filter and the conventional Bloom filter. We suppose that the FIB and distance-encoded Bloom filter contents are structured as shown in Figure 7 and that the lookup target content name is /a/b/c/d/e/F/vr. In Step 1, both Bloom filters begin with the search range [1,7], querying the Bloom filter at level 4 with /a/b/c/d. In the case of the conventional Bloom filter, which follows binary search, the lookup always starts at the middle level (level 4). However, for the distance-encoded Bloom filter, the starting level is flexible; it could begin at the most popular level (where most prefixes exist), but for this example, we assume it also starts at level 4.  
In the distance-encoded Bloom filter, the BF (/a/b/c/d) output is \(\langle 2,3\rangle\), indicating a positive result. Using the \(sd\) and \(ld\) values (\(\langle 2,3\rangle\)), the next search range is obtained as [6,7], marking Step 2. At this step, the midpoint of the search range is level 6, and BF (/a/b/c/d/e/F) returns \(\langle 0,0\rangle\), which is also positive. Since \(sd=ld=0\), this implies that the LMP may exist at the current level. As a result, Bloom filter access stops here, and a hash table lookup is performed for /a/b/c/d/e/F.  
For binary search using the conventional Bloom filter, the search range halves with each Bloom filter access, and the next lookup level is always the midpoint of the current range. In Step 2, the Bloom filter access at level 6 returns a positive result, so the next step proceeds to level 7. For /a/b/c/d/e/F/vr, which corresponds to level 7, the Bloom filter lookup result is negative. Additionally, since no further search range remains, Bloom filter access terminates. Consequently, the last successful lookup at level 6 (/a/b/c/d/e/F) triggers the hash table search.