文献

J-GLOBAL ID：201802263036344902   整理番号：18A0728633

ハッシュテーブルより良い機能的Bloomフィルタ【JST・京大機械翻訳】

Functional bloom filter, better than hash tables

著者 (2件)： Byun Hayoung (Ewha Womans University) ,  Lim Hyesook (Ewha Womans University)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2018  号： ICEIC  ページ： 1-3  発行年： 2018年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ハッシュテーブルは多くのアプリケーションで広く使われており,各入力キーに対応する値を返す必要がある。しかし,ハッシュベースのデータ構造には,衝突の固有の問題があり,そこでは,異なる鍵にはハッシュテーブルの同じインデックスがある。ハッシュテーブルの荷重係数が増加すると,衝突の数は増加する。衝突のために貯蔵できない要素は,戻る値の失敗を引き起こす。マルチハッシング,cuckoハッシング,およびd-左ハッシングのような変種構造を研究したが,構造のどれも完全に衝突問題を解決しなかった。本論文では,機能的なBloomフィルタがハッシュテーブルを置き換えることができると主張する。ハッシュテーブルはリターン値に加えて各入力キー自身または各入力キーの署名を保存する必要があるが,機能的なBloomフィルタは,各入力キーの署名として,Bloomフィルタ指標の異なる組合せが働くことができるので,リターン値のみを保存できる。性能評価結果により,機能的Bloomフィルタは,固定サイズメモリに多くの要素を保存し,従って,より少ない故障を生成することにおいて,ハッシュベースのデータ構造よりも効率的であることを示した。Copyright 2018 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【JST・京大機械翻訳】

シソーラス用語： *ハッシング ,  データ構造 ,  性能評価 ,  応用プログラム
準シソーラス用語： *Bloomフィルタ ,  *ハッシュテーブル , 【Automatic Indexing@JST】

分類 (5件)： フィルタ一般  (NC04021I) ,  電話・データ通信・交換一般  (ND11010T) ,  記憶方式  (JC02040V) ,  システムプログラミング一般  (JD03010Y) ,  検索技術  (AC06020S)

タイトルに関連する用語 (2件)： ハッシュテーブル ,  Bloomフィルタ