Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

Proposal: Implement Distributed Balanced Partitioning via Linear Embedding (DBP-LE)

Đang mở
  • Có gì không ổn?
#4,875 0 bình luận 1 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 2 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
25/100
Loại issue
Tính năng
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Đình trệ
Công nghệ
java
Lĩnh vực
databases, distributed-systems

Hướng nghiên cứu

Bắt đầu bằng cách xem xét bộ phân vùng backend của JanusGraph và bài báo DBP-LE được trích dẫn, sau đó so sánh đề xuất với các phương pháp phân vùng hiện có theo hash, theo phạm vi và bên ngoài. Công việc hoàn tất khi DBP-LE được tích hợp như một chiến lược tùy chọn với cấu hình được đề xuất và tạo ra các phân vùng cân bằng với số lượng edge cut giảm.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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:

  1. Embedding vertices into a one-dimensional linear order using affinity (common-neighbor similarity).
  2. Performing local refinements via Minimum Linear Arrangement (MinLA) and RankSwap.
  3. 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.
Ngôn ngữ chính
Java
Star
5.9k
Fork
1.2k
Merge trung bình
2 ngày 8 giờ
Pull request đã merge (30 ngày)
73

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của JanusGraph/janusgraph

Tất cả issue của JanusGraph/janusgraph

Issue tương tự

Thêm issue về Java

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.