Proposal: Implement Distributed Balanced Partitioning via Linear Embedding (DBP-LE)
メンテナーはふだん 1 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 25/100
- issue の種類
- 機能追加
- 明瞭さ
- おおむね明確
- 活発さ
- 停滞
- 技術スタック
- java
調査の方向性
まず JanusGraph のバックエンドパーティショナと引用されている DBP-LE の論文を確認し、次に提案を既存のハッシュ、範囲、外部パーティショニングのアプローチと比較します。DBP-LE が提案された設定でオプションの戦略として統合され、エッジカットを削減したバランスの取れたパーティションを生成できれば、作業は完了です。
索引モデルが issue の本文から書いたものです。
説明
Describe the feature:
This proposal suggests implementing the Distributed Balanced Partitioning via Linear Embedding (DBP-LE) algorithm — originally developed by Aydin, Bateni & Mirrokni (Google Research, WSDM 2016) — as an optional graph partitioning strategy in JanusGraph.
DBP-LE addresses the challenge of balanced partitioning in large distributed graphs by:
- Embedding vertices into a one-dimensional linear order using affinity (common-neighbor similarity).
- Performing local refinements via Minimum Linear Arrangement (MinLA) and RankSwap.
- Applying imbalance-aware postprocessing (sliding-window min-cut / DP optimization).
The output is a vertex ordering and balanced partition boundaries that minimize edge cuts between partitions.
This algorithm is highly scalable (MapReduce-friendly), easy to integrate with JanusGraph’s backend partitioner, and has been validated on real-world production graphs (Google Maps, Twitter, Friendster).
Describe a specific use case for the feature:
Distributed graph deployments in JanusGraph currently rely on simple hash or range partitioning, or external partitioners such as METIS.
These methods either:
- don’t scale to billions of edges, or
- produce suboptimal cut quality (leading to excessive cross-partition traversals).
Integrating DBP-LE as a native partitioning strategy would:
- Improve query performance and reduce network I/O by minimizing cross-machine edges.
- Provide balanced data distribution across storage backends.
- Enable better performance for iterative analytics (e.g., PageRank, Connected Components, community detection).
- Support machine-learning workloads (e.g., GNN training) that require balanced graph mini-batches with minimal boundary communication.
Example configuration:
storage.partition.strategy: dbp_linear_embedding
storage.partition.alpha: 0.03
storage.partition.parts: 16
Additional context / references:
Paper: Distributed Balanced Partitioning via Linear Embedding — Aydin, Bateni, Mirrokni, WSDM 2016. DOI: [10.1145/2835776.2835829](https://doi.org/10.1145/2835776.2835829)
Expected benefits:
15–25 % reduction in edge cut size vs. METIS/FENNEL.
40 % fewer cross-shard queries in Google Maps case study.
Linear scalability to hundreds of millions of vertices.
- 主要言語
- Java
- スター
- 5.8k
- フォーク
- 1.2k
- 平均マージ
- 21時間 16分
- マージ済み PR（30日）
- 30
環境構築
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートあり
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
JanusGraph/janusgraph のほかの issue
-
難易度 1/5 1時間未満 初心者へのやさしさ 95/100
JanusGraph/janusgraph#4943 ·
メンテナーはふだん 1 日以内に返信
-
難易度 1/5 1時間未満 初心者へのやさしさ 62/100
JanusGraph/janusgraph#1578 ·
メンテナーはふだん 1 日以内に返信
-
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
JanusGraph/janusgraph#4954 ·
メンテナーはふだん 1 日以内に返信
-
難易度 5/5 1週間以上 初心者へのやさしさ 25/100
JanusGraph/janusgraph#4934 ·
メンテナーはふだん 1 日以内に返信
-
難易度 5/5 1週間以上 初心者へのやさしさ 35/100
JanusGraph/janusgraph#4923 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
JanusGraph/janusgraph の issue をすべて見る
似ている issue
-
area/frontend good first issue kind/cooldown
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 84/100
beehive-lab/TornadoVM#1151 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 88/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 77/100
FasterXML/jackson-dataformats-binary#823 ·
メンテナーはふだん 1 日以内に返信
-
難易度 1/5 1時間未満 初心者へのやさしさ 90/100
メンテナーはふだん 1 日以内に返信