@Article{Riv76b, author = { Ronald L. Rivest }, title = { Partial-match retrieval algorithms }, journal = { SIAM J. Computing }, OPTyear = { 1976 }, OPTmonth = { March }, date = { 1976-03 }, pages = { 19--50 }, volume = { 5 }, number = { 1 }, doi = { 10.1137/0205003 }, publisher = { SIAM }, abstract = { We examine the efficiency of hash-coding and tree-search algorithms for retrieving from a file of $k$-letter words all words which match a partially-specified input query word (for example, retrieving all six-letter English words of the form S**R*H where ``*'' is a ``don't care'' character). We precisely characterize those balanced hash-coding algorithms with minimum average number of lists examined. Use of the first few letters of each word as a list index is shown to be one such optimal algorithm. A new class of combinatorial designs (called associative block designs) provides better hash functions with a greatly reduced worst-case number of lists examined, yet with optimal average behavior maintained. Another efficient variant involves storing each word in several lists. Tree-search algorithms are shown to be approximately as efficient as hash-coding algorithms, on the average. In general, these algorithms require time about $O(n^{(k - s)/k} )$ to respond to a query word with $s$ letters specified, given a file of $n$ $k$-letter words. Previous algorithms either required time $O(s \cdot n/k)$ or else used exorbitant amounts of storage. } }