Title: Fast approximate hash table using extended counting Bloom filter

Authors: Jinhong Zhou; Chao Wang; Xi Li; Xuehai Zhou

Addresses: Embedded System Laboratory, Suzhou Institute for Advanced Study of USTC, No. 166, Ren'ai Road, Suzhou Dushu Lake Higher Education Town Suzhou, Jiangsu 215123, China ' Embedded System Laboratory, Suzhou Institute for Advanced Study of USTC, No. 166, Ren'ai Road, Suzhou Dushu Lake Higher Education Town Suzhou, Jiangsu 215123, China ' School of Computer Science and Technology, West Campus of USTC, Room 421, DianSan Building, No. 443, Huang Shan Road, Hefei, Anhui 230027, China ' School of Computer Science and Technology, West Campus of USTC, Room 421, DianSan Building, No. 443, Huang Shan Road, Hefei, Anhui 230027, China

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.

Keywords: approximate hash table; counting Bloom filter; on-chip memory; off-chip memory; high performance retrieval; simulation.

DOI: 10.1504/IJCSE.2015.073497

International Journal of Computational Science and Engineering, 2015 Vol.11 No.4, pp.380 - 390

Received: 18 Sep 2013
Accepted: 02 Nov 2013
Published online: 10 Dec 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article