"あなたはどのように接続されていますか"のようなLinkedInを効率的に実装するには？

Question

LinkedInには、ネットワーク経由でそのユーザに接続する方法を入力するプロンプトが表示される、このクールな機能があります。

ノードがユーザーを表し、エッジが友情を表すグラフの2つのノードであると仮定すると、単純な解決策は、両方のノードから特定のレベルまでbfsであり、交差点。交差点はネットワークリンクノードになります。

これはきちんと聞こえますが、問題は各人の友人を判断するために、別のDBクエリが必要であるということです。ネットワークが2レベルよりも深くなると、非常に時間がかかるアルゴリズムになります。より効率的な選択肢がありますか？そうでない場合は、計算に必要な時間を短縮するために、ハードウェアサポート（並列コンピューティング、グリッド、分散データベースなど）を追加するにはどうすればよいでしょうか？

Answer 1

これは、Lorenzo Albertonの記事Graphs in the database: SQL meets social networksで確認できます。サンプルコードは、CTEを使用してPostgreSQL用に書かれています。しかし、私はこのためにRDBMSを使うとうまくいくのではないかと疑います。私は、ネイティブグラフデータベースを使用して、上記の記事と同じものを実行する方法についての記事を書いています。この場合はNeo4j：​​です。パフォーマンスの違いとは別に、グラフ・データベースは、SQLで（またはストアード・プロシージャーを使用して）非常に複雑なトラバーサルを容易に処理できるグラフAPIを提供することで、タスクを簡素化します。私はthis threadにグラフデータベースをもう少し書いて、this oneも参照してください。

Answer 2

何らかの種類の再帰ストアドプロシージャ（SQL Server 2005以降のCTE）がないと、レベルが深くなるにつれ、複数のラウンドトリップが必要になります。ただし、最も一般的な/アクティブなユーザーの接続リストがキャッシュされたままになるため、優れたキャッシュインフラストラクチャによってパフォーマンスが向上します。キャッシュ機構を介した読み取り/書き込みにより、より良いものになります（キャッシュ更新はデータベースの更新にカスケードします）。