Investigation of Golay Code (8, 12, 24) Structure
in Improving Search Techniques
Eyas El-Qawasmeh1, Maytham Safar2, and Talal Kanan3
1College of Computer and Information Sciences, King Saud University, Saudi Arabia
2Department of Computer Science, Jordan University of Science and Technology, Jordan
3Department of Computer Engineering, Kuwait University, Kuwait
1College of Computer and Information Sciences, King Saud University, Saudi Arabia
2Department of Computer Science, Jordan University of Science and Technology, Jordan
3Department of Computer Engineering, Kuwait University, Kuwait
Abstract: 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 (8, 12, 24), 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.
Keywords: Golay code, information retrieval, distortion, and hashing.
Received December 25, 2008; accepted August 3, 2009