Space/Time Trade-offs in Hash Coding with Allowable Errors

In this paper trade-offs among certain computational factors
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.  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.  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 new methods.  An example is discussed
which illustrates possible areas of application for the new
methods.  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.

CACM July, 1970

Bloom, B. H.

hash coding, hash addressing, scatter storage, searching, storage
layout, retrieval trade-offs, retrieval efficiency, storage efficiency

3.73 3.74 3.79

CA700704 JB February 13, 1978  9:18 AM

1676	4	2033
1682	4	2033
1728	4	2033
1860	4	2033
1860	4	2033
1973	4	2033
1973	4	2033
1992	4	2033
2018	4	2033
2018	4	2033
2032	4	2033
2033	4	2033
2033	4	2033
2033	4	2033
2107	4	2033
2107	4	2033
2109	4	2033
2109	4	2033
2203	4	2033
2203	4	2033
2251	4	2033
2251	4	2033
2359	4	2033
2524	4	2033
2543	4	2033
2543	4	2033
2552	4	2033
2559	4	2033
2573	4	2033
2770	4	2033
2991	4	2033
3053	4	2033
1314	5	2033
1785	5	2033
1786	5	2033
2033	5	2033
2033	5	2033
2033	5	2033
3001	5	2033
2033	6	2033
2139	6	2033