This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.
带有允许误差的哈希编码中的空间／时间权衡
BURTON H. BLOOM
Computer Usage Company，Newton Upper Falls，Mass.
本文分析了哈希编码中某些计算因素之间的权衡。所考虑的典型问题是逐一测试一系列消息，以确定它们是否属于给定的消息集合。我们考察了两种新的哈希编码方法，并将其与一种特定的传统哈希编码方法进行比较。所考虑的计算因素包括哈希区域的大小（空间）、确定某消息不是给定集合成员所需的时间（拒绝时间），以及允许的错误频率。
新方法旨在减少存储哈希编码信息所需的空间，使其低于传统方法所需的空间。空间的减少是通过利用这样一种可能性实现的：在某些应用中，少量的误判错误可能是可以容忍的，尤其是在涉及大量数据、因而使用传统方法无法将哈希区域驻留于内存中的应用中。
在此类应用中，可以设想，通过结合使用新方法和较小的内存驻留哈希区域，并在必要时采用某种辅助的、可能耗时的测试来“捕获”与新方法相关的少量错误，从而提高整体性能。文中讨论了一个示例，以说明新方法可能的应用领域。
References
- Batson, A. The organization of symbol tables. Comm. ACM 8, 2 (Feb. 1965), 111–112.
- Maurer, W. D. An improved hash code for scatter storage. Comm. ACM 11, 1 (Jan. 1968), 35–38.
- Morris, R. Scatter storage techniques. Comm. ACM 11, 1 (Jan. 1968), 38–44. | TABLE I. SUMMARY OF EXPECTED PERFORMANCE OF HYPHENATION APPLICATION OF HASH CODING USING METHOD 2 FOR VARIOUS VALUES OF ALLOWABLE FRACTION OF ERRORS | | | | --- | --- | --- | | P = Allowable Fraction of Errors | N = Size of Hash Area (Bits) | Disk Accesses Saved | | $\frac{1}{2}$ | 72,800 | 45.0% | | $\frac{1}{4}$ | 145,600 | 67.5% | | $\frac{1}{8}$ | 218,400 | 78.7% | | $\frac{1}{16}$ | 291,200 | 84.4% | | $\frac{1}{32}$ | 364,000 |
- 2% | | $\frac{1}{64}$ | 509,800 |
- 5% |
Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 中文 by gpt-5, against glossary version 6. Translated from the English.