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

許容誤りを伴うハッシュ符号化における空間／時間のトレードオフ

BURTON H. BLOOM

Computer Usage Company, Newton Upper Falls, Mass.

本論文では、ハッシュ符号化におけるいくつかの計算上の要因間のトレードオフを分析する。検討する典型的な問題は、メッセージの所与の集合への所属を、一連のメッセージについて一つずつ検査することである。2つの新しいハッシュ符号化法を検討し、特定の従来型ハッシュ符号化法と比較する。考慮する計算上の要因は、ハッシュ領域の大きさ（空間）、メッセージが所与の集合の非所属要素であることを識別するために必要な時間（拒否時間）、および許容可能な誤り頻度である。

新しい方法は、従来の方法に伴うものよりも、ハッシュ符号化された情報を格納するために必要な空間量を削減することを目的としている。空間の削減は、いくつかの応用では、誤って所属と判定する誤りのごく一部が許容され得る可能性を利用することによって達成される。特に、大量のデータを扱い、そのため従来の方法ではコア常駐のハッシュ領域が現実的でない応用が対象となる。

このような応用では、新しい方法と併用してより小さいコア常駐のハッシュ領域を使用し、必要に応じて、時間を要する可能性のある何らかの二次的な検査を行って、新しい方法に伴う誤りのごく一部を「捕捉」することにより、全体的な性能を向上できると考えられる。新しい方法の応用可能な領域を示す例についても論じる。

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