講演抄録/キーワード |
講演名 |
2013-09-27 10:55
消失誤りを伴うInvertible Bloom Lookup Tablesの性能評価 ○湯川大地・和田山 正(名工大) IT2013-35 |
抄録 |
(和) |
Invertible Bloom Lookup Tables (IBLT)はkey-valueペアの挿入,削除,検索,リストアップ操作をサポートしたデータ構造である.IBLTの一番の特徴は,すべてのkey-valueペアをリストアップする操作が可能な点であり,この操作を用いた集合一致(set reconciliation)の応用例等が提案されている.ハードディスクやメモリ等の記録装置では,メディアの欠陥やエラーによりデータの一部が消失する可能性がある.IBLTをこのような信頼性の低い環境化で利用する場合には,IBLTの消失誤りに対する耐性を定量的に評価することが求められている.本稿では,IBLTに消失誤りが発生するモデルを仮定し,リストアップ操作の失敗確率の評価を行う解析手法を提案する.本稿で提案する解析手法は,IBLTのリストアップ操作とLDPC符号のピーリングアルゴリズムの類似性に基づいている.ユニオンバウンドに基づいて導出したリストアップ失敗確率の上界は,正確にリストアップ失敗率のエラーフロアの振る舞いを捉えていることが計算機実験により確認された. |
(英) |
The Invertible Bloom Lookup Tables (IBLT) is a data structure which supports insertion, deletion, retrieval and listing operations of the key-value pair. The most notable feature of the IBLT is the complete listing operation of the key-value pairs and there are applications such as set reconciliation based on the listing operation. In some cases, data stored in a recording device such as a hard disk drive or memories can be lost due to defects of the media or errors. In such an environment, it is crucial to know the error tolerance of the IBLT. In this paper, we assume an erasure channel model for the IBLT. We will present an analysis for the IBLT which reveals behaviors of the listing failure probability, which represents robustness ofthe IBLT. The analysis is based on the similarity between listing operation of IBLT and peeling algorithm of low-density parity check (LDPC) codes.Some computer experiments indicate that an upper bound on the listing failure probability based on the union bound accurately captures the error floor behaviors. |
キーワード |
(和) |
データ構造 / ハッシュ関数 / 停止集合 / / / / / |
(英) |
data structure / hash function / stopping set / / / / / |
文献情報 |
信学技報, vol. 113, no. 228, IT2013-35, pp. 19-24, 2013年9月. |
資料番号 |
IT2013-35 |
発行日 |
2013-09-20 (IT) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2013-35 |