Sage Journals: Discover world-class research

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

Get full access to this article

View all access options for this article.

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,

Jiang,

Liu and

Chen, Scalable name lookup in NDN using effective name component encoding, in: 2012 IEEE 32nd International Conference on Distributed Computing Systems, 2012, pp. 688–697. doi:10.1109/ICDCS.2012.35.

SLCF: Single-hash lookup cuckoo filter

Abstract

Keywords

Get full access to this article

References