インメモリ型高速SPARQLエンジン:FROST

応募者の情報
ご氏名 藤原浩司,兼岩 憲(代表)
ご所属 電気通信大学
e-mailアドレス [非公開]
応募する基盤技術の情報
基盤技術の名称 インメモリ型高速SPARQLエンジン:FROST
基盤技術のURL http://www.sw.cei.uec.ac.jp/frost/index-j.html
基盤技術の概略説明 SPARQLクエリの検索エンジンを備えた本格的なインメモリ型RDFデータストアです.特に,データインデックス化とクエリ解決手順の効率化による高速検索と,高い圧縮率で簡潔なRDFデータ格納を両立します.
基盤技術の詳細説明 FROSTはユーザーやソフトウェアがSPARQLクエリを発行して,RDFで記述された大量のメタデータやオントロジーデータから高速にクエリ結果を出力します.インメモリ型のRDFデータストアに加え,クエリ解決を主要なSPARQLクエリ文(SELECT文)に制限することにより,高速検索に特化したエッジのきいたSPARQLエンジンを実現しています.安価になったメモリを大量に積んだPCを用意すれば,100GBを超えたRDFデータも超高速で検索できます.これは機能を特化して高速化のために一部機能を犠牲にするようなNoSQLの考えに基づいています.従って,クエリの条件指定でFILTER, OPTIONAL, UNIONは許しますが,データ結果をソートするORDER BYやDISTINCTなどは使用できません(これら無しでも,多くの標準クエリ文は十分に実行できます).

【背景と問題点】
Linked Dataなどの大規模なRDFデータが多くの分野で作成されており,それらのデータストアからメタデータを検索するためにはクエリ言語SPARQLが重要な役割をもちます.RDFデータはグラフ構造とRDF語彙の意味構造を含んだ大規模で複雑なデータであり,それらから高速に検索するエンジンはLinked Dataの有効活用に不可決です.
しかしながら,実用に耐えうるRDFデータストアとSPARQLクエリの検索エンジンを開発するには,以下のボトルネックが存在します.
・メモリより格段に遅いハードディスクによるデータストアのアクセス処理速度
・データベースの高速検索に有用なインデックスがもたらすデータ量の倍増化
・高速化を目指すとインデックスデータが増えるため,一般的に高速検索とデータ圧縮は相反し両立が困難

【特徴/優位性】
(1)クエリ順序書き換えによる解決の効率化:クエリの結果を変えずに探索の組み合わせが小さくなるようなクエリ実行計画を生成し,RDFデータへの高速な問い合わせ方法を実現します.
(2)RDFデータのインデックス化による検索の高速化:RDFデータのリソースをID化,RDFトリプルを構造化してIDからインデックス検索すれば,特定のリソースを起点にしたトリプルの情報を定数オーダーO(1)で取得できます.
(3)RDFデータ圧縮によるメモリ使用量の削減:2つのインデックスだけですべてのトリプルパターンの解決が可能なリレーインデックスを提案し,既存の圧縮手法と組み合わせて省メモリかつ高速検索を実現します.

【性能評価の結果】
RDFデータとクエリ処理に関するベンチマークLUBM(Lehigh University Benchmark)とBMDB(RDF Store Benchmarks with DBpedia)が提供する2つのデータセットを用いて,処理速度とメモリ使用量でFROSTが優れている実験結果を得ました.この実験では, 次のようにJena,Sesame,Virtuosoなどの広く使われているSPARQLエンジンと性能比較を行っています.

メモリ使用量の大幅削減:インメモリで使用したJena やSesame よりも非常に少ないメモリでデータを格納できます.元のデータサイズと比較すると15~25% 程度でデータを格納することができ,実装メモリ128GBよりも大きなデータサイズ(160GB以上)のLUBM7000も圧縮して読み込めます.

圧縮データのもとでのクエリ解決の高速化:LUBMベンチマークの10クエリを用いると,Jena にはすべてのクエリ,Sesame には7クエリにおいてFROSTの解決時間が短くなります(残りの3クエリはほぼ同じ解決時間).DBpediaを用いたBMDBベンチマークの5クエリでは,Jenaには3クエリ,Sesameには2クエリでFROSTの方が解決時間が短くなり,FILTER付きの2クエリでは少し遅い解決時間となります.また,その他にオンディスクのVirtuosoと比較したとき,LUBMベンチマークの10クエリにおいてFROSTの方が6クエリで解決時間が短くVirtuosoの方が4クエリで解決時間が短く,全クエリの結果を通して見たときFROSTの方がやや優勢の性能結果を得ています.

以上の比較実験により,FROSTが高速検索を可能にしながらRDFデータ読込後のメモリ使用量を大幅に削減することを示しています.
アプリケーションの権利指定
全ての権利の主張
作品の著作権は応募者に帰属し、いかなる修正、変更、利用も応募者の許可なくしてはできない。
アイコン icon
関連する作品の情報
関連するデータセット
関連するアイデア
関連するアプリケーション
関連するビジュアライゼーション作品
関連する基盤技術作品

登録情報の修正について

修正の希望がある場合には実行委員会までご連絡下さい。lod-challenge[at]sfc.keio.ac.jp *メールアドレスの[at]を@としてお送り下さい。