Design of a near-minimal dynamic perfect hash function on embedded device
Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45) › 32_Refereed conference paper (with ISBN/ISSN) › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Title of host publication | International Conference on Advanced Communication Technology, ICACT |
| Pages | 457-462 |
| Publication status | Published - 2013 |
Publication series
| Name | |
|---|---|
| ISSN (Print) | 1738-9445 |
Conference
| Title | 15th International Conference on Advanced Communication Technology: Smart Services with Internet of Things!, ICACT 2013 |
|---|---|
| Place | Korea, Republic of |
| City | PyeongChang |
| Period | 27 - 30 January 2013 |
Link(s)
Abstract
There has been a general opinion that it is difficult to construct perfect hash tables with high load factor for large datasets having a million records. The problem is even more challenging if new records can be added to the hash table incrementally. In this article, we shall demonstrate the design of a dynamic perfect hash function on embedded device based on simple bit-shuffle and bit-extraction operations. The achievable load factor can be up to 100%, and the amortized memory cost of the hash function is about 7 to 15 bits per key for 32-bit keys. Incremental updates to the hash table are allowed. The perfect hash function for a dataset with 1 million keys can be constructed in a few seconds of CPU time. © 2013 GIRI.
Research Area(s)
- Dynamic Perfect Hash Table, Embedded System, Pipelined Architecture, Searching
Citation Format(s)
Design of a near-minimal dynamic perfect hash function on embedded device. / Pao, Derek; Wang, Xing; Lu, Ziyan.
International Conference on Advanced Communication Technology, ICACT. 2013. p. 457-462 6488228.Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45) › 32_Refereed conference paper (with ISBN/ISSN) › peer-review
