# A New Bloom Filter Architecture
## 3 Proposed Algorithm
### 2-Phase Bloom Filter Architecture
#### 3.2.2 Search  
Figure 3 also shows a brief overview of the search procedure of the proposed architecture. The search procedure proceeds by interactively querying the \(l\)-BF and the \(p\)-BF. By querying the \(l\)-BF, the level is returned. The returned level is used in querying the \(p\)-BF, and the output face is obtained. This process is repeated until a negative result is returned in \(l\)-BF. For example, assume an input \(com/youtube/user/image\). The \(l\)-BF is first queried using \(com\) as the hash key. If at least one non-conflict cell exists, the \(l\)-BF returns level value 4. Since the returned value is larger than the number of components used in querying, it can be noticed that node \(com\) is an LP-node. The \(p\)-BF is queried with the key \(com/youtube/user/image\). In this case, the \(p\)-BF returns a negative result. Hence, the \(l\)-BF is queried again using \(com/youtube\) and returns 2. Since the level information returned by string \(com/youtube\) is the same as the number of components, node \(com/youtube\) is considered to be an ordinary node. Hence, the search procedure queries the \(l\)-BF again using \(com/youtube/user\). The \(l\)-BF returns a negative result, meaning that neither node \(com/youtube/user\) nor its children exist. Hence, level 2 is the last level and the \(p\)-BF is queried using \(com/youtube\). The search procedure is completed by returning output face 2. In this case, the total number of Bloom filter queries is 5, and no accesses to the off-chip hash table occur. As another example, assume input name \(com/facebook\). First, the \(l\)-BF is queried using \(com\) and returns level 4. However, since the number of input components is fewer than 4, the \(l\)-BF is queried again using \(com/facebook\). The \(l\)-BF then returns level 2. Since an ordinary node is accessed, the \(l\)-BF query should be continued, but there are no more input components. Hence, the \(p\)-BF is queried using \(com/facebook\). Subsequently, the \(p\)-BF returns the output face and the search is complete. In this case, the total number of Bloom filter accesses is 3, without any off-chip memory accesses. Figure 3: Proposed 2-phase Bloom filter architecture. Algorithm 1 describes the search procedure in detail, which consists of the \(l\)-BF query and the \(p\)-BF query. Algorithms 2 and 3 show the detailed querying procedure of the \(l\)-BF and the \(p\)-BF, respectively. ```
FunctionSearch(\(inName\)) \(BMPport\) = default; for(\(i=1\)toPlevel)do //Plevel is the depth of the LPT nodeType = queryLevelBF(\(inName\), \(i\), &match_lvl); if(nodeType == ORD)then last_match_lvl = \(i\); elseif(nodeType == PRI)then \(BMPport\) = queryPortBF(\(nodeType\), \(inName\), match_lvl, &indet_lvl); if(\(BMPport\)!= default)then break;  end if elseif(nodeType == NEG)then \(BMPport\) = queryPortBF(\(nodeType\), \(inName\), last_match_lvl, &indet_lvl); break; elseif(nodeType == INDET)then \(BMPport\) = queryPortBF(\(nodeType\), \(inName\), \(C\), &indet_lvl); // back-tracking break; else continue;  end if if(\(i==\)Plevel or \(C\))then //C is the number of components of the inName \(BMPport\) = queryPortBF(NEG, \(inName\), last_match_lvl, &indet_lvl); break;  end if  end if if(\(BMPport\) == INDET)then \(BMPport\) = searchHT(\(inName\), \(indet\_lvl\)); // search hash table for an indeterminable case  end if return\(BMPport\);  end if
```  
**Algorithm 1**Search Procedure  
For a given input name, querying the \(l\)-BF produces one of four types of results: ORD, PRI, NEG, and INDET, as shown in Algorithm 2. The ORD result occurs when an ordinary node is accessed. In this case, the current level is remembered as the \(last\_match\_lvl\), and the \(l\)-BF querying continues as shown in Algorithm 1. The PRI result occurs when an LP-node is accessed. In this case, the \(p\)-BF is queried using the returned level. If the \(p\)-BF returns the output face by producing a _positive_ result, the search immediately ends.