SLCF: Single-hash lookup cuckoo filter

Abstract

Approximate Membership Query (AMG) data structures are widely used in the networking area recently. The most popular AMQ data structures are Bloom, Quotient and Cuckoo Filter (CF). The CF is more efficient than the Quotient and Bloom filters in term of the lookup time and false positive rate. An issue in CF is utilization of two hash functions in the query phase that increases the lookup time. Another issue is the relocation loop problem in the programming phase that attempts to find an empty bucket for the collied items. In this paper, a new approach called Single-hash Lookup Cuckoo Filter (SLCF) using one hash function to lookup an item is proposed. In the programming phase, SLCF utilizes a sequence of hash functions without any relocation to find an empty bucket and storing the overflowed items. It finds a bucket with an empty place and sets an index in the original bucket to the address of found bucket. To accelerate the query phase, a handle as a tiny part of the fingerprint is placed in conjunction with the index value in the bucket. In the query phase, only one hash function is used and if the queried item cannot be found in the bucket, the handle is investigated to membership checking. Otherwise, the second bucket pointed by the index is accessed. The simulation results for name search in the named data networking demonstrate that the lookup time is improved 27% for 16 million names in comparison to CF.

Keywords

Single hash-lookup Cuckoo filter approximate membership query Bloom filter

1. Introduction

Emerging the new paradigms in computer networking, such as Named Data Networking (NDN) and Software-Defined Networking (SDN) need efficient data structures with high-speed lookup time. In NDN, the name lookup in Forwarding Information Base (FIB) and Pending Interest Table (PIT) and in SDN, the many-field packet classification in the flow tables of forwarding devices are challenging problems. Therefore, the using of efficient data structures to design the FIB, PIT and flow tables are definitely important. On the other side, the Approximate Membership Query (AMQ) data structures have been used widely in the networking area in recent years. The popular AMQ data structures are Bloom, Quotient and Cuckoo filters. They use a small amount of memory and are able to identify whether an element is member of a set that previously programmed or not. An AMQ data structure can answer that an element is not definitely in a set or may exist in a set with high probability. Among the AMQ data structures, Cuckoo filter is the most recent one which has a lower false positive rate and faster lookup operation in comparison to the Bloom and Quotient filters. Cuckoo Filter (CF) [5] is a set-membership data structure based on the Cuckoo hash table [10]. It takes a fingerprint of the inserting items and then uses an array of buckets and two hash functions to locate the inserting items. If the first place is filled, it will be placed in second place. Accordingly, each inserted item always will be in one of its own places. In this paper, in the programming phase, when the first bucket is overflowed we utilize a set of k hash functions sequentially that generates different addresses, hence the generated addresses by means of the different hash functions are investigated until the empty bucket is found. The address of the found bucket is set as an entry in index-array. In the meantime, a handle field of the overflow bucket is filled with the tiny part of the fingerprint to accelerate the search operation in the query phase. In the query phase, a single-hash approach is utilized that performs the lookup operation using a single hash operation. In each bucket, an index-array in conjunction with a tiny part of fingerprints of overflowed items is used. The index-array is used to point to the overflowed items in the second bucket found by hash functions in the programming phase. The tiny part of a fingerprint which called handle is used for fast lookup. The handle is a small part of the most significant bits of the fingerprint. The simulation results for the name search in named data networking show that the proposed approach can improve the lookup throughput 27% for 16 million names in comparison to the Cuckoo filter. The main contribution of this paper is in the following:

Proposal of using a single hash function in the query phase of the Cuckoo filter to accelerate the search operation.

Proposal of using multiple hashing functions to find the bucket with the empty bucket to avoid the relocation problem in the Cuckoo filter.

The rest of this paper is organized as follows. Section 2 presents related research in this area. Section 4 introduces the single-hash lookup Cuckoo filter concept and the related algorithms. Section 5 describes the evaluation of the SLCF approach and the Section 6 concludes the paper.

2. Related work

Some efforts have been done to improve the lookup time of the Cuckoo filter. The “dynamic cuckoo filter” [9] enables reliable delete operation for a dynamic set and exploits a novel extendible and compressible structure to make the data structure space efficient. “SmartCuckoo” [15] is proposed to address relocation loop problem. They proposed a hashing scheme using a direct pseudo forest to placement of the inserted item that solves the endless loop in relocation phase. The “length aware cuckoo filter (LCAF) for IP lookup” [7] uses different numbers of hash functions to store and search for entries based on the prefix length popularity of routing entries. Using the LACF decrease the false positive rate while the memory usage is increased. A new general-purpose AMQ, the counting quotient filter (CQF) [11] supports approximate membership testing and counting the occurrences of items in a data set. This general-purpose AMQ is small and fast, has good locality of reference, scales out of RAM to SSD, and supports deletions, counting (even on skewed data sets), resizing, merging, and highly concurrent access. The paper reports on the structure’s performance on both manufactured and application-generated data sets. In their experiments, the CQF performs in-memory inserts and queries up to an order-of-magnitude faster than the original quotient filter, several times faster than a Bloom filter, and similarly to the cuckoo filter. New dynamic set intersection data structures, which we call 2–3 cuckoo filters and hash tables is introduced [4]. These structures differ from the standard cuckoo hash tables and cuckoo filters in that they choose two out of three locations to store each item, instead of one out of two, ensuring that any item in an intersection of two structures will have at least one common location in both structures. They use these structures to design improved algorithms for dynamic set intersection, which can, in turn, be used for answering triangle listing queries faster than with previous approaches, in the practical RAM and EM models. Name Component Encoding method has been proposed in [16] which speeds up the name lookup through encoding components to codes before searching in FIB. However, the mappings between components and codes are stored in a character trie, hence the encoding process will potentially slow down the name lookup noticeably.

In [8] a name prefix matching technique has been proposed that depends on using Bloom filter as a pre-searching tool before accessing the hashing-based name prefix trie. The main issue that arise when using Bloom filter is the use of multiple hash functions that slowing down the system.

In [1], the authors propose a new variant of membership query data structure, called quotient-based Cuckoo filter (QCF), that reflects a merging process between QF and CF to minimise the calculation overhead and employing it in a DPI system. QCF employs only two hash functions and consumes less calculation overhead than BF, QF, and CF. In [13], a new approach called fast two-dimensional filter with hash table (FTDF-HT) is proposed. In the proposed approach, a hash table storing the name prefixes, in a hierarchical manner, is only accessed when the proposed filter (FTDF) states that the name under querying exists. Thus, reducing the unnecessary access to the hash table. Moreover, the access to the hash table will be done with same hash function that is used for FTDF and this will minimize the search time.

In [14], a novel PIT implementation called FTDF-PIT for NDN is proposed. This new design depends on employing an approximate data structure that called fast two dimensional filter (FTDF) which has better performance than the other proposed filters (Bloom and Quotient filters).

In our proposed work, the standard cuckoo filter is improved to accelerate the query time and the relocation operation is overcome.

3. Cuckoo filter concept

The Cuckoo filter [5] is a compact data structure for approximate set-membership queries where elements can be added and removed dynamically in $O (1)$ time. Basically, it is a highly compact cuckoo hash table [10] that saves fingerprints (i.e., short hash values) for each element. To understand how Cuckoo filter works, it is necessary to explain cuckoo hash function first and then describing its algorithms.

3.1. Cuckoo hashing basics

Cuckoo hash table [10] consists of an array of buckets where each element has two candidate buckets specified by two hash functions $h_{1} (x)$ and $h_{2} (x)$ . The lookup procedure examines both buckets to check if either includes this element. Figure 1(a) depicts the example of inserting a new element x into a hash table that consists of 8 buckets, where x can be positioned in either buckets 2 or 6. If either of $x^{'} s$ two buckets is empty, the algorithm inserts x to that free bucket and the insertion algorithm terminates. If both buckets already contain elements, which is the situation in this example, the element chooses one of the candidate buckets (e.g., bucket 6), moving out the already inserted element (“a” in the example) and re-inserts this victim element to its own alternate position. In this example, displacing “a” triggers another relocation that moves existing element “c” from bucket 4 to bucket 1. This process may recur until an unoccupied bucket is found as explained in Fig. 1(c), or until a maximum number of displacements (which specified in advance) is reached. Despite that cuckoo hashing may execute a series of displacements, its insertion time is $O (1)$ .

Fig. 1.

(a) Before inserting element x. (b) After element x inserted. (c) A Cuckoo filter, two hash per element and functions and four entries per bucket.

3.2. Cuckoo filter algorithms

Insertion: As formerly explained, with standard cuckoo hashing, inserting new elements to an existing hash table needs some ways of accessing the original existing elements in order to specify where to relocate them if needed to make room for the new ones. CFs, however, only save fingerprints and consequently there is no way to restore and rehash the original keys to find their alternate positions. This issue has been addressed by Cuckoo filter through utilizing a mechanism called partial-key cuckoo hashing to derive an element’s alternate position depend on its fingerprint. If there is an element x. This hashing scheme computes the indexes of the two candidate buckets in the following way: $\begin{array}{l} (1) & \begin{aligned} h_{1} (x) = hash (x), \\ h_{2} (x) = h_{1} (x) \oplus hash (x^{'} s fingerprint) \end{aligned} \end{array}$

The role of $x o r$ operation in Eq. (1) is to guarantee a significant feature: $h_{1} (x)$ can also be computed from $h_{2} (x)$ and the fingerprint using the same equation. In general, to displace a key already in bucket i (no difference if i is $h_{1} (x)$ or $h_{2} (x)$ ), its alternate bucket j can be computed directly from the current bucket index i and the fingerprint saved in this bucket by Eq. (2): $\begin{matrix} (2) & j = i \oplus hash (fingerprint) \end{matrix}$

Therefore, an insertion only utilizes information in the table, and never has to retrieve the original element x. Lookup: The lookup process of a CF is quite simple. If we have an element x, the algorithm first utilizes Eq. (1) to compute $x^{'} s$ fingerprint and two candidate buckets. Next, these two buckets are examined: if any existing fingerprint in either bucket matches, the CF returns true, otherwise the filter returns false. It can be noticed that false negatives cannot be occurred as long as bucket overflow never happens. Deletion: It examines both candidate buckets for a given element. If any fingerprint matches in any bucket, one copy of that matched fingerprint is removed from that bucket. It is important to notice that deletion process does not have to clear the entry after deleting an element. This will avoids the “false deletion” issue when two element share one candidate bucket and also have the same fingerprint [5].

4. Single-hash lookup cuckoo filter

Single-hash Lookup Cuckoo Filter (SLCF) is a data structure for approximate set-membership based on the standard Cuckoo filter. SLCF uses multiple hash functions in the programming phase rather than doing relocation by removing items. During the insertion phase, if each address is filled, the algorithm calculates a new address using a new hash function.

Fig. 2.

(a) Schema of programming of SLCF with k hash functions. (b) SLCF query with one hashing function.

Figure 2(a) shows a schema of the programming phase of SLCF with k hash functions. In AMQ data structures, by given two hash functions, it can be generated others using an equation introduced by Kirsch and Mitzenmacher [6] as can be observed in Eq. (3). $\begin{matrix} (3) & {hash}_{i} (x) = {hash}_{1} (x) + i \times {hash}_{2} (x) \end{matrix}$ In Fig. 2(a), the number of buckets in CF and the number of entries in each bucket are represented as b and e respectively. Each bucket contains multiple entries and each entry contains one item. Relocate Index (RI) is an index array which consists of an address and a handle. The items which their initial places (their initial hash functions) are equal are showed with the same pattern. There are two items with the original places of the first bucket, however, they have inserted in the third and fourth buckets because of the overflow occurred in this bucket. When overflow occurs in a bucket during insertion and then the algorithm successfully inserts the item in another bucket, an address will be set as RI address in the former bucket which represents a pointer to the bucket contains successfully inserted item. A “handle” contains the r most significant bits of the fingerprint which is applied to verify that a queried item weather exists in the overflowed bucket or not (in this case, 8 bits). SLCF utilizes multiple hash functions rather than a loop as a novel approach to relocation in the programming phase, consequently, provides improved insertion time. Moreover, SLCF performs a lookup operation by calculating one hash function)Fig. 2(b)). The hash functions are utilized to find an empty place in the programming phase. Finally, after finding the empty bucket, SLCF stores the fingerprint in the bucket and sets an index which is pointing this bucket in the initially attempted bucket. This index assists access to the queried fingerprint in the lookup phase. However, this characteristic increases memory usage, we will demonstrate that it improves the lookup time of the query phase because there are not any requirements to calculate more than one hash function or performing an XOR operation in contrast to CF. Figure 3 shows an example of previously inserted items a, b and c in the SLCF. In this example, the algorithm’s initial attempt to insert item d has been unsuccessful because its first hash function is eaual to address 1, however, bucket 1 is full. Then the second hash function is calculated which its corresponding bucket has contained an empty entry for insertion. After insertion, an index is set for this item in the former bucket (bucket 1) toward the inserted bucket (bucket 2).

Fig. 3.

An example of initially stored items a, b, and c in the SLCF.

4.1. Insertion algorithm in SLCF

Algorithm 1 depicts the insertion procedure. Initially, the fingerprint of the given item x in line 2 and then the first hash function in line 3 are calculated. In lines 4–7, If the initial bucket which is obtained by the hash function has an empty entry, therefore, the fingerprint is inserted, otherwise, in lines 8 and 9, more hash functions are calculated until a maximum number of attempts (considered as 150). Then, in line 11, the fingerprint is inserted at this entry of the bucket and in line 12, the Most Significant Bits (MSB) of the fingerprint as the “handle” is extracted and in line 13, a Relocate Index (RI) for this fingerprint in the initial bucket toward the inserted bucket is set. The size of RI is equal to the sum of a tiny part of the fingerprint (the “handle”) and an index for containing the address of the inserted item’s bucket, which can be different depending on the implementation. We considered 8 bits of the fingerprint as the “handle”.

Algorithm 1

Insert

4.2. Lookup algorithm in SLCF

Algorithm 2 depicts the lookup procedure. Initially, the fingerprint of the given item x in line 2 and then the first hash function in line 3 are calculated. In line 4, if the algorithm finds the fingerprint in the bucket of the first hash functions’ bucket, then it is assumed that x exists in the CF in line 5, otherwise, the algorithm attempts to find an RI which contains the “handle” of x’s fingerprint in the bucket. If it is successful to find the RI (line 7) then it is assumed that x exists in the CF (line 8), and if more than one RI are found, the algorithm starts to discovering the RIs until it finds the fingerprint (lines 10–16). Otherwise, it returns a negative answer to discovering x’s fingerprint in the CF (line 17).

Algorithm 2

Lookup

4.3. Deletion algorithm in SLCF

Algorithm 3 depicts the deletion procedure. Initially, the fingerprint of the given item x in line 2 and the first hash function in line 3 are calculated. If it finds the fingerprint in the first hash function’s bucket (line 4), it will be deleted (line 5), otherwise, in lines 8–15, the algorithm attempt to find the fingerprint’s RI in the bucket. If it finds any RI, the RI will be deleted and the procedure will be terminated.

Algorithm 3

Delete

5. Experimental evaluation

Our approach is evaluated using JAVA language on a machine with the following specifications: Operating system is Microsoft Windows 10, the processor is Intel(R) Core(TM) i7-6500U CPU @ 2.50 GHz, 2 cores, 4 logical processors, 4MB cache and memory is 8GB DDR3 RAM. We utilized the standard dataset of Content Name Collection (CNC) which contains unique and different length names [12] generated for NDN networks. The dataset has the following features: Hierarchical infrastructure of URL names, no duplicates, ordered, lowercase and uppercase letters, application layer protocol removed, and “www” removed. There are some examples of the dataset names: “/com/vimeo/33561523”, “/com/canaryislandgoing/index.php”, “/com/blogspot/ cocinaconsilvia/2011/12/ turron-de-chocolate-con-almendras.html”, and “/com/facebook/ photo.php”

In the implementation, the utilized hash function for SLCF is xxHash [2] and for CF are xxHash and Murmur3. It is assumed $2^{22}$ as the number of the buckets and 32 bits for the fingerprint. In our implementation, each RI consists of 8 bits as the MSB (the “handle”) of the fingerprint and an integer number (32 bits) as the address, therefore it’s size equals to 40 bits.

We ran each experiment 20 times and then calculated the average results. Three existing approaches for name matching in NDN have been chosen for comparison with our approach: Bloom Hash (BH) [3], Components-Trie (CT) [16] and Name prefix trie with Bloom filter (NPT-BF) [8].

5.1. Lookup evaluation

Figure 4 shows the lookup throughput of BF, CF, Bloom Hash (BH) [3], Components-Trie (CT) [16], Name prefix trie with Bloom filter (NPT-BF) [8] and SLCF. We considered the number of entries per each bucket (e) equals to 4 because in this case, the memory usage is the most efficient [5]. The results in Fig. 4 demonstrate that SLCF improves lookup time by average approximately 19% in comparison to CF. The improvement of lookup time is due to that when the CF is on the verge of overflow, more items have been relocated, hence for more items it needs to calculate the second hash function. In addition, Fig. 4 shows that the SLCF outperforms the BH, CT, NPT-BF and CF and improves the lookup time.

Moreover, we evaluated the lookup procedure for different number of entries per each bucket which is shown in Table 1. The results demonstrate that lookup time is improved approximately by an average of 21%.

Fig. 4.

Lookup throughput comparison of BF, CF, SLCF, BH [3], CT [16], and NPT-BF [8].

Table 1

Lookup time comparison of BF, CF, and SLCF in milliseconds

Items	BF	e¹	CF	SLCF	i²
8,000,000	25824	2	5768	4473	22%
12,000,000	47216	3	8688	6952	20%
16,000,000	63123	4	12218	9644	21%
20,000,000	88835	5	15901	12348	22%
24,000,000	110740	6	19422	15413	21%

¹ Number of entries per each bucket of CF and SLCF.

² Improvement of SLCF than CF.

5.2. Insertion evaluation

Figure 5 shows the comparison of the insertion throughput. The results demonstrate that SLCF’s insertion throughput is improved than CF by average approximately 8%. In CF, time is lost in two ways while relocating an item. The first is calculating a hash function of the stored item’s fingerprint and performing an XOR operation and the second is performing the relocation operation. However, in SLCF, the only required operation is calculating a hash function without relocating the item.

Fig. 5.

Insertion throughput comparison of BF, CF, and SLCF.

5.3. Deletion evaluation

Figure 6 shows the comparison of the deletion throughput. The results demonstrate that SLCF is improved than CF by average approximately 9% of deletion time. This improvement is due to that in the CF if the algorithm does not found an item by the hash function, it performs an XOR operation to find the item. However, in SLCF, discovering the existence of an RI does not require any calculation.

Fig. 6.

Deletion throughput comparison between CF and SLCF.

5.4. Load factor evaluation

We evaluated the load factor (α) by means of an individual experiment. We performed it by inserting maximum possible items in order to obtain the overflow. The number of inserted items (the maximum number of possible insertable items) was different in CF and SLCF. Therefore the load factor using Eq. (4) is measured. $\begin{matrix} (4) & α = \frac{i}{b \times e} \end{matrix}$ The notations used in Eq. (4) are: i represents the number of inserted items, b represents the number of buckets in CF which each bucket contains e items, and e as the number of entries in each bucket. Each bucket contains multiple entries and each entry contains one item. Table 2 shows comparison of the load factor.

Table 2
Load factor comparison between CF and SLCF

e¹ CF SLCF i²

2 0.85 0.96 13%

3 0.93 0.97 4%

4 0.96 0.97 1%

5 0.97 0.98 1%

6 0.97 0.98 1%

e¹	CF	SLCF	i²
2	0.85	0.96	13%
3	0.93	0.97	4%
4	0.96	0.97	1%
5	0.97	0.98	1%
6	0.97	0.98	1%

¹ Number of entries per each bucket of CF and SLCF.

² Improvement of SLCF than CF.

The results demonstrate that SLCF is improved than CF by average approximately 4% in load factor. This improvement is significant if the number of entries per each bucket is lower. This improvement is due to that in SLCF, sufficient bit count is extracted depending on the number of buckets (22 bits in our evaluation) from the hash function in the inserting phase. There is a possible circumstance which the hash functions generated by Eq. (3) are repeated. To solve this problem in such cases, a different substring of the bits from one of the hash functions in Eq. (3) is extracted and utilized to generate others.

5.5. Memory consumption evaluation

Figure 7 shows the comparison of memory usage measured after insertion items.

Fig. 7.

Memory usage comparison of BF, CF, and SLCF.

It shows by average approximately 34% increase in memory usage. It is applied 32 bits for each address and 8 bits for each tiny fingerprint handle in an RI. In our experiment, CF and SLCF have $2^{22}$ buckets and different entry count per each bucket which have mentioned in Fig. 4.

5.6. False positive evaluation

The false positive rate in SLCF is increased than CF by average of approximately $6.34 \times 10^{- 5}$ . It is due to the cases that just one RI is found for a given item. Consider a given item x is not found in a bucket b, however exactly one corresponding RI for x exist in b which x’s address is toward a bucket b′. SLCF does not verify b′’s stored fingerprint to accelerate the lookup. The result of false positive is shown in Table 3. Based on the false positive values for different applications, this difference between SLCF and CF might be ignored. In addition, Fig. 8 depicts the false positive rate of SLCF and CF for different number of bucket and different values of load factor.

Table 3
False positive rate comparison between CF and SLCF

Inserted items Lookup items CF SLCF

7,000,000 8,000,000 2.01E-4 2.15E-4

9,000,000 10,000,000 2.14E-4 2.45E-4

11,000,000 12,000,000 2.11E-4 2.64E-4

13,000,000 14,000,000 2.21E-4 3.10E-4

15,000,000 16,000,000 2.16E-4 3.47E-4

Inserted items	Lookup items	CF	SLCF
7,000,000	8,000,000	2.01E-4	2.15E-4
9,000,000	10,000,000	2.14E-4	2.45E-4
11,000,000	12,000,000	2.11E-4	2.64E-4
13,000,000	14,000,000	2.21E-4	3.10E-4
15,000,000	16,000,000	2.16E-4	3.47E-4

Fig. 8.

False positive comparison between CF and SLCF. (a) In term of number of buckets. (b) In term of load factor.

As can be observed in Figs 8(a) and (b), the false positive of SLCF is close to the CF, while the lookup time of SLCF has been improved.

6. Conclusion

In this paper, a variation of Cuckoo filter called Single-hash Lookup Cuckoo Filter (SLCF) was proposed. The SLCF utilizes k hash functions in the programming phase to overcome the relocation overheads. It additionally utilized a relocation index to point to the bucket which stores overflowed items and a handle to store a tiny fingerprint of overflowed items. In the query phase, the SLCF uses a single hash function to perform the lookup. In this phase, initially, it will check the tiny fingerprint then, if there is more than one matched tiny fingerprint, the fingerprints in the overflowed bucket will be investigated.

References

Al-hisnawi and

Ahmadi, QCF for deep packet inspection, IET Networks 7(5) (2018), 346–352. doi:10.1049/iet-net.2017.0037.

Collet, xxHash – Extremely fast non-cryptographic hash algorithm, Online; accessed October-2017, https://github.com/Cyan4973/xxHash.

Dharmapurikar,

Krishnamurthy and

D.E.

Taylor, Longest prefix matching using bloom filters, IEEE/ACM Transactions on Networking 14(2) (2006), 397–409. doi:10.1109/TNET.2006.872576.

Eppstein,

M.T.

Goodrich,

Mitzenmacher and

M.R.

Torres, 2-3 cuckoo filters for faster triangle listing and set intersection, in: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, ACM, 2017, pp. 247–260. doi:10.1145/3034786.3056115.

Fan,

D.G.

Andersen,

Kaminsky and

M.D.

Mitzenmacher, Cuckoo filter: Practically better than bloom, in: Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, ACM, 2014, pp. 75–88.

Kirsch and

Mitzenmacher, Less hashing, same performance: Building a better bloom filter, Random Structures & Algorithms 33(2) (2008), 187–218. doi:10.1002/rsa.20208.

Kwon,

Reviriego and

Pontarelli, A length-aware cuckoo filter for faster IP lookup, in: 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), IEEE, 2016, pp. 1071–1072. doi:10.1109/INFCOMW.2016.7562258.

Lee,

Shim and

Lim, Name prefix matching using bloom filter pre-searching for content centric network, Journal of Network and Computer Applications 65 (2016), 36–47. doi:10.1016/j.jnca.2016.02.008.

Mitzenmacher,

Pontarelli and

Reviriego, Adaptive cuckoo filters, in: 2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, 2018, pp. 36–47. doi:10.1137/1.9781611975055.4.

10.

Pagh and

F.F.

Rodler, Cuckoo hashing, Journal of Algorithms 51(2) (2004), 122–144. doi:10.1016/j.jalgor.2003.12.002.

11.

Pandey,

M.A.

Bender,

Johnson and

Patro, A general-purpose counting filter: Making every bit count, in: Proceedings of the 2017 ACM International Conference on Management of Data, ACM, 2017, pp. 775–787.

12.

Schnurrenberger, The Content Name Collection, [Online; accessed October-2017], http://www.icn-names.net/download/unibas-icn-names-2016-08-cc-(1-5)_en.

13.

Shubbar and

Ahmadi, Efficient name matching based on a fast two-dimensional filter in named data networking, International Journal of Parallel, Emergent and Distributed Systems 34(2) (2019), 203–221. doi:10.1080/17445760.2017.1363202.

14.

Shubbar and

Ahmadi, A filter-based design of pending interest table in named data networking, Journal of Network and Systems Management 27(3) (2019), 1–22.

15.

Sun,

Hua,

Jiang,

Li,

Cao and

Zuo, SmartCuckoo: A fast and cost-efficient hashing index scheme for cloud storage systems, in: 2017 {USENIX}, Annual Technical Conference ({USENIX}{ATC} 17), 2017, pp. 553–565.

16.

Wang,

He,

Dai,

Meng,