Investigation of golay code (24, 12, 8)‎ structure in improving search techniques

Abstract EN

This paper presents a new technique for hash searching that is designed for approximate matching problem of multi-attribute objects.

The suggested technique can be used for improving the search operation when the multi-attribute objects are partially distorted or when the searching criterion is not specified properly.

The suggested approach is based upon reversing the conventional scheme of Golay code (24, 12, 8), which maps 24-bit vectors into 12-bit message words.

In this technique, a multi-dimensional space is used to represent objects, where each object is given by a 24-bit vector.

The closeness of the objects is determined by partitioning a 24-dimensional cube.

In addition, the possibility of 1-bit distortions is considered through bit modifications of the 24-bit vectors.

Thus, we proposed a hash table of 4096 entries that is fault-tolerant in the sense that the index is the same for any two different 24-bit vectors that share the same sphere.

This allows organizing a direct retrieval of a neighborhood of 24-bit vectors with two or possibly more mismatches.

The simulation experiments measured the retrieval capabilities of the proposed system and the expected hash distribution.