database - 大規模な DAG でのトポロジカル ソートの例

Question

大きなグラフサイズでトポロジカル ソートが実行される実際のアプリケーションを探しています。

そのような事例を見つけることができると私が想像するいくつかの分野は、バイオインフォマティクス、依存関係の解決、データベース、ハードウェア設計、データ ウェアハウジングなどでしょう。トップソート。

データ/プロジェクトが公開されていない場合でも、ヒント (および潜在的なグラフ サイズの大きさの見積もり) が役立つ場合があります。

Answer 1

これまでに見たトポロジカル ソートの例をいくつか示します。

• 分散システムでタスク グラフをスケジュールするときは、通常、タスクをトポロジ的に並べ替えてからリソースに割り当てる必要があります。100,000 を超えるタスクを含むタスク グラフをトポロジー順にソートする必要があることを認識しています。このコンテキストでこれを参照してください。

• むかしむかし、私はドキュメント管理システムに取り組んでいました。このシステム上の各ドキュメントには、コンテンツ タイプやフィールド参照など、他の一連のドキュメントに対する優先順位の制約があります。次に、システムは保存されたトポロジー順序でドキュメントの順序を生成できる必要があります。私が覚えているように、2 年前には約 5,000,000 のドキュメントが利用可能でした!!!

• ソーシャルネットワーキングの分野では、ネットワーク内の最大の友情距離を知るための有名なクエリがあります。この問題は、BFS アプローチによってグラフをトラバースする必要があり、これはトポロジカル ソートのコストと同じです。Facebook のメンバーを考えて、答えを見つけてください。

さらに実際の例が必要な場合は、遠慮なく私に尋ねてください。私は、大きなグラフを扱う多くのプロジェクトに携わってきました。

PS 大規模な DAG データセットについては、Stanford Large Network Dataset Collection and Graphics@ Illinoisページをご覧ください。

Answer 2

これがあなたの探しているものに合っているかどうかはわかりませんが、Bio4jプロジェクトを知っていましたか?

グラフ ベースの DB に保存されているすべてのコンテンツがトポロジカル ソートに適しているわけではありませんが (グラフの重要な部分に有向サイクルが存在します)、遺伝子オントロジーやタクソノミーなどのサブグラフでは、この順序付けが意味を持つ場合があります。

Answer 3

私が働いている会社は、ソフトウェアの脆弱性とパッチの (独自の) データベースを管理しています。パッチは通常、ソフトウェア ベンダー (Microsoft、Adobe など) によって定期的に発行されます。ホストに新しいパッチを適用すると古いパッチが適用されるという意味で、「新しく改良された」パッチが古いパッチよりも優先されます。パッチは不要になりました。

これにより、各ソフトウェア パッチが各「置き換え」パッチのノードを指すアークを持つノードである DAG が発生します。現在、グラフには 10,000 近くのノードがあり、毎週新しいパッチが追加されています。

このコンテキストでは、グラフにサイクルが含まれていないことを確認するためにトポロジカル ソートが役立ちます。サイクルが発生した場合は、新しい DB レコードの追加でエラーが発生したか、DB インスタンス間のデータ レプリケーションの失敗によって破損が発生したことを意味します。

Answer 4

TopoRは商用のトポロジー PCB ルーターであり、最初に PCB をトポロジー問題としてルーティングし、次にトポロジーを物理空間に変換します。それらは最大 32 の電気層をサポートするため、何千もの接続 (たとえば 10^4) に対応できるはずです。

集積回路も同様の方法を使用する可能性があると思います。