Efficient set representation and membership testing are important in high-speed network measurement. Fast insertions, space efficiency, fast query, and low false positive rate are the core requirements of traffic measurement, but existing solutions, such as hash tables and Bloom filters(BFs), cannot satisfy these requirements simultaneously. The state-of-the-art cuckoo filter and its variants(CFs) rely on the random eviction relocation strategy to resolve hash collisions, improving space utilization while reducing false positives and maintaining high query efficiency. However, CFs suffer a critical challenge in practical applications: insertion could trigger multiple evictions when all candidate buckets for an element are saturated, leading to insertion performance degradation, especially when space utilization exceeds 0.8. To solve the above problem, we propose a novel relocation strategy based on a random graph model, called the local minimum strategy. Our core idea is to use the implicit meaning of the number of evictions in each bucket as an indication to minimize the relocation of elements. We theoretically and experimentally prove that the eviction threshold for each bucket is$O(\log m)$, where$m$is the number of buckets. The threshold establishes the bounds for the probability of a successful insertion. The experimental results show that, the local minimum strategy significantly reduces the number of relocations by 67 %, as well as increasing the insertion throughput by more than 10 %.

Set query is a fundamental problem in computer systems. Plenty of applications rely on the query results of membership, association, and multiplicity. A traditional method that addresses such a fundamental problem is derived from Bloom filter. However, such methods may fail to support element deletion, require additional filters or apriori knowledge, making them unamenable to a high-performance implementation for dynamic set representation and query. In this paper, we envision a novel sketch framework that is multi-functional, non-parametric, space efficient, and deletable. As far as we know, none of the existing designs can guarantee such features simultaneously. To this end, we present a general shifting framework to represent auxiliary information (such as multiplicity, association) with the offset. Thereafter, we specify such design philosophy for a hash table horizontally at the slot level, as well as vertically at the bucket level. Theoretical and experimental results jointly demonstrate that our design works exceptionally well with three types of set queries under small memory.

Sketches are widely deployed to represent network flows to support complex flow analysis. Typical sketches usually employ hash functions to map elements into a hash table or bit array. Such sketches still suffer from potential weaknesses upon throughput, flexibility, and functionality. To this end, we propose Ark filter, a novel sketch that stores the element information with either of two candidate buckets indexed by the quotient or remainder between the fingerprint and filter length. In this way, no further hash calculations are required for future queries or reallocations. We further extend the Ark filter to enable capacity elasticity and more functionalities (such as frequency estimation and top-$k$query). Comprehensive experiments demonstrate that, compared with Cuckoo filter, Ark filter has$2.08\times$,$1.34\times$, and$1.68\times$throughput of deletion, insertion, and hybrid query, respectively; compared with Quotient filter, Ark filter has$4.55\times$,$1.74\times$, and$22.12\times$throughput of deletion, insertion, and hybrid query, respectively; compared with Bloom filter, Ark filter has$2.55\times$and$2.11\times$throughput of insertion and hybrid query, respectively.

Cuckoo filter (CF) and its variants are emerging as replacements of Bloom filters in various networking and distributed systems to support efficient set representation and membership testing. Cuckoo filters store item fingerprints directly with two candidate buckets and a reallocation scheme is implemented to mitigate the bucket overflow problem for higher space utilization. Such a reallocation scheme, once triggered, however, can be time-consuming. This shortcoming makes the existing CFs not applicable for insertion-intensive scenarios such as online applications wherein the items join and leave frequently. To this end, in this paper, we propose the Vertical Cuckoo filter (VCF) which extends the standard Cuckoo filter by providing more candidate buckets to each item. Another challenging issue with such a design is how to ensure that the candidate buckets can be indexed by each other such that no additional hash computation and item access are necessary during fingerprint reallocation. Therefore, we present the vertical hashing, which indexes the candidate buckets with the fingerprint and given bitmasks. We further generalize and improve the VCF by realizing$k$(≥ 4) candidate buckets and avoiding unnecessary computation. The comprehensive experiments indicate that VCF outperforms its same kinds in terms of space utilization and insertion throughput, with a slight compromise of lookup speed.

Cuckoo filter (CF), Bloom filter (BF) and their variants are space-efficient probabilistic data structures for approximate set membership queries. However, their data synopsis would inevitably become unusable when there are a number of member updates on the set; while updates are not uncommon for the real-world data streaming applications such as duplicate item detection, malicious URL checking, and caching applications. It has been shown that some variants of BF can be adaptive to stream applications. However, current extensions of BF structures generally incur unstable performance or intolerant membership testing errors. In this paper, we aim to design a data synopsis for membership testing on data streams with stable performance and tolerant query errors. To this end, we propose Stable Cuckoo Filters (SCF), which take a fine-grained manner to evict the stale elements and store those more recent ones. SCF absorbs the design philosophy from several unsuccessful designs. Specifically, SCFs take elegant update operations to embed time information with insertion operation and carefully evict the stale elements. We show that a tight upper bound of the expected false positive rate (FPR) remains asymptotically constant over the insertion of new members. The query error for recent elements of SCF (FNR) is related to the characteristics of the input data stream and query workloads. Extensive experiments on the real-world and synthetic datasets show that our designs are more stable than the existing variants of BF and realize 7 x smaller false errors and up to 3 x throughput.