Nowadays, an explosive increase of the size of Forwarding Information Base (FIB) in backbone router makes IP lookup a challenging issue. An effective solution is to use Bloom filter. Because of its false positive, to boost longest prefix matching (LPM), sophisticated Bloom filter-based algorithms were proposed, which makes FIB updating extremely difficult. To address this issue, in this paper, we propose a novel IP lookup algorithm which prunes unneeded prefix probes incurred by false positive and supports FIB updating. Experimental results show that our algorithm can save approximately 7~24% on-chip memory space than the well-known PBF (longest Prefix matching using Bloom Filters) while keeping the same average number of probes of 1.003 per IP lookup. In other words, given a limited on-chip memory budget, our proposed algorithm can handle FIB 7~24% bigger than PBF. The source code can be found in [1].

Multi-set query is a fundamental issue in data science. When the sizes of multi-sets are large, exact matching methods like hash tables need too much memory, and they cannot achieve high query speed. Bloom filters are recently used to handle big data query, but they cannot achieve high accuracy when the memory space is tight. In this paper, we propose a new data structure named coloring embedder, which is fast, accurate as well as memory efficient. The insight is to first map elements to a high dimensional space to almost eliminate hashing collisions, and then use a dimensional reduction representation, which is similar to coloring a graph, to save memory. Theoretical proofs and experimental results show that compared to the state-of-the[1]art, the error rate of the coloring embedder is thousands of times smaller even with much less memory usage, and the query speed of the coloring embedder is about 2 times faster. The source code of coloring embedder is released on Github.

Per-flow measurement is a critical issue in computer networks, and one of its key tasks is to count the number of packets in each flow (for big streaming data). The literature has demonstrated that sketch is the most memory-efficient data structure for the counting task, and is widely used in distributed systems. Existing sketches often use many counters that are of the same size to record the number of packets in a flow, thus the counters are forced to be large enough to accommodate the size of the largest flow. Unfortunately, as most flows are small (i.e., mice flows) and only a very few flows are large (i.e., elephant flows), many counters represent very small values, which is a waste of memory. Sketches are often stored in fast but expensive memory (e.g., SRAM), thus it is critical to achieve high memory efficiency. To address this issue, we propose a novel sketch, namely the Diamond sketch. The Diamond sketch is composed of atom sketches, and each atom sketch uses small counters. The key idea of Diamond is to dynamically assign an appropriate number of atom sketches to each flow on demand, thus optimizing memory efficiency. Experimental results show that the Diamond sketch outperforms the best of the five typical sketches by up to 508.3 times in terms of relative error while keeping comparable speed. We made the source code of all the six sketches available on GitHub [1] .

The problem of multi-set membership query plays a significant role in many network applications, including routers and firewalls. Answering multi-set membership query means telling whether an element belongs to the multi-set, and if yes, which particular set it belongs to. Most traditional solutions for multi-set membership query are based on Bloom filters. However, these solutions cannot achieve high accuracy and high speed at the same time when the memory is tight. To address this issue, this paper presents the ID Bloom Filter (IBF) and ID Bloom Filter with ones' Complement (IBFC). The key technique in IBF is mapping each element to k positions in a filter and directly recording its set ID at these positions. It has a small memory usage as well as a high processing speed. To achieve higher accuracy, we propose IBFC that records the set ID and its ones' complement together. The experimental results show that our IBF and IBFC are faster than the state-of-the-art while achieving a high accuracy.

Given v sets and an incoming item e, multi-set membership query is to report which set contains item e. Multi-set membership query is a fundamental problem in computer systems and applications. All existing data structures cannot achieve small memory usage, fast query speed and high accuracy at the same time. In this paper, we propose a novel probabilistic data structure named Difference Bloom Filter (DBF) for fast multi-set membership query, which not only is more accurate than the state-of-the-art, but has a faster query speed. There are two key design principles for DBF. The first one is to make the representation of the membership of elements exclusive by writing different number of 1s and 0s in the same filter, and the second one is to use the slow but cheap DRAM memory to improve the accuracy of the filter on the fast but expensive SRAM memory. Experimental results show that in terms of accuracy, DBF has a great advantage compared to state-of-the-art, being hundreds of times more accurate than the state-of-the-art vBF and ShBF. Furthermore, we have made the source code of our DBF available at our homepage [1] and GitHub [2].