FROST

SPARQL検索エンジン:FROST

バージョン

　 1.1.0

概要

　 FROSTは、RDFデータをメモリ上で高速かつコンパクトに処理するRDFストアです。読み書きの高速なメモリ上でデータ処理するだけでなく、インデックスやクエリ解決の効率化を導入して複雑なクエリでも高速な検索を実現しています。また、圧縮技術を用いることで読み込んだRDFデータの領域を縮小して、簡潔なデータ格納を可能にしています。

　ダウンロード

動作要件

Java 7以上

　以下では、FROSTの性能を評価するために3つの実験を行っています。 1つ目は128GBの大量メモリ環境で、JenaとRDF4Jに比べてFROSTがメモリ上のRDFデータを大幅(12%～17%程度)に圧縮していることを示しています。 JenaとRDF4Jは100GB以上のデータ読み込みでメモリオーバーとなる一方で、FROSTは実装メモリサイズを大きく超える350GB以上のデータ読み込みが可能です。 2つ目はメモリ上の高速なクエリ解決環境において、メモリ使用量の圧縮だけでなく FROSTがJenaとRDF4Jより高速にクエリを解決していることを示しています。 3つ目はオンディスクのRDFデータストアであるVirtuosoと比較してFROSTが高速なクエリ解決時間となっています。 VirtuosoはRDFデータをディスクへ読みますが、 FROSTではデータ圧縮によりディスクを使わずインメモリで実行しています。

性能評価1:インメモリRDFデータストアとの使用メモリ効率比較

実験環境

CPU : Intel(R) Xeon(R) CPU E5-2667 v2 @3.30GHz 3.30GH
実装メモリ : 128.0GB
OS : Windows 8.1 Enterprise 64bit
Version
- FROST : 1.1.0
- Jena : 3.1.1
- Sesame : 2.1.4

データセット

Lehigh University Benchmark(LUBM)を使用
データ生成器を使用して生成したLUBM500(データサイズ:11.9GB)～LUBM16000(データサイズ:358.9GB)までの16個のデータで比較

性能評価2:インメモリRDFデータストアとの解決時間比較

実験環境

CPU : Intel(R) Xeon(R) CPU E5-2667 v2 @3.30GHz 3.30GH
実装メモリ : 128.0GB
OS : Windows 8.1 Enterprise 64bit
Version
- FROST : 1.1.0
- Jena : 3.1.1
- Sesame : 2.1.4

データセット

LUBM1000とRDF Store Benchmarks with DBpedia(BMDB)の2種類で比較

LUBM1000(データサイズ:23.8GB)

BMDB(データサイズ:2.3GB)

性能評価3:オンディスクRDFデータストアとの解決時間比較

実験環境

CPU : Intel(R) Core(TM) CPU i7-3770 @3.40GHz 3.40GH
実装メモリ : 8.0GB
OS : Windows 8.1 Enterprise 64bit
Version
- FROST : 1.1.0
- Virtuoso : 7.2.4

データセット

LUBM300(データサイズ:6.6GB)で比較

実行例

RDFデータ

<http://example.com/Woman> <http://www.w3.org/2000/01/rdf-schema#subClassOf> <http://example.com/Human> .
<http://example.com/Man> <http://www.w3.org/2000/01/rdf-schema#subClassOf> <http://example.com/Human> .
<http://example.com/Alice> <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://example.com/Woman> .
<http://example.com/Alice> <http://example/Properties#name> "Alice" .
<http://example.com/Alice> <http://example/Properties#age> "20" .
<http://example.com/Bob> <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://example.com/Man> .
<http://example.com/Bob> <http://example/Properties#name> "Bob" .
<http://example.com/Bob> <http://example/Properties#knows> <http://example.com/Alice> .
<http://example.com/Bob> <http://example/Properties#age> "21" .

Query1

#Bobの知り合いの女性の名前を調べる
PREFIX ex: <http://example.com/>
PREFIX prop: <http://example/Properties#>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT * WHERE{ex:Bob prop:knows ?x .?x rdf:type ex:Woman .?x prop:name ?y .}

C:FROST>frost --data sample.nt --query query1.rq
---------------------------------------- | x | y | ======================================== | <http://example.com/Alice> | "Alice" | ----------------------------------------

Query2

#Bobから距離2まででつながるリソースを調べる
PREFIX ex: <http://example.com/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT ?o1 ?o2 WHERE{ex:Bob ?p1 ?o1 .?o1 ?p ?o2 .}

C:FROST>frost --data sample.nt --query query2.rq
----------------------------------------------------------- | o1 | o2 | =========================================================== | <http://example.com/Alice> | "Alice" | | <http://example.com/Alice> | <http://example.com/Woman> | | <http://example.com/Man> | <http://example.com/Human> | -----------------------------------------------------------

Query3

#Bobの型を調べる
PREFIX ex: <http://example.com/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT * WHERE{ex:Bob rdf:type ?x .}

C:FROST>frost --data sample.nt --query query3.rq
---------------------------- | x | ============================ | <http://example.com/Man> | ----------------------------

Query3は推論モードで実行するとRDFS推論が行われます。

C:FROST>frost --data sample.nt --query query3.rq -inf
------------------------------ | x | ============================== | <http://example.com/Man> | | <http://example.com/Human> | ------------------------------

Query4

#名前にlを含みかつ年齢が20以上の人間を調べる(推論必須)
PREFIX ex: <http://example.com/>
PREFIX prop: <http://example/Properties#>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT * WHERE{?person rdf:type ex:Human .?person prop:name ?name .
?person prop:age ?age .FILTER(?age >= 20 && REGEX(?name,"l"))}

C:FROST>frost --data sample.nt --query query4.rq -inf
----------------------------------------------- | person | name | age | =============================================== | <http://example.com/Alice> | "Alice" | "20" | -----------------------------------------------

Query5

#人を探し、その人が知っている人を探す
PREFIX ex: <http://example.com/>
PREFIX prop: <http://example/Properties#>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT ?person ?person2 ?property WHERE{?person rdf:type ex:Human .
OPTIONAL{?person2 rdf:type ex:Human .?person prop:knows ?person2 .}}

C:FROST>frost --data sample.nt --query query5.rq -inf
----------------------------------------------------------- | person | person2 | =========================================================== | <http://example.com/Bob> | <http://example.com/Alice> | | <http://example.com/Alice> | | -----------------------------------------------------------

Query6

#AliceかBobに関連するものを探す
PREFIX ex: <http://example.com/>
SELECT ?property ?obj WHERE{{ex:Alice ?property ?obj .}UNION{ex:Bob ?property ?obj .}}

C:FROST>frost --data sample.nt --query query5.rq -inf
---------------------------------------------------------------------------------- | property | obj | ================================================================================== | <http://example/Properties#age> | "20" | | <http://example/Properties#name> | "Alice" | | <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> | <http://example.com/Woman> | | <http://example/Properties#age> | "21" | | <http://example/Properties#knows> | <http://example.com/Alice> | | <http://example/Properties#name> | "Bob" | | <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> | <http://example.com/Man> | ----------------------------------------------------------------------------------

使い方

frost.jarを実行してください。

java -jar frost.jar --data <data_name> --query <query_name> [-options]

<data_name>	nt形式のRDFデータのファイル名
<query_name>	クエリファイルのファイル名

同梱のバッチファイルを使っても起動できます。

frost --data <data_name> --query <query_name> [-options]

実行が終了した後に、次のクエリファイル名を入力(＋ENTER)すると続けて別のクエリ処理を実行できます。
終了する場合は exit と入力してください。

options

-version	バージョンの表示
-help	ヘルプの表示
--result csv	結果形式をcsvに変更(csv出力のほうが高速です)
-inf	RDFとRDFSによる推論を実行
-once	実行終了時に次のクエリファイルの入力を求めない
-comp	より圧縮効率の高いデータ構造に変更
--ld num	データを num 分割にして読み込む

FROSTを実行後、カレントディレクトリ内のフォルダ(temporarydata)にインデックスデータ(データ名_dictionary.txt、データ名_triple.txt)が生成されます。
推論の有無を変更する場合はインデックスデータを削除し、再実行してください。

クエリ

制限されたSPARQLをクエリとして入力することができます。
複数のクエリを1つのファイルに記述できます。
行頭に#をつけると行末までコメントになります。

制限されたSPARQLのEBNF記法

Query	::=	Prologue SelectQuery
Prologue	::=	PrefixDecl*
PrefixDecl	::=	'PREFIX' PNAME_NS IRI_REF
SelectQuery	::=	'SELECT' ( Var+ \| '*' ) WhereClause SolutionModifier
WhereClause	::=	'WHERE'? GroupGraphPattern
SolutionModifier	::=	LimitOffsetClauses?
GroupGraphPattern	::=	'{' TripleBlock? ('.' TripleBlock? )* '}'
TripleBlock	::=	VarOrTerm ' ' VarOrTerm ' ' VarOrTerm

上記にない生成規則に関してはSPARQLの生成規則を参照してください

許諾と免責

本プログラムの著作権は開発者の藤原浩司及び兼岩研究室に帰属します。
国公立研究機関や教育機関による非営利目的の利用に際して許可は必要ありません（但し、民間企業の業務などで使用される場合は兼岩研究室にご相談ください）
本プログラムの使用により、いかなるトラブルが発生しても一切責任を負いませんのでご了承下さい。
研究開発に使用する場合は、論文に参考文献として以下を参照ください。

藤原浩司, 兼岩憲, 「大規模RDFグラフのための効率的なクエリ解決」, 人工知能学会論文誌, Vol. 29, No. 4, pp. 364-374, 2014. [PDF]

藤原浩司, 兼岩憲, 「大規模RDFグラフに対する高速検索とデータ圧縮の両立」, セマンティックWebとオントロジー研究会, SIG-SWO-A1402-08, 2014. [PDF]

香川俊幸, 兼岩憲, 「FROSTにおけるデータストアの圧縮と読み込み手法」, セマンティックWebとオントロジー研究会, SIG-SWO-040-06, 2016. [PDF]