| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | IT |
| 開催期間 | 2013-09-27 - 2013-09-27 |
| 開催地（和） | 沖縄・カルチャーリゾート フェストーネ |
| 開催地（英） | Culture Resort Festone (Okinawa) |
| テーマ（和） | 誤り訂正符号，一般（「誤り訂正符号のワークショップ」(9/25-9/27)と併催） |
| テーマ（英） | error correcting codes, general |
| 講演論文情報の詳細 | |
| 申込み研究会 | IT |
| 会議コード | 2013-09-IT |
| 本文の言語 | 日本語 |
| タイトル（和） | 消失誤りを伴うInvertible Bloom Lookup Tablesの性能評価 |
| サブタイトル（和） | |
| タイトル（英） | Performance Analysis on Invertible Bloom Lookup Tables with Erasure Errors |
| サブタイトル（英） | |
| キーワード(1)（和/英） | データ構造 / data structure |
| キーワード(2)（和/英） | ハッシュ関数 / hash function |
| キーワード(3)（和/英） | 停止集合 / stopping set |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 湯川 大地 / Daichi Yugawa / ユガワ ダイチ |
| 第1著者 所属（和/英） | 名古屋工業大学 (略称： 名工大) Nagoya Institute of Technology (略称： Nagoya Inst. of Tech.) |
| 第2著者 氏名（和/英/ヨミ） | 和田山 正 / Tadashi Wadayama / ワダヤマ タダシ |
| 第2著者 所属（和/英） | 名古屋工業大学 (略称： 名工大) Nagoya Institute of Technology (略称： Nagoya Inst. of Tech.) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-09-27 10:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IT |
| 資料番号 | IT2013-35 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.228 |
| ページ範囲 | pp.19-24 |
| ページ数 | 6 |
| 発行日 | 2013-09-20 (IT) |
[研究会発表申込システムのトップページに戻る]