# A New Bloom Filter Architecture
## 3 Proposed Algorithm
### Level-Priority Trie  
The motivation of the proposed LPT begins with applying the p-NPT for name lookup. Since the number of components of a name prefix stored in a priority node is not constant, each priority node should provide the number of components of the name prefix, which in our terminology is the level information. While the p-NPT only removes the longest name prefix in the sub-trie of an empty node by relocating it to the priority node, the LPT removes all of the name prefixes in the longest level by storing the longest level information in the level priority node.  
Figure 2 shows the level-priority trie (LPT) transformed from the NPT shown in Figure 1. Since an NPT is expected to have many empty nodes, the LPT is constructed by repeatedly removing empty nodes (except for the root node) and storing the level information of the longest prefix. Each empty node becomes a level-priority node (LP-node) by storing the longest level information of its own sub-trie as well as removing every black node with a prefix in the longest level. The gray-colored nodes in Figure 2 are LP-nodes. For example, as an empty node, node _con_ in Figure 1 is transformed into an LP-node in the LPT as shown in Figure 2, and stores level 4, because the longest level of its sub-trie is 4. Each non-deleted black node stores its own level. Therefore, the LPT is a lightweight trie that only stores level information, and the total number of nodes of the LPT is much lower than that of the NPT or that of the p-NPT (because every black node in the longest level is deleted). Figure 2 also shows a hash table storing the output face of each name prefix. Since the nodes in the LPT only store level information, a hash table is required in order to obtain the output face of the best matching name prefix.  
Figure 2 shows a brief overview of the search procedure. When the LPT is searched, if an ordinary node is encountered, the level is remembered, and the search procedure proceeds to the next level. When there are no further nodes to follow, the hash table is accessed for the last matching level. Otherwise, if an LP node is encountered, the hash table is immediately accessed, since the LPT returns the longest level. If the input matches the name prefix at the returned level in the hash table, the search for a given input can be completed. In the case that the hash entry does not match the input at the returned level, the search procedure returns to the next level of the LPT.  
For an example of a search, for an input \(com/youtube/user/image\), since the first component \(com\) reaches an LP-node with level information 4, the hash table is accessed using the string of \(com/youtube/user/image\) as the hash key. The hash table entry does not match the string, and hence, the search procedure returns to the LPT. At the next level, the first two components \(com/youtube\) reach an ordinary node with level information 2. If the node has a matching child, the search should continue on to the next level. However, since the node does not have any children, the hash table is accessed using the string of \(com/youtube\). The hash entry returns output face 2, and the search procedure is complete.