Fast approximate hash table using extended counting Bloom filter
by Jinhong Zhou; Chao Wang; Xi Li; Xuehai Zhou
International Journal of Computational Science and Engineering (IJCSE), Vol. 11, No. 4, 2015

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.

Online publication date: Thu, 10-Dec-2015

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Computational Science and Engineering (IJCSE):
Login with your Inderscience username and password:

    Username:        Password:         

Forgotten your password?


Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com