4

友人id, u1, u2とのテーブルと< 500,000、単一の mysql サーバー上のエントリについてのテーブルがあります

そして、彼らに共通の友達がいるかどうかを確認したいと思いuserAます。userB

したほうが早いか

select u2 from friends where u1 = userA and u2 IN (select u2 from friends where u1 = userB)

グラフ上で (1 つのサーバー上で) 最短経路アルゴリズムを実行するよりも?

LinkedIn や Facebook などの大規模なネットワークがこれを処理するために使用する標準的な方法は何ですか?

ありがとう！

4

5 に答える 5

2

テーブル friends が u1 と u2 の両方でインデックス付けされている場合、SQL クエリは 2 つのサブセットの共通部分を取ることになり、かなり高速になります。これは、索引付けがすでに行われているためです。メモリ内で計算を行う場合、時間は事前に作成されたインデックスがあるかどうかによって異なります。ある場合は、データベース接続のオーバーヘッドがないため、高速になります。インデックス作成が計算時間に含まれていて、データベースがウォームアップされている場合 (メモリ内のすべてのデータ)、失われる可能性があります。

最短経路アルゴリズムは必要以上のデータを計算するため、最短経路アルゴリズムではなく、インデックス作成について話しています。

于 2012-09-15T19:19:20.207 に答える
2

MySQL では、作成したクエリは、この情報を見つける他のどの方法よりも遅くなります。一人一人に尋ねるよりも遅いかもしれません。クエリ:

select u2
from friends
where u1 = userA and
      u2 IN (select u2 from friends where u1 = userB)

IN 句にサブクエリがあります。MySQL は、検出されたすべての行のクエリを評価します。これを書くより良い方法は次のとおりです。

select u2
from friends
where u1 = userA and
      exists (select 1 from friends where u1 = userB limit 1)

データがすべて 1 つのサーバーに収まり、メモリに収まる場合、最適化された MySQL クエリのパフォーマンスは問題ないはずです。LinkedIn や FaceBook などのサイトは、ネットワークの絶え間ない更新、大量のデータ、さまざまな種類のリンクなど、無数の問題に対処しています。あなたの単純な例は、彼らがしていることを代表するものではありません。しかし、彼らの分析の多くは、Hadoop または Hadoop をリレーショナル データベースと組み合わせて使用​​しています。

于 2012-09-15T19:23:33.310 に答える
2

グラフ データベースでは、 gremlinでクエリを次のように記述できます。

g.V('username','userB').out('friend').retain(g.V('username','userA').out('friend').gather)

ほとんどのグラフ データベースは、これをすばやく実行する必要があります。

Titan を使用すると、Titan が隣接する頂点を並べ替え順に維持することをさらに活用できます。つまり、データに対して 1 回の反復のみを使用して、追加のデータ構造を作成することなく、2 つのフレンド リストの交差を計算できます。これはおそらく MySQL よりも高速であり、友人の平均数が多い場合ははるかに高速です。

于 2012-11-19T23:32:04.837 に答える
0

単純なものを使用した2次接続の別の見方を次に示しますinner join。

select fA.u2 
from friends fA 
inner join friends fB on
           fA.u2 = fB.u2 
where fA.u1 = userA and
      fB.u1 = userB

これは、多対多タイプのクエリと同じアプローチです。そのレベルの関係に最短経路を使用する必要はありません。

より大きな程度の関係を探したい場合は、隣接リストを調べる必要がありますが、MySQLを使用してそれを実装するのは簡単ではありません。そのセットアップで実際に注意しなければならないいくつかの問題があります：

  • グラフの非交和（サブグラフの推移閉包を維持することで処理でき、必要に応じてそれらをマージできます）、
  • 有向グラフと無向グラフ、
  • データ分散（処理を高速化する方法としてhadoopについて言及した別の回答ですが、適切なパーティションスキームが必要です）

いくつか例を挙げると。

于 2012-11-19T16:43:14.667 に答える
0

実際にこれを試して、自分のデータと比較する必要があります。cassovary、flockdb、 neo4j などを調べてください

エントリがそれほど多くないので、個人的にはインメモリで行います。たとえば、高速なビット操作 (AND) を使用できる BitSet を試してみてください。

于 2012-09-15T19:18:53.827 に答える