{"doi":"10.1145/362686.362692","title":"Space/time trade-offs in hash coding with allowable errors","abstract":"<jats:p>In this paper trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency.</jats:p>\n          <jats:p>The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods.</jats:p>\n          <jats:p>In such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to “catch” the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods.</jats:p>\n          <jats:p>Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time.</jats:p>","journal":"Communications of the ACM","year":1970,"id":2257,"datarank":30.140904888241323,"base_score":8.918784137975802,"endowment":8.918784137975802,"self_citation_contribution":1.3378176206963706,"citation_network_contribution":28.803087267544953,"self_endowment_contribution":1.3378176206963706,"citer_contribution":28.803087267544953,"corpus_percentile":98.1,"corpus_rank":2008,"citation_count":7470,"citer_count":200,"citers_with_citation_signal":200,"citers_with_endowment":200,"datacite_reuse_total":0,"is_dataset":false,"is_oa":true,"file_count":0,"downloads":0,"has_version_chain":false,"published_date":"1970-07-01","authors":[{"id":27799,"name":"Burton H. Bloom","orcid":null,"position":0,"is_corresponding":true}],"reference_count":3,"raw_metadata":{"citation_network_status":"fetched"},"created_at":"2026-03-01T18:20:47.508186Z","pmid":null,"pmcid":null,"fwci":null,"citation_percentile":null,"influential_citations":0,"oa_status":null,"license":null,"views":0,"total_file_size_bytes":0,"version_count":0,"clinical_trials":[],"software_tools":[],"db_accessions":[],"linked_datasets":[],"topics":[]}