Proposal: Implement Distributed Balanced Partitioning via Linear Embedding (DBP-LE)
维护者通常 1 天内回复
还没有人认领这个 Issue。
评估
- 难度
- 5/5
- 预计耗时
- 一周以上
- 新手友好度
- 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.9k
- 派生
- 1.2k
- 平均合并
- 1 天 14 小时
- 30 天内合并 PR
- 65
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
JanusGraph/janusgraph 的其他 Issue
-
Add Janus Studio to the Visualization section可能已有人在做 @Zorabi 于 57 天前认领。 未关闭
难度 1/5 1 小时以内 新手友好度 95/100
JanusGraph/janusgraph#4943 ·
维护者通常 1 天内回复
-
难度 1/5 1 小时以内 新手友好度 62/100
JanusGraph/janusgraph#1578 ·
维护者通常 1 天内回复
-
Lucene 9 miswrites some long strings with unpaired surrogates可能已有人在做 @porunov 于 1 天前认领。 未关闭
难度 4/5 3-5 天 新手友好度 15/100
JanusGraph/janusgraph#5111 ·
维护者通常 1 天内回复
-
Removed floats of LIST and SET keys are still found on Lucene可能已有人在做 @porunov 于 1 天前认领。 未关闭
难度 4/5 3-5 天 新手友好度 22/100
JanusGraph/janusgraph#5109 ·
维护者通常 1 天内回复
-
order().by(key) returns the elements without the key, which TinkerPop leaves out可能已有人在做 @porunov 于 1 天前认领。 未关闭
难度 4/5 3-5 天 新手友好度 15/100
JanusGraph/janusgraph#5107 ·
维护者通常 1 天内回复
查看 JanusGraph/janusgraph 的全部 Issue
相似的 Issue
-
难度 2/5 1-3 小时 新手友好度 72/100
-
bug
难度 1/5 1 小时以内 新手友好度 88/100
PhasetransCrystal/FPSMatch#47 ·
维护者通常 1 天内回复
-
bug
难度 1/5 1 小时以内 新手友好度 76/100
apache/maven-toolchains-plugin#205 · 1 条评论 ·
维护者通常 2 天内回复
-
难度 1/5 1 小时以内 新手友好度 90/100
维护者通常 1 天内回复
-
[Bug] Dated CSV export filenames use the UTC day rather than the operator day可能已有人在做 关联的 PR 仍在进行中或已合并。 未关闭
难度 2/5 1-3 小时 新手友好度 82/100
apache/rocketmq-dashboard#6896 ·
维护者通常 3 天内回复