Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Article type: Research Article
Authors: Najafimehr, Mohammad | Ahmadi, Mahmood; *
Affiliations: Department of Computer Engineering and Information Technology, Razi University, Kermanshah, Iran. E-mails: mnm1551@gmail.com, m.ahmadi@razi.ac.ir
Correspondence: [*] Corresponding author. E-mail: m.ahmadi@razi.ac.ir.
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
DOI: 10.3233/JHS-190624
Journal: Journal of High Speed Networks, vol. 25, no. 4, pp. 413-424, 2019
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl