商フィルター

商フィルタは、要素がセットのメンバーであるかどうかをテストするために使用される、スペース効率の高い確率的 データ構造です(近似メンバーシップ クエリ フィルタ、AMQ)。クエリは、要素がセットに確実に含まれていないか、要素がセットに含まれている可能性が高いかを指定する応答を引き出します。前者の結果は決定的です。つまり、テストでは偽陰性は生成されません。ただし、後者の結果では、要素が実際にはセットに存在しない (つまり、偽陽性)場合に、テストで「要素はセット内にあります」と返される確率 ε があります。偽陽性率 ε とストレージ サイズの間にはトレードオフがあり、フィルタのストレージ サイズを増やすと ε が減少します。その他の AMQ 操作には、「挿入」や「オプションで削除」などがあります。セットに追加される要素が多いほど、偽陽性の確率は高くなります。

商フィルターやその他の AMQ フィルターの一般的な用途は、ディスク上のデータベース内のキーのプロキシとして機能することです。データベースにキーが追加または削除されると、フィルターはこれを反映するように更新されます。検索ではまず高速な商フィルターを参照し、商フィルターがキーの存在を報告した場合にのみ (おそらくはるかに低速な) データベースを検索します。フィルターがキーが存在しないと返した場合、ディスク アクセスが実行されなくても、キーがデータベースに存在しないことがわかります。

商フィルターには、挿入とクエリという通常の AMQ 操作があります。さらに、元のキーを再ハッシュすることなく、マージやサイズ変更もできます (そのため、セカンダリ ストレージからそれらのキーにアクセスする必要がなくなります)。このプロパティは、特定の種類のログ構造化マージ ツリーに役立ちます。

商フィルタの基礎となるコンパクトなハッシュテーブルは、1984 年に Cleary によって説明されました。 ^[1]この構造を AMQ フィルタとして使用することについての最初の既知の言及は、2005 年のPaghらによるものです。^[2] 2009 年に、Dillinger と Manolios は構造のメタデータを最適化し、より多くの要素をインプレースで収容できるようにし、この構造を明示的状態モデル検査に適用しました。^[3] 2011 年に、Benderらは「商フィルタ」という名前を書き、メタデータ エンコーディングのトレードオフが異なるいくつかのバリエーションを説明し、商フィルタをマージしてサイズ変更する方法を示し、ディスクで使用するための商フィルタの書き込み最適化バージョンを提示し、この構造をデータベース ストレージの問題に適用しました。^{[4] [5]} 2017 年に、Pandeyらは、ハードウェア ビット操作命令を使用してパフォーマンスを向上させ、同時更新をサポートし、各要素に可変サイズのカウンタを関連付けるためのサポートを追加したバージョンを説明しました。^[6]

商フィルタは、エントリにキーの一部と追加のメタデータ ビットのみが含まれる一種のハッシュ テーブルに基づいています。これらのビットは、異なるキーが同じテーブル エントリにハッシュされる場合に対処するために使用されます。対照的に、オーバーフロー領域にリンクすることでこのような衝突に対処する他の種類のハッシュ テーブルは、リンクによるオーバーヘッドがキーを格納するために使用されるストレージを超える可能性があるため、コンパクトではありません。^[1]商フィルタでは、ハッシュ関数によってpビットのフィンガープリントが生成されます。最下位rビットは剰余と呼ばれ、最上位q = p - rビットは商と呼ばれ、これが商計算( Knuthによる造語)という名前です。^[7]ハッシュ テーブルには 2 つの^qスロットがあります。

フィンガープリントd _Hにハッシュされるキーdについて、その商をd _Q、剰余をd _Rとします。QF は剰余をスロット d _Q （標準スロットと呼ばれる）に格納しようとします。ただし、複数のキーが同じフィンガープリントにハッシュされる場合があるため（ハード衝突）、またはキーのフィンガープリントが異なっていても同じ商を持つことがあるため（ソフト衝突）、標準スロットがすでに使用されている可能性があります。標準スロットが使用されている場合、剰余は右側のスロットに格納されます。

以下に説明するように、挿入アルゴリズムは同じ商を持つすべての指紋が連続したスロットに格納されることを保証します。このような指紋のセットはランとして定義されます。 [ ^4] ランが左側のランによって右側に強制された場合、ランの最初の指紋はその標準スロットを占有しない場合があることに注意してください。

しかし、最初のフィンガープリントが正規のスロットを占める実行は、クラスターの開始を示します。^[4]最初の実行とその後のすべての実行はクラスターを構成し、空いているスロットまたは別のクラスターの開始で終了します。

追加の 3 つのビットは、スロットのフィンガープリントを再構築するために使用されます。これらのビットの機能は次のとおりです。

占有されている

スロットがフィルター内のどこかに格納されているキーの正規スロットである場合に設定されます (ただし、必ずしもこのスロット内である必要はありません)。

継続である

スロットが占有されているが、実行の最初の残りによって占有されていない場合に設定されます。

シフトされた

スロット内の残りが標準スロット内にない場合に設定されます。

さまざまな組み合わせには次の意味があります。

商フィルタにキーdが含まれているかどうかは次のようにしてテストできる。^[4]

キーをハッシュしてフィンガープリント d _Hを生成し、それを商を構成する上位 q ビット d _Qと剰余を構成する下位 r ビット d _Rに分割します。スロット d _Qはキーの正規スロットです。3 つのメタデータ ビットが false の場合、そのスロットは空になります。その場合、フィルターにはキーが含まれません。

標準スロットが占有されている場合は、商のランを見つける必要があります。同じ商に属する剰余を保持するスロットのセットは連続して格納され、これらが商のランを構成します。ランの最初のスロットが標準スロットである可能性がありますが、別のランの左側からの侵入によってラン全体が右にシフトされている可能性もあります。

商のランを見つけるには、まずクラスターの開始点を見つける必要があります。クラスターは連続したランのセットで構成されます。商の標準スロットから始めて、左にスキャンしてクラスターの開始点を見つけ、次に右にスキャンして商のランを見つけます。

左にスキャンして、 is_shiftedが false のスロットを探します。これはクラスターの開始を示します。次に、スキップする必要がある実行回数の実行カウントを維持しながら右にスキャンします。is_occupiedが 設定されている標準スロットの左側の各スロットは、スキップする別の実行を示しているため、実行カウントをインクリメントします。is_continuationが クリアされている各スロットは、別の実行の開始、つまり前の実行の終了を示しているため、実行カウントをデクリメントします。実行カウントがゼロに達すると、商の実行をスキャンしています。実行の各スロットの剰余を d _Rと比較できます。見つかった場合は、キーが (おそらく) フィルター内にあると報告し、見つからなかった場合、キーがフィルター内に確実にないと報告します。

たとえば、要素e を検索するとします。図の状態 3 を参照してください。hash (e) を計算し、それを剰余 e _Rと商 e _Q（4）に分割します。スロット 4 から左にスキャンすると、インデックス 4、2、1 の3 つのis_occupiedスロットに遭遇します。これは、 e _Qの実行がクラスター内の 3 番目の実行であることを示しています。スキャンはスロット 1 で停止します。スロット 1 は空ではなくシフトもされていないため、クラスターの開始として検出されます。次に、3 番目の実行まで右にスキャンする必要があります。実行の開始は、is_continuationが false であることによって示されます。最初の実行はインデックス 1 で見つかり、2 番目は 4、3 番目は 5 にあります。インデックス 5 から始まる実行の各スロットに保持されている剰余を比較します。その実行にはスロットが 1 つしかありませんが、例ではその剰余は e _Rに等しく、e が確かにフィルターのメンバーであることを示しています (確率 1 - ε)。

挿入は、キーがフィルターに確実に存在しないことを確認するまで、検索に似たパスをたどります。^[4]その時点で、残りの部分を現在の実行のスロットに挿入します。このスロットは、実行をソートされた順序に保つために選択されます。クラスター内の選択されたスロット以降のスロットの残りの部分を前方にシフトし、スロットのビットを更新します。

• スロットの残りをシフトしても、スロットのis_occupiedビットには影響しません。これは、このビットがスロットに関係するものであり、スロットに含まれる残りには関係しないためです。
• 既存の実行の開始時に剰余を挿入すると、前の剰余がシフトされて継続スロットになるため、is_continuationビットを設定します。
• シフトした余りのis_shiftedビットを設定します。

この図は、要素が追加されるにつれて一連の状態を経て進む商フィルタを示しています。状態 1 では、3 つの要素が追加されています。各要素が占めるスロットは、1 スロット ランを形成し、これもまた個別のクラスターです。

状態 2 では、要素cとd が追加されています。要素cの商は 1 で、bと同じです。 b _R < c _Rと仮定すると、 c _{R は}スロット 2 にシフトされ、継続とシフトの両方としてマークされます。要素dの商は 2 です。その標準スロットは使用中であるため、スロット 3 にシフトされ、シフトとしてマークされます。さらに、その標準スロットは占有としてマークされます。商 1 と 2 の実行は、クラスターを構成します。

状態 3 では、要素aが追加されています。その商は 1 です。a _R < b _Rと仮定すると、スロット 1 から 4 の剰余はシフトされる必要があります。スロット 2 は b _{R を}受け取り、継続としてマークされ、シフトされます。スロット 5 は e _{R を受け取り、}シフト済みとしてマークされます。商 1、2、4 のランはクラスターを構成するようになり、クラスター内にこれら 3 つのランが存在することは、スロット 1、2、4 が占有済みとしてマークされることによって示されます。

ベンダー^[4]は、クラスターは小さいと主張している。これは、検索と挿入ではクラスター全体の開始と長さを見つける必要があるため重要である。ハッシュ関数が均一に分散した指紋を生成する場合、ほとんどのランの長さはO（1）であり、すべてのランの長さがO（log m）である可能性が非常に高い。ここで、 mはテーブル内のスロットの数です。^[4]

Bender ^[4]は、ハッシュテーブルの剰余サイズと負荷係数の観点から、偽陽性（つまり、2つのキーのハッシュが同じ指紋になる場合）の確率を計算します。pビットの指紋は、テーブルサイズm = 2 ^{qスロットを決定する}qビットの商とrビットの剰余に分割されることを思い出してください。負荷係数は 、占有スロットnと合計スロットm : の比率です。したがって、優れたハッシュ関数の場合、はハード衝突の確率にほぼ相当します。 ${\displaystyle \alpha}$${\displaystyle \alpha =n/m}$${\displaystyle 1-e^{-\alpha /2^{r}}\leq 2^{-r}}$

パンディの商フィルタは、目標の偽陽性率が1/64未満の場合、同等のブルームフィルタよりも必要なスペースが少なくなります。^[6]

商フィルタはAMQであり、ブルームフィルタと同じ利点の多くを提供します。Webtable ^[8]などの大規模なデータベースは、それぞれが関連するフィルタを持つ小さなサブテーブルで構成されている場合があります。各クエリはすべてのサブテーブルに同時に分散されます。サブテーブルに要求された要素が含まれていない場合、そのフィルタはI/Oを発生させることなく要求を迅速に完了できます。

商フィルターは、一部のアプリケーションで 2 つの利点を提供します。

1. 2 つの商フィルターは、偽陽性率に影響を与えずに効率的に結合できます。これは Bloom フィルターでは不可能です。
2. いくつかの重複は効率的に許容され、削除できます。

商フィルターが使用するスペースは、ブルーム フィルターのスペースと同程度です。ただし、商フィルターは、元のキーを再挿入しなくても、メモリ内で効率的にマージできます。

これは、ログ構造化マージツリーまたは LSM ツリーを使用する一部のログ構造化ストレージシステムで特に重要です。 ^[9] LSM ツリーは実際にはツリーのコレクションですが、単一のキー値ストアとして扱われます。LSM ツリーの 1 つのバリエーションは、ソート配列マージツリーまたは SAMT です。^[10] このバリエーションでは、SAMT のコンポーネントツリーは Wanna-B ツリーと呼ばれます。各 Wanna- Bツリーには、関連する商フィルターがあります。SAMT へのクエリは、商フィルターによって証明される選択された Wanna- Bツリーのみに向けられます。

ストレージ システムは、通常の操作で SAMT の Wanna- Bツリーを圧縮し、小さい Wanna- Bツリーを大きい Wanna- B ツリーにマージし、それらの商フィルターをマージします。商フィルターの重要な特性は、元のキーを再挿入しなくても効率的にマージできることです。大規模なデータ セットの場合、Wanna- Bツリーがメモリ内にない場合があるため、元のキーを取得するためにそれらにアクセスすると、多くの I/O が発生します。

構造上、商フィルターの値はソートされた順序で保存されます。各実行は特定の商値に関連付けられており、これがフィンガープリントの最重要部分を提供します。実行は順番に保存され、実行内の各スロットはフィンガープリントの最重要部分を提供します。

したがって、左から右に作業することで、すべての指紋を再構築することができ、結果として得られる整数のリストはソートされた順序になります。2つの商フィルターをマージするには、各商フィルターをそのようなリストに変換し、2つのリストをマージして、それを使用して新しい大きな商フィルターを作成するだけです。同様に、指紋は商と余りだけを使用して再計算できるため、キーを再ハッシュせずに商フィルターのサイズを半分または2倍にすることができます。^[4]

• ミンハッシュ
• ブルームフィルタ
• カッコウフィルター

• ウィキメディア・コモンズの商フィルタに関連するメディア