Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

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

Aperta
  • Qualcosa non va?
#4,875 0 commenti 1 reazione 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Funzionalità
Chiarezza
Abbastanza chiara
Stato di attività
Ferma
Stack tecnologico
java
Ambito
databases, distributed-systems

Direzione di ricerca

Inizia esaminando il partizionatore del backend di JanusGraph e il paper citato su DBP-LE, quindi confronta la proposta con gli approcci esistenti di partizionamento hash, per intervallo ed esterno. Il lavoro è completato quando DBP-LE è integrato come strategia opzionale con la configurazione proposta e produce partizioni bilanciate con un numero ridotto di edge cut.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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.
Lingua principale
Java
Stelle
5.8k
Fork
1.2k
Merge medio
22h 17m
PR unite (30g)
28

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di JanusGraph/janusgraph

Tutte le issue di JanusGraph/janusgraph

Issue simili

Altre issue su Java

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.