Tener miles de millones de nodos y solo millones de bordes indica que muchos nodos están aislados. ¿Es este realmente el caso?
Sin embargo, parece que solo le interesa una carga equilibrada durante el procesamiento. En este caso, definitivamente debe considerar el Hashing simple de nodos a máquinas. Esto da como resultado particiones casi perfectamente equilibradas y es extremadamente rápido.
Si le interesa la localidad de los vértices (lo cual recomendaría encarecidamente) para minimizar la sobrecarga de la comunicación y mejorar la latencia de extremo a extremo, debería considerar la posibilidad de transmitir algoritmos de partición . Este es uno de los documentos clave de KDD 2012.
- ¿Qué es un algoritmo fácil de implementar para estimar la complejidad de Kolmogorov de una secuencia finita?
- Gráfico distribuido: ¿Cuál es la forma más efectiva de distribuir los nodos de un gráfico en diferentes servidores en un sistema distribuido?
- ¿YouTube está sesgado políticamente?
- En los concursos de programación, ¿puedo adivinar la complejidad temporal de la solución (digamos n, n ^ 2, log n) para el problema, dado el límite de tiempo para el problema?
- ¿Cuál es una explicación intuitiva del ataque de cumpleaños en criptografía?
Por cierto, Victor definitivamente tiene un punto en recomendar la partición de corte de vértice en lugar de la partición de corte de borde. Esto puede resultar en un mejor equilibrio de carga y menos sobrecarga de comunicación para gráficos con distribución de grados sesgada (es decir, la mayoría de los gráficos del mundo real; piense en el número de seguidores de Twitter de Justin Bieber en comparación con cualquier usuario aleatorio de Twitter). Sin embargo, también hay MUCHOS sistemas de gráficos extremadamente escalables basados en corte de bordes (es decir, asignación de vértices) que pueden procesar gráficos de billones de escalas (!). Echa un vistazo a este documento VLDB, por ejemplo.
Los algoritmos de particionamiento de transmisión tienen un tiempo de ejecución lineal y proporcionan una ubicación razonable (es decir, calidad de particionamiento). Para tareas de procesamiento de gráficos de complejidad baja a media, esta clase algorítmica debe estar muy cerca de lo óptimo. Si tiene tareas de procesamiento de gráficos más complejas, puede valer la pena verificar algoritmos más sofisticados que mejoran aún más la localidad, a costa de una mayor inversión de tiempo inicial para la partición.
