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

5 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationInternational Conference on Advanced Communication Technology, ICACT
Pages457-462
Publication statusPublished - 2013

Publication series

Name
ISSN (Print)1738-9445

Conference

Title15th International Conference on Advanced Communication Technology: Smart Services with Internet of Things!, ICACT 2013
PlaceKorea, Republic of
CityPyeongChang
Period27 - 30 January 2013

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