分散 RDF 問合せ処理時の転送量減少のためのブルームフィルタの拡張

IPSJ Web Site

Bibliographic Information

Other Title
  • ブンサン RDF トイアワセ ショリジ ノ テンソウリョウ ゲンショウ ノ タメ ノ ブルームフィルタ ノ カクチョウ
  • Distributed RDF Query Processing Based on an Extension of Bloom Filters

Search this article

Abstract

本稿では，分散環境における RDF 問合せ処理の効率化を目指し，ブルームフィルタを拡張して転送量を減少させる手法を提案する．RDF はメタデータ記述のための枠組みで，近年様々な応用分野に広く利用されており，各地でボトムアップに作成・管理されている．それらの分散した RDF データに対して，横断的・包括的な問合せを行いたいという要求が高まっている．これまで，分散 RDF データ検索に関する研究はいくつか提案されているが，それらの多くは，トップダウンに配置した RDF データに対する処理手法やトリプルパターンマッチングのような単純な検索に関する研究が主であった．我々が提案する手法のような，ボトムアップに作成された RDF データに対して，結合や和集合などの演算を含む高度な問合せ処理の効率化を目指した研究は，これまでほとんど行われていない．提案手法では RDF トリプルに対応した 3 次元のブルームフィルタを用い，問合せ処理時にブルームフィルタ間でビット演算を行うことで，リモート RDF データへアクセスする前に，そのデータが解に含まれているかどうかを判断することができるため，データ転送量を削減でき，処理時間の減少につながる．我々は，RDF 問合せ言語 SPARQL を処理するプロトタイプシステムを作成し，分散環境における RDF データ問合せ処理の効率が向上することを実験によって確認した．

In this paper, we propose an indexing scheme for distributed RDF query processing using the Bloom filters. RDF is a framework for describing metadata and, today, it is widely used in various fields. Generally, RDF data are created in a bottom-up manner, that is they are created by different people and stored in different locations. Therefore, RDF query processing for the distributed RDF data becomes an important issue. So far, several distibuted search approaches for RDF data have already been proposed. These approaches, however, were specially designed for RDF data in a top-down fashion, or for simple search using triple pattern matching. To the best of our knowledge, there are no studies for efficient distributed RDF query processing that includes binary operations such as join and union. In this paper, we propose an approach that uses an extended Bloom filter fitting for the RDF model. By using the filter combined with bit operations, we are able to know whether a particular data is included in the result set before actually accessing remote RDF data source. This can significantly reduce transfer volume among distributed RDF data sources, and thus the query processing time decreases. We have implemented the proposed approach and performed a performance evaluation. Our evaluation shows that the proposed approach can significantly improve query processing performance in a distributed environment.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top