Finding top-$k$frequent items has been a hot issue in databases. Finding top-$k$persistent items is a new issue, and has attracted increasing attention in recent years. In practice, users often want to know which items are significant,i.e., not only frequent but also persistent. No prior art can address both of the above two issues at the same time. Also, for high-speed data streams, prior art cannot achieve high accuracy when the memory is tight. In this paper, we define a new issue, named finding significant items, and propose a novel algorithm namely LTC to address this issue. It includes two key techniques, Long-tail Restoring and CLOCK, as well as three optimizations. In addition, LTC is extended to support finding significant items with thresholds. We theoretically derive the correct rate and error bound, and conduct extensive experiments on three real datasets to test the performance of LTC. Our experimental results show that LTC can achieve$10^5$times higher accuracy in terms of average relative error than other related algorithms. Lastly, LTC is applied to a DDoS detection task and it shows that finding significant items is more powerful than finding frequent items.

Finding top-k frequent items has been a hot issue in databases. Finding top-k persistent items is a new issue, and has attracted increasing attention in recent years. In practice, users often want to know which items are significant, i.e., not only frequent but also persistent. No prior art can address both of the above two issues at the same time. Also, for high-speed data streams, they cannot achieve high accuracy when the memory is tight. In this paper, we define a new issue, named finding top-k significant items, and propose a novel algorithm namely LTC to address this issue. It includes two key techniques: Long-tail Replacement and a modified CLOCK algorithm. We theoretically prove there is no overestimation error and derive the correct rate and error bound. We conduct extensive experiments on three real datasets. Our experimental results show that LTC achieves 300~10^8 and in average 10^5 times higher accuracy than other related algorithms.

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.

Sketch is a data structure used to record frequencies of items in a multiset, which is widely used in data streams, data graph, distributed datasets processing, etc. It works with small memory usage and a high speed at the cost of a slight inaccuracy. In practice, frequencies of items in many datasets are non-uniformly distributed. Unfortunately, existing sketches can hardly work well on non-uniform datasets. To address this issue, we propose a new sketch framework, namely ABC framework, which can be applied to most existing sketches and can significantly improve the accuracy on non-uniform datasets. The key idea behind our framework is that when a counter overflows, it makes use of the space from the adjacent counters by operations of bits-borrowing and combination. Extensive experimental results show that our ABC framework improves the accuracy by 4.10 times and 4.49 times in average, respectively. A demo and all the related source codes are available on our homepage [1].

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].

Set queries are fundamental operations in computer networks. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a shifting bloom filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF-based set data structures allocate additional memory to store auxiliary information. We further extend our shifting framework from BF-based data structures to sketch-based data structures, which are widely used to store multiplicities of items. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.

Fitting large and ever increasing routing tables in small on-chip memory is just like fitting an elephant in a box, which has been considered as impossible. In this paper, we propose the data structure of two-Dimensional Division Bloom Filter (D2BF) that can compactly encode almost all the needed information for performing IP lookup from a FIB in small on-chip memory. With pipelining, we further achieve the throughput of one packet per on-chip memory access.