Fast approximate hash table using extended counting Bloom filter. (2015)

• Record Type: Journal Article
• Authors: Zhou, Jinhong; Wang, Chao; Li, Xi; Zhou, Xuehai
• Is Part Of: International journal of computational science and engineering. Volume 11:Number 4(2016)
• Page Start: 380
• Page End: 390
• Publication Date: 2015
• Subjects: approximate hash table -- counting Bloom filter -- on-chip memory -- off-chip memory -- high performance retrieval -- simulation; Computer science -- Mathematics -- Periodicals; Computer simulation -- Mathematical aspects -- Periodicals; Computational intelligence -- Periodicals; 004.015105
• Languages: English
• ISSNs: 1742-7185

Abstract

Naive hash table (NHT) scheme associates a set of keys to a set of values. Apart from hash address computation, the search operation of the traditional scheme still brings three parts of overhead: key storage overhead, key memory access overhead, as well as key comparison overhead. They are significant especially when the hash table is too large to be implemented in slow off-chip memory. Therefore how to efficiently store keys in hash table is still posing serious challenges to researchers. In this paper, we propose a fast approximate hash table (FAHT) scheme which can eliminate these three parts of overhead with very small false rate. Theoretical analysis and data simulation are presented. The experiment results show that, with the same configuration, when the size of key is 128 bytes, FAHT uses 79% less memory than the NHT used, and if the hash address computation time is ignored, the speedup of FAHT comparing with NHT can be 199.