Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

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

Abierto
  • ¿Algo no está bien?
#4,875 0 comentarios 1 reacción 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
25/100
Tipo de issue
Nueva funcionalidad
Claridad
Bastante claro
Estado de actividad
Estancado
Stack tecnológico
java
Área
databases, distributed-systems

Línea de trabajo

Comienza revisando el particionador de backend de JanusGraph y el artículo citado sobre DBP-LE; después, compara la propuesta con los enfoques existentes de particionamiento por hash, por rangos y externo. El trabajo estará terminado cuando DBP-LE esté integrado como una estrategia opcional con la configuración propuesta y produzca particiones equilibradas con menos cortes de aristas.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.
Lenguaje dominante
Java
Estrellas
5.8k
Forks
1.2k
Merge medio
22 h 17 min
PR fusionados (30 d)
28

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de JanusGraph/janusgraph

Todos los issues de JanusGraph/janusgraph

Issues similares

Más issues de Java

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.