Document Type

Report

Date

2-1972

Embargo Period

4-25-2012

Keywords

Best match problem

Language

English

Disciplines

Computer Sciences

Description/Abstract

The "best-match problem" is concerned with the complexity of finding the best match between a randomly chosen query word and the members of a randomly chosen set of data words. Of principal interest is whether it is possible to significantly reduce the search time required, as compared to exhaustive comparison, by use of memory redundancy (file structure). Minskv and Papert conjecture that "the speed-up values of large memory redundancies is very small, and for large data sets with long word lengths there are no practical alternatives to large searches that inspect large parts of memory". For this report we present two algorithms that do yield significant speed-up, although at the cost of large memory redundancies. (Whether these algorithms constitute counterexamples to the Minskv-Papert conjecture depends on one's interpretation of their term “large memory redundancies".) The algorithms are subjected to statistical analysis and time-memory trade-off curves are given.

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.