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

带有允许误差的哈希编码中的空间／时间权衡

BURTON H. BLOOM

Computer Usage Company，Newton Upper Falls，Mass.

本文分析了哈希编码中某些计算因素之间的权衡。所考虑的典型问题是逐一测试一系列消息，以确定它们是否属于给定的消息集合。我们考察了两种新的哈希编码方法，并将其与一种特定的传统哈希编码方法进行比较。所考虑的计算因素包括哈希区域的大小（空间）、确定某消息不是给定集合成员所需的时间（拒绝时间），以及允许的错误频率。

新方法旨在减少存储哈希编码信息所需的空间，使其低于传统方法所需的空间。空间的减少是通过利用这样一种可能性实现的：在某些应用中，少量的误判错误可能是可以容忍的，尤其是在涉及大量数据、因而使用传统方法无法将哈希区域驻留于内存中的应用中。

在此类应用中，可以设想，通过结合使用新方法和较小的内存驻留哈希区域，并在必要时采用某种辅助的、可能耗时的测试来“捕获”与新方法相关的少量错误，从而提高整体性能。文中讨论了一个示例，以说明新方法可能的应用领域。

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.

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 the 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.

KEY WORDS AND PHRASES: hash coding, hash addressing, scatter storage, searching, storage layout, retrieval trade-offs, retrieval efficiency, storage efficiency CR CATEGORIES: 3.73, 3.74, 3.79

This section is missing here.

Introduction