BFマージ結合：Bloomフィルタを保持するB+木を用いた低結合選択率に適した結合手法

• Item type: Trans(1)
• 公開日: 2011-07-01
• タイトル: BFマージ結合：Bloomフィルタを保持するB+木を用いた低結合選択率に適した結合手法
• タイトル / 言語: en
• タイトル: BF Merge Join: A Merge Join for Low Selectivity Using Extended B+ Trees with Bloom Filters
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 産業技術総合研究所
• 著者所属: 産業技術総合研究所
• 著者所属: 産業技術総合研究所
• 著者所属: 産業技術総合研究所
• 著者所属(英): en
• 著者所属(英): National Institute of Advanced Industrial Science and Technology (AIST)
• 著者所属(英): en
• 著者所属(英): National Institute of Advanced Industrial Science and Technology (AIST)
• 著者所属(英): en
• 著者所属(英): National Institute of Advanced Industrial Science and Technology (AIST)
• 著者所属(英): en
• 著者所属(英): National Institute of Advanced Industrial Science and Technology (AIST)
• 著者名: 的野, 晃整; スティーブン, リンデン; 谷村, 勇輔; 小島, 功
• 著者名(英): Akiyoshi, Matono; Steven, Lynden; Yusuke, Tanimura; Isao, Kojima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，結合不能タプルを読み飛ばしできるマージ結合アルゴリズム（BFマージ結合）と，それに用いる，各ノードにBloomフィルタを付与するよう拡張したB+木（BB+木）を提案する．BFマージ結合は，2つのBB+木の各ノードにおいて，子孫ノードの読み飛ばしのために，子孫集合が互いに素であるかどうかの判定を行う．この判定は，的野ら（2010）が提案した素集合判定可能なBloomフィルタを用いる．BB+木の機能として，Bloomフィルタを遅延更新可能なレコードの追加と削除に加え，木全体を高速にメンテナンスする操作も提案する．実験を通して，BB+木およびBFマージ結合の性能を評価した結果，BFマージ結合は選択率が低い等結合処理時に非常に効率的であることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a novel merge join algorithm, called BF merge join, that can skip dangling tuples using extended B+ trees, which we call BB+ trees, each node of which has Bloom filters to represent its descendant keys. BF merge join traverses BB+ trees, comparing nodes to check whether the nodes' descendants are disjoint ot not. This disjoint test uses Bloom filters that we have extended to be able to check whether they are disjoint. The proposed BB+ tree supports lazy scalable insertion and deletion. Furthermore, we propose a memtenance operation to updete entire tree. We evaluated the performance of our BB+ tree and BF merge join. The results show that a BF merge join can give performance improvements, especially in the case of low-selectivity equi-join queries.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 4, 号 2, p. 114-125, 発行日 2011-07-01
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会