Symbolic Gray Code as a Multikey Hashing Function

H. C. Du, R. C.T. Lee

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

In this paper, we extend the binary Gray code to symbolic Gray code. We then show that this symbolic Gray code can be used as a multikey hashing function for storing symbolic records. The record stored at location k and the record stored at location k + 1 will be nearest neighbors if this hashing function is used. Thus, this symbolic Gray code hashing function exhibits some kind of clustering property which will group similar records together. This property is a desirable property for designing nearest neighbor searching (also called best match searching) systems. There are many other interesting properties of this hashing function. For instance, there exists an address-to-key transformation which can be used to determine the record stored at certain location k if this hashing function is used. Besides, if there are totally M records, we only have to reserve exactly M locations; there are no collisions and wasting of memory storage. At the end of this paper, it is shown that the resulting file exhibits the multiple-attribute tree structure.

Original languageEnglish (US)
Pages (from-to)83-90
Number of pages8
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
VolumePAMI-2
Issue number1
DOIs
StatePublished - Jan 1980

Keywords

  • Address-to-key transformation
  • best match searching
  • binary Gray code
  • clustering property
  • key-to-address transformation
  • multikey hashing functions
  • multiple-attribute tree
  • nearest neighbor searching
  • partial match
  • symbolic Gray code

Fingerprint Dive into the research topics of 'Symbolic Gray Code as a Multikey Hashing Function'. Together they form a unique fingerprint.

Cite this