performance - programacion - ¿Almacena gráficos muy grandes en algoritmos de partición de gráficos de disco/transmisión?

pseudocodigo (3)

Ningún algoritmo realmente necesita "encajar en la memoria": siempre puede ingresar y sacar las páginas según sea necesario. Pero desea evitar que el cálculo tarde demasiado tiempo, y la partición global de gráficos en el caso genérico es un problema NP completo, que es "irracionalmente largo" para la mayoría de los problemas que ni siquiera caben en la memoria.

Afortunadamente, desea realizar búsquedas amplias, lo que significa que desea un formato en el que la amplitud de primer grado sea el cálculo sencillo. No conozco ningún algoritmo que haga esto, pero puede construir su propio diseño de amplitud si está dispuesto a permitir un poco de espacio adicional en el disco.

Si los bordes no están sesgados hacia las interacciones locales, entonces desenredar el gráfico será difícil. Si están sesgados hacia las interacciones locales, sugiero un algoritmo como el siguiente:

Elija un conjunto aleatorio de vértices como puntos de partida a lo largo de todo el conjunto de datos.
Para cada vértice, recoge todos los vértices vecinos (realiza un barrido a través del conjunto de datos).
Para cada conjunto de vértices vecinos, recopile el conjunto de vecinos-de-vecinos y clasifíquelos según la cantidad de bordes que se conecten a ellos. Si no tiene espacio en una página para almacenarlos todos, mantenga los vértices más conectados. Si tiene espacio para guardarlos todos, puede desechar los menos útiles (por ejemplo, si la fracción de bordes mantenida dentro de una página / fracción de vértices que necesita una relación de almacenamiento cae "demasiado baja", donde "demasiado baja") dependerá de la amplitud que realmente necesiten las búsquedas, y de si puede o no hacer una poda, etc., y no incluya las del vecindario.
Repita el proceso de recopilación y clasificación de vecinos hasta que su vecindario esté lleno (por ejemplo, llena el tamaño de página que más le convenga). Luego verifique las repeticiones entre los inicios elegidos al azar. Si tiene un pequeño número de vértices que aparecen en ambos, elimínelos de uno u otro, cualquiera que rompa menos aristas. Si tiene una gran cantidad de vértices que aparecen en ambos, mantenga el vecindario con la mejor relación (vértices en el vecindario / borde roto) y tire el otro hacia afuera.

Ahora tiene algunos vecindarios locales que son aproximadamente óptimos a nivel local, ya que las primeras búsquedas tienden a caer dentro. Si su búsqueda de amplitud elimina las ramas improductivas con bastante eficacia, entonces esto es probablemente lo suficientemente bueno. De lo contrario, es probable que desee que los vecindarios adyacentes se agrupen.

Si no necesita que los vecindarios adyacentes se agrupen demasiado, deje de lado los vértices que ha agrupado en barrios y repita el proceso en los datos restantes hasta que se tengan en cuenta todos los vértices. Cambia cada identificador de vértice a (vértice, vecindario), y listo: cuando sigue los bordes, sabe exactamente qué página tomar, y la mayoría de ellos estarán cerca dada la construcción.

Si necesita vecindarios adyacentes, necesitará hacer un seguimiento de sus barrios en crecimiento. Repites el proceso anterior (escoges al azar, creces vecindarios), pero ahora clasificas a los vecinos tanto por la cantidad de bordes que satisfacen dentro del vecindario como por la fracción de bordes que salen del vecindario en un grupo existente. Es posible que necesite factores de ponderación, pero algo así como

score = (# edges within) - (# neighborhoods outside) - (# neighborhoodless edges outside)

probablemente haría el truco.

Ahora bien, esto no es global ni siquiera localmente óptimo, pero esto o algo muy parecido debería proporcionar una estructura muy bien conectada a nivel local, y debería permitirle producir un conjunto de vecindarios con una interconectividad relativamente alta.

De nuevo, depende de si su búsqueda de amplitud prunes ramas o no. Si lo hace, lo más barato es maximizar la interconectividad local. Si no es lo que hay que hacer, es minimizar la conectividad externa, y en ese caso, sugeriría simplemente recopilar conjuntos de ancho hasta cierto tamaño y guardarlos (con duplicación en los bordes de los conjuntos). no está muy limitado por el espacio en el disco duro, ¿verdad?).

Supongamos que tengo un gran gráfico no ponderado, no ponderado (que comienza en cientos de millones de vértices, ~ 10 aristas por vértice), no distribuido y procesado por un solo subproceso único y que deseo hacer búsquedas amplias en él. Espero que estén vinculados a E / S, por lo tanto, necesito un diseño de página de disco bueno para BFS, el espacio en disco no es un problema. Las búsquedas pueden comenzar en cada vértice con la misma probabilidad. Intuitivamente eso significa minimizar el número de bordes entre vértices en diferentes páginas de disco, que es un problema de partición de gráfico.

El gráfico en sí parece un espagueti, piense en un conjunto aleatorio de puntos interconectados aleatoriamente, con cierto sesgo hacia bordes más cortos.

El problema es, ¿cómo una partición grafica así de grande? Los particionadores de gráficos disponibles que he encontrado funcionan con gráficos que se ajustan solo a la memoria. No pude encontrar descripciones ni implementaciones de ningún algoritmo de partición de gráficos de transmisión.

O, ¿tal vez haya una alternativa al gráfico de particiones para obtener un diseño de disco que funcione bien con BFS?

En este momento, como una aproximación, uso el hecho de que los vértices tienen coordenadas espaciales adjuntas a ellos y pongo los vértices en el disco en el orden de clasificación de Hilbert. De esta forma, los vértices espacialmente cercanos aterrizan en la misma página, pero la presencia o ausencia de borde entre ellos se ignora por completo. ¿Puedo hacerlo mejor?

Como alternativa, puedo dividir el gráfico en partes utilizando el orden de clasificación de Hilbert para los vértices, particionar los subgrafos, coserlos hacia atrás y aceptar particiones pobres en las costuras.

Algunas cosas que ya he considerado:

Cómo almacenar un gran gráfico no ponderado dirigido con miles de millones de nodos y vértices
http://neo4j.org/ - Encontré información cero sobre cómo funciona el diseño del gráfico en el disco

Implementaciones de particionamiento (a menos que esté equivocado, todas necesitan encajar el gráfico en la memoria):

EDITAR: información sobre cómo se ven los gráficos y que BFS puede comenzar en cualquier lugar. EDIT: idea sobre partición de subgrafos

Verifique esta publicación en el blog:

"búsqueda gráfica en amplitud utilizando un algoritmo iterativo de reducción de mapas"

http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm

Es posible que desee ver HDF5 . A pesar de que H representa jerárquico, puede almacenar gráficos, verificar la documentación bajo la palabra clave "Grupos" y está diseñado para conjuntos de datos muy grandes. Si entiendo correctamente, los ''archivos'' de HDF5 pueden extenderse a través de múltiples ''o'' s ''archivos''. Ahora, HDF5 es solo una estructura de datos, más un conjunto de bibliotecas para manipulaciones de bajo y alto nivel de la estructura de datos. De repente, no tengo ni idea acerca de la transmisión de algoritmos de partición de gráficos, pero me atengo a la idea de que si obtienes la estructura de datos, los algoritmos correctos serán más fáciles de implementar.

¿Qué es lo que ya sabes sobre el mega-gráfico? ¿Se divide naturalmente en subgrafos densos que a su vez están escasamente conectados? ¿Sería un tipo topológico del gráfico una mejor base para el almacenamiento en disco que el ordenamiento espacial existente?

Si fallan las respuestas nítidas a tales preguntas, tal vez solo tenga que lidiar con la bala y leer el gráfico varias veces para construir las particiones, en cuyo caso solo desea la E / S más rápida que pueda administrar, y el diseño sofisticado de las particiones en los nodos es agradable pero no tan importante. Si puede dividir el gráfico en subgráficos que tienen bordes individuales para los otros subgráficos, tal vez pueda hacer que el problema sea más manejable.

Desea un diseño bueno para BFS, pero BFS generalmente se aplica a árboles. ¿Su gráfico tiene una raíz única desde la que iniciar todos los BFS? De lo contrario, el diseño de BFS desde un vértice no será óptimo para BFS desde otro vértice.