Partial-Match Retrieval Algorithms
Ronald L. Rivest · SIAM Journal on Computing · 1976
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 nk-letter words. Previous algorithms either required time $O(s \cdot n/k)$ or else used exorbitant amounts of storage.
Cited by 244 works. doi:10.1137/0205003
Authors
References
- The Art of Computer Programming
- Error-Correcting Codes.
- An Introduction to Probability Theory and Its Applications, Vol. 2
- Sorting and Searching
- An ALGOL-based associative language
- Quad trees a data structure for retrieval on composite keys
- ERROR CORRECTING CODES
- Trie memory
- An indirect chaining method for addressing on secondary keys
- Virtual Memory