LinkedInには、あるユーザーのプロファイルにアクセスしているときに、ネットワークを介してそのユーザーに接続する方法を尋ねるこの優れた機能があります。
訪問者とプロファイル所有者がグラフの2つのノードであり、ノードがユーザーを表し、エッジが友情を表すと仮定すると、単純な解決策は、両方のノードから特定のレベルまでのbfsで、交差点があるかどうかを確認することです。交差点はネットワークリンクノードになります。
これはきちんと聞こえますが、問題は、各人の友達を特定するために、個別のDBクエリが必要になることです。ネットワークが2レベルより深くなると、非常に時間のかかるアルゴリズムになります。より効率的な代替手段はありますか？そうでない場合、計算に必要な時間を短縮するために、より良いハードウェアサポート（並列コンピューティング、グリッド、分散データベースなど）を追加するにはどうすればよいですか？
これがどのように行われるかは、データベースのグラフ：SQLとLorenzoAlbertonによるソーシャルネットワークの出会いの記事で確認できます。サンプルコードは、CTEを使用してPostgreSQL用に記述されています。ただし、これにRDBMSを使用してもうまくいくとは思えません。ネイティブグラフデータベースを使用して、前述の記事と同じことを行う方法についての記事を書きました。この場合、Neo4j：データベース内のソーシャルネットワーク：グラフデータベースを使用します。パフォーマンスの違い以外に、グラフデータベースは、SQLでの記述が非常に複雑になる（またはストアドプロシージャを使用する）トラバーサルを簡単に処理できるグラフAPIを提供することにより、タスクを簡素化します。このスレッドのグラフデータベースについてもう少し書きました。これも。
ある種の再帰ストアド プロシージャ (SQL Server 2005 以降の CTE) がなければ、レベルが深くなるにつれて複数のラウンド トリップが必要になります。ただし、優れたキャッシュ インフラストラクチャは、最も人気のある/アクティブなユーザーの接続リストがキャッシュされたままになるため、パフォーマンスを大幅に向上させる可能性があります。キャッシュ メカニズムを介した読み取り/書き込みにより、状況はさらに改善されます (キャッシュ更新は db 更新にカスケードされ、キャッシュ読み取りは db 読み取りにカスケードされます)。