Gray code chaining: a high performance hashing algorithm for limited storage applications. (8th December 2008)

• Record Type: Journal Article
• Authors: Loeb, Mitchell; Tharp, Alan L.
• Is Part Of: International journal of high performance systems architecture. Volume 1:Number 3(2008)
• Page Start: 143
• Page End: 149
• Publication Date: 2008-12-08
• Subjects: high performance hashing -- external memory -- embedded systems -- real-time systems -- sensor systems -- TCC -- tridirectional computed chaining -- GCC -- gray code chaining -- limited storage applications; Computer architecture -- Periodicals; Computer systems -- Periodicals; High performance computing -- Periodicals; 004.205
• Languages: English
• ISSNs: 1751-6528

Abstract

Hardware continues to evolve which implies that software and the data structures contained therein must also. Motes, Radio Frequency Identification (RFIDs) and embedded systems are examples of hardware which require updated software and storage structures because of limited amounts of storage. Even though processor speeds have increased significantly recently, access times for external storage have lagged. This paper introduces Gray Code Chaining (GCC), a hashing scheme which provides the best retrieval performance to date when storage is limited. In fact, the performance approaches the theoretical limit but uses only 40% of the storage otherwise needed for the link fields. Unlike other methods, its retrieval performance actually improves as the file size increases. The method is also easier to implement than previous chaining methods.