Skip Navigation

The Computer Journal 2000 43(1):54-64; doi:10.1093/comjnl/43.1.54
© 2000 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Berkovich, S. Y.
Right arrow Articles by El-Qawasmeh, E.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Reversing the Error-Correction Scheme for a Fault-Tolerant Indexing

Simon Y. Berkovich1 and Eyas El-Qawasmeh1

1 Department of Computer Science, The George Washington University, Washington D.C. 20052, USA Email: berkov@seas.gwu.edu

The paper presents an innovative approach to approximate matching of multi-attribute objects based on reversing of the conventional scheme of error-correction coding. Approximate matching problems primarily arise in information retrieval systems storing fuzzily described items and operating with nebulous searching criteria. Applying a decoding procedure to binary vectors corresponding to multi-attribute objects, the obtained message words can be used as indices of these objects, so certain mismatches in their attributes can be tolerated. This technique is mostly efficient when the error-correcting code is perfect. Thus, the simplest practical choice for the realization of this technique is based on the so-called perfect Golay code that maps 23-bit vectors into 12-bit message words. In this case, two different 23-bit vectors at a Hamming distance of 2 would have some common 12-bit indices. This allows the organizing of a direct retrieval of a neighbourhood of 23-bit vectors with up to two mismatches from a given key. The proposed technique employs a reasonable redundancy and can trade utilization of extra memory for the speed and range of searching.

Received 23 March, 1999. Revised 15 November, 1999.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.