SPACE/TIME TRADE/OFFS IN HASH CODING WITH ALLOWABLE ERRORS
SPACE/TIME TRADE/OFFS IN HASH CODING WITH ALLOWABLE ERRORS
复制标题
DOI：
10.1145/362686.362692
复制
发表时间：
1970-01-01
影响因子：
22.7
通讯作者：
BLOOM, BH
中科院分区：
文献类型：
--
作者：
BLOOM, BH
本文分析了散列编码中某些计算因素之间的权衡。考虑的范例问题是，测试一系列的消息一个接一个的成员在一个给定的消息集。两个新的散列编码方法进行了检查，并与一个特定的传统的散列编码方法进行了比较。考虑的计算因素是散列区域（空间）的大小，所需的时间来识别一个消息作为给定的集合的非成员（拒绝时间），和允许的错误频率。新的方法是为了减少所需的空间量包含散列编码的信息与传统的方法相关联。空间的减少是通过利用以下可能性来实现的：在一些应用中，特别是在涉及大量数据并且核心驻留散列区域因此使用常规方法不可行的应用中，一小部分调试错误可能是可容忍的。可以设想，通过结合新方法使用较小的核心驻留散列区域，并且在必要时，通过使用一些次要的并且可能是耗时的测试来“捕获”与新方法相关联的小部分错误。一个例子进行了讨论，说明了可能的应用领域的新方法。分析的范式问题表明，允许少量的测试消息被错误地识别为给定的集合的成员将允许一个小得多的哈希区域被使用，而不增加拒绝时间。
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.