許容される誤差を伴うハッシュコーディングの空間/時間トレードオフ

本論文では、ハッシュコーディングにおける特定の計算要因間のトレードオフが分析されます。考慮されるパラダイム問題は、一連のメッセージを一つずつ指定されたメッセージセットのメンバーシップのためにテストすることです。二つの新しいハッシュコーディング手法が検討され、特定の従来のハッシュコーディング手法と比較されます。考慮される計算要因は、ハッシュ領域のサイズ（空間）、指定されたセットの非メンバーとしてメッセージを特定するのに必要な時間（拒否時間）、および許容される誤差頻度です。新しい手法は、従来の方法に関連するハッシュコーディング情報を格納するために必要な空間量を削減することを目的としています。空間の削減は、特に大量のデータが関与し、従来の方法を使用してコア常駐のハッシュ領域が実現不可能なアプリケーションにおいて、少量のエラーを許容できる可能性を利用することによって達成されます。そのようなアプリケーションでは、新しい手法とともに小さなコア常駐ハッシュ領域を使用することで全体的なパフォーマンスが改善されることが見込まれ、必要に応じて新しい手法に関連する少数のエラーを「キャッチ」するために、二次的で時間のかかるテストを使用することが検討されています。新しい手法の適用可能な領域を示す例が議論されます。パラダイム問題の分析は、少数のテストメッセージが指定されたセットのメンバーとして誤って特定されることを許すことで、拒否時間を増加させることなくはるかに小さなハッシュ領域を使用できることを示しています。