Fast approximate hash table using extended counting Bloom filter Online publication date: Thu, 10-Dec-2015
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
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:
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