Title: Gray code chaining: a high performance hashing algorithm for limited storage applications

Authors: Mitchell Loeb, Alan L. Tharp

Addresses: IBM Corporation, Research Triangle Park, NC 27709, USA. ' Department of Computer Science, North Carolina State University, Raleigh, NC 27695-8206, USA

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.

Keywords: high performance hashing; external memory; embedded systems; real-time systems; sensor systems; TCC; tridirectional computed chaining; GCC; gray code chaining; limited storage applications.

DOI: 10.1504/IJHPSA.2008.021794

International Journal of High Performance Systems Architecture, 2008 Vol.1 No.3, pp.143 - 149

Published online: 04 Dec 2008 *

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