消失誤りを伴うInvertible Bloom Lookup Tablesの性能評価

摘要

Invertible Bloom Lookup Tables（IBLT）はkey-valueペアの挿入，削除，検索，リストアップ操作をサポートしたデータ構造である．IBLTの一番の特徴は，すべてのkey-valueペアをリストアップする操作が可能な点であり，この操作を用いた集合一致（set reconciliation）の応用例等が提案されている．ハードディスクやメモリ等の記録装置では，メディアの欠陥やエラーによりデータの一部が消失する可能性がある．IBLTをこのような信頼性の低い環境化で利用する場合には，IBLTの消失誤りに対する耐性を定量的に評価することが求められている．本稿では，IBLTに消失誤りが発生するモデルを仮定し，リストアップ操作の失敗確率の評価を行う解析手法を提案する．本稿で提案する解析手法は，IBLTのリストアップ操作とLDPC符号のピーリングアルゴリズムの類似性に基づいている．ユニオンバウンドに基づいて導出したリストアップ失敗確率の上界は，正確にリストアップ失敗率のエラーフロアの振る舞いを捉えていることが計算機実験により確認された．