On hash-coding algorithms for partial-match retrieval

1 October 1974

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02724847,p. 95-103
https://doi.org/10.1109/swat.1974.17

Abstract

We examine the efficiency of generalized hash-coding algorithms for performing partial-match searches of a random-access file of binary words. A precise characterization is given of those hash functions which minimize the average number of buckets examined for a search; and a new class of combinatorial designs is introduced which permits the construction of hash functions with worst-case behavior approaching the best achievable average behavior in many cases.

Keywords

This publication has 4 references indexed in Scilit:

An ALGOL-based associative language
Communications of the ACM, 1969
Combinatorial Information Retrieval Systems for Files
SIAM Journal on Applied Mathematics, 1968
File organization schemes based on finite geometries
Information and Control, 1968
Outline for a multi-list organized system
Published by Association for Computing Machinery (ACM) ,1959