1

問題の説明

巨大なグラフ データベースにリンク分析アルゴリズムを実装しています。

グラフ データベースは、エンティティ (頂点) と関係 (エッジ) で構成されます。

各エンティティ タイプにはプロパティがあります。たとえば、Person : [年齢、身長、体重]。

各関係にもプロパティがあります。たとえば、Call(Phone,Phone) : [date, duration]または Own(Person, Phone) : [start-date, end-date] などです。

今、私は次の構造を持つパターンを与えられています:

[エンティティ タイプ,制約] [関係タイプ,制約] [エンティティ タイプ,制約] [関係タイプ,制約] ... [エンティティ タイプ,制約]

例えば：

[person,age>20] [own, start-date>1/1/2010] [phone, end with '5'] [call date>1/1/2010] [phone, starts with '6'] [ownedまでに、開始日<1/2/2011] [人物、身長>40]。

パターン内のすべてのエンティティと関係に対して、すべての有効な割り当てを見つける必要があります。

次のプリミティブを使用して、データベースにクエリを実行できます。

  • 与えられた一連の制約について、最初の 1000 個の[entity-type,relationship-type,entity-type]割り当てを見つけます。
  • 上記の次の 1000 を見つける
  • 与えられた一連の制約について、最初の[concrete-entity,relationship-type,entity-type]割り当てを見つけます。
  • 上記の次の 1000 を見つける

特定のクエリに対するすべての回答を RAM に保持することは不可能です。各エンティティー - 関係 - エンティティーのトリプルには、何百万 (何十億?) の割り当てが存在する可能性があります。ただし、パターン全体の割り当て数は少ないものとします。

私が試したこと：

チェーンET1-RT1-ET2-RT2-ET3-RT3 の場合... 単純な実装は次のようになります。

Get first 1000 (ET1-RT1-ET2)   
for each concrete ET2:
    Get first 1000 (ET2-RT2-ET3)
        for each concrete ET3:
            ...

問題は、同じサブ問題を複数回解決している可能性があることです。

このような冗長性を排除し、メモリ効率の良いアルゴリズムを探しています。

ノート：

アルゴリズムを探しています。「SQL JOINを使用する」/「SPARQLを使用する」などの回答ではありません...

4

1 に答える 1

0

ここでは動的計画法が役立つはずです。

ここでは、ルールを R1-R2-R3...Rk のように単純化します。

next_nodes(node x, Rule R) が、ルール R に準拠する x にリンクされたすべてのノードを返すようにします。R がエンティティ制約の場合: 条件が満たされた場合は同じノードのシングルトン セットを返し、そうでない場合は空のセットを返します。関係制約の場合、条件を満たすすべてのリンクされたノードを返します。

Initialize cur_set to all set of nodes.

nextset = {}

For each rule R in Ri:
    for each node x in cur_set:
        nextset = nextset U next_nodes(x)
    cur_set = nextset

セットをハッシュテーブルまたはツリー (任意の log(n) 検索および更新時のデータ構造) として保存できる必要があります。

トラバースのパスを保持する部分は省略していますが、かなり簡単に実行できるはずです。セット内の各要素に対して、'path' という属性を追加し、反復ごとに現在のノードを追加します。複数のパスが同じ中間/最終ノードにつながる可能性があることに注意してください。

于 2012-02-02T22:46:22.843 に答える