"CuckooFilter" (データ構造)

"CuckooFilter"

要素が確実にメンバではないかどうかを検定する集合を表す．

詳細

  • Cuckooフィルタは通常，要素が確実にメンバでないかどうかを検証することができる確率集合として使われる．
  • 要素はCuckooフィルタから除去することができる．
  • 同じ要素を複数回Cuckooフィルタに挿入することができる．
  • ある要素がCuckooフィルタのメンバであるかどうかを検証すると，要素が集合のメンバではない場合に必ずFalseを返す．
  • ある要素がCuckooフィルタのメンバであるかどうかを検証すると，要素が集合のメンバである場合に必ずTrueを返すとは限らない．
  • 要素を入れるスペースがない場合には，Cuckooフィルタへの挿入に失敗することがある．
  • CreateDataStructure[ "CuckooFilter",capacity]指定の capacity を持つ新しい"CuckooFilter"を作成する
    Typed[x,"CuckooFilter"]x に"CuckooFilter"の型を与える
  • "CuckooFilter"型のデータ構造には，以下の演算が使える．
  • ds["Array"]ds 内の基本となるデータtime: O(1)
    ds["Capacity"]ds の記憶容量time: O(1)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["CouldContain",x]ds に x が含まれる可能性がある場合にはTrue，それ以外の場合にはFalseを返すtime: O(1)
    ds["Delete",x]x を ds から削除し，x が要素だったかもしれない場合にはTrueを返すtime: O(1)
    ds["FalsePositiveProbability"]メンバシップ検定で誤検出される確率time: O(1)
    ds["Insert",x]x を ds に挿入するtime: O(1)
    ds["Length"]ds に保存される要素の数time: O(1)
    ds["LoadFactor"]ds のロード係数time: O(1)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する

例題

すべて開くすべて閉じる

例  (1)

新しい"CuckooFilter"は，CreateDataStructureを使って作成できる：

任意の式を"CuckooFilter"のデータ構造に挿入することができる：

式が存在するかどうかを検証することは可能である．結果がFalseである場合には，f[2]が確実にその集合内にないことを意味する：

結果がTrueである場合には，f[1]がその集合内に存在する可能性があることを意味する：

要素は集合から削除できる：

これで要素は確実に集合内にない：

要素を集合に挿入する：

式バージョンの ds を返す：

データ構造の可視化を生成することができる：

スコープ  (1)

情報  (1)

新しい"CuckooFilter"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：

考えられる問題  (1)

十分なスペースがない場合には，Cuckooフィルタへの挿入に失敗することがある．

Cuckooフィルタを作成し，いくつかの要素を挿入する．可視化するとその分布を見ることができる：

ロード係数を使うと，どのくらいのスペースがあるかを知ることができる：

同じハッシュ特性を持つ要素をもう一つ入れるスペースはないので，挿入に失敗する：

削除を行うと，挿入が可能になる：