enorme estructura de gráfico

Estoy desarrollando una aplicación en la que necesito una estructura para representar un gran gráfico (entre 1000000 y 6000000 nodos y 100 o 600 bordes por nodo) en la memoria. La representación de los bordes contendrá algunos atributos de la relación.enorme estructura de gráfico

He intentado una representación de mapa de memoria, matrices, diccionarios y cadenas para representar esa estructura en la memoria, pero estos siempre se bloquean debido al límite de memoria.

Me gustaría obtener un consejo de cómo puedo representar esto, o algo similar.

Por cierto, estoy usando python.

Fuente

2010-05-10 Harph

dijiste que solo hay 600 bordes, ¿por qué no almacenarlos? – Cam

¿Quiere decir 100-600 bordes por nodo? – tster

Necesita usar una base de datos, ya que su conjunto de datos, incluso con un puntero por cada dato, es enorme, y mucho menos como objetos de Python. Cómo quiere consultar y recorrer su gráfico determinará qué tipo de base de datos utiliza. –

Si eso es 100-600 bordes/nodo, entonces estás hablando de 3.6 billones de bordes.
¿Por qué tiene que ser todo en la memoria?
¿Puede mostrarnos las estructuras que está utilizando actualmente?
¿Cuánta memoria se nos permite (¿cuál es el límite de memoria que está golpeando?)

Si la única razón por la que necesita esta en la memoria se debe a que necesita para ser capaz de leer y escribir de forma rápida, a continuación, usa una base de datos Las bases de datos leen y escriben extremadamente rápido, a menudo pueden leer sin tener que ir al disco.

Fuente

2010-05-10 22:23:10 tster

+1: esta no es una respuesta, pero todas estas preguntas tienen que ser respondidas antes de que podamos proceder – Claudiu

bien ... cada nodo tiene entre 100 y 600 bordes. Tengo que mantener esto en la memoria (memoria RAM) porque se debe acceder constantemente. También se actualizará constantemente, cambiando los pesos de las relaciones, agregando y eliminando nodos y bordes. Todo esto debe tener un buen rendimiento (tiempo de respuesta). – Harph

He intentado muchas estructuras diferentes como diccionarios, listas y combinaciones de objetos para representar la matriz de adyacencia. Yo, también he intentado mapear este intro de un archivo, usando y partición xt4, pero cuando tengo que escribir al azar, lleva mucho tiempo y gasta mucha memoria porque la escritura en bloque. Ahora mismo estoy probando esto en mi propia máquina con 4 gb. Cuando vaya a implementarlo, usaré un servidor con algo de memoria (espero menos de 1 Tera). – Harph

Parece que tiene muy pocos bordes teniendo en cuenta la cantidad de nodos, lo que sugiere que la mayoría de los nodos no son estrictamente necesarios. Entonces, en lugar de almacenar todos los nodos, ¿por qué no usar una estructura dispersa y solo insertarlos cuando están en uso? Esto debería ser bastante fácil de hacer con un diccionario; simplemente no inserte el nodo hasta que lo use para un borde.

Los bordes se pueden almacenar utilizando un adjacency list en los nodos.

Por supuesto, esto solo se aplica si realmente quiere decir 100-600 nodos en total. Si te refieres a cada nodo, esa es una historia completamente diferente.

Fuente

2010-05-10 22:23:26

dudo que será capaz de utilizar una estructura de memoria a menos que tenga una gran cantidad de memoria a su disposición:

Supongamos que estamos hablando de unos 600 bordes dirigidos desde cada nodo, con un nodo de ser de 4 bytes (clave entera) y un borde dirigido SÓLO las claves del nodo de destino (4 bytes cada una).

Entonces los datos en bruto sobre cada nodo es 4 + 600 * 4 = 2404 bytes x 6.000.000 = sobre 14.4GB

Eso es sin otros gastos generales o datos adicionales en los nodos (o bordes).

Fuente

2010-05-10 22:29:34

Sin embargo, los sistemas con 16 GB o más de RAM son bastante comunes. Tengo un servidor HP usado que pagué menos de $ 500 por 16 GB. Tengo servidores trabajando con 512 GB o 1TB. Incluso he usado algunos en un trabajo anterior con múltiples TB de RAM. Por ejemplo, aquí hay un Dell viejo que admite hasta 6 TB: http://www.dell.com/en-us/work/shop/productdetails/poweredge-r920 –

@BrianMinton El punto sigue siendo válido ahora, ya que era 7 hace años que.Una vez que agrega el sistema de asignación para administrar esa cantidad de datos, sigue siendo muy importante almacenar dicha estructura en la memoria en lugar de simplemente conservarla en una estructura de base de datos adecuada. –

Parece que necesita una base de datos y un iterador sobre los resultados. Entonces no tendrías que tener todo guardado en la memoria al mismo tiempo, pero siempre podrías tener acceso a él.

Fuente

2010-05-10 22:34:54 exupero

Sin duda necesita algún tipo de almacén de datos que no sea memoria, pero ¿qué es "un iterador sobre los resultados"? Los algoritmos de gráficos generalmente no se van a satisfacer con un iterador simple. –

Podría significar "generador", como en '(uva [tallo] para uva en racimo)' o una función que usa 'rendimiento '. – exupero

Si decide utilizar algún tipo de base de datos después de todo, sugiero mirar neo4j y sus enlaces de python. Es una base de datos de gráficos capaz de manejar gráficos grandes. Aquí hay un presentation del PyCon de este año.

Fuente

2010-05-11 08:01:27 miles82

Suponiendo que quiere decir 600 por nodo, podría intentar algo como esto:

import os.path 
import cPickle 
class LazyGraph: 
    def __init__(self,folder): 
     self.folder = folder 

    def get_node(self,id): 
     f = open(os.path.join(self.folder,str(id)),'rb') 
     node = cPickle.load(f) 
     f.close() # just being paranoid 
     return node 

    def set_node(self,id,node): 
     f = open(os.path.join(self.folder,str(id)),'wb') 
     cPickle.dump(node,f,-1) # use highest protocol 
     f.close() # just being paranoid

Use matrices (o matrices numpy) para mantener el ID de nodos reales, ya que son más rápidos.

Nota, esto será muy, muy lento.

Puede utilizar el enhebrado para buscar previamente los nodos (suponiendo que sepa en qué orden los está procesando), pero no será divertido.

Fuente

2010-05-11 09:15:53 wisty

Dependiendo de sus recursos de hardware, todo en la memoria para un gráfico de este tamaño probablemente esté fuera de discusión. Dos opciones posibles desde el punto de DB gráfico de vista específico son:

Neo4j - activos para manejar fácilmente miles de nodos y su estado en desarrollo desde hace mucho tiempo.
FlockDB - recientemente lanzado por Twitter se trata de una base de datos de gráficos distribuidos.

Dado que usa Python, ¿ha mirado Networkx? ¿Qué tan lejos llegaste a cargar un gráfico de este tamaño si lo has visto sin interés?

Fuente

2010-05-12 00:39:20

Gracias por su respuesta ... He intentado con Networkx, pero se ajusta a mis requisitos (uso mucha memoria). Neo4j es demasiado caro. Lo probaré con flockDB. – Harph

He leído sobre FlockDB ... parece bastante genial, pero tengo muchos problemas para instalarlo. Creo que FlockDB está en versión alpha. No tiene buena documentación/soporte. – Harph

Neo4j tiene una versión de código abierto que puede ser útil. https://neo4j.com/open-source-project/ –

El paquete scipy.sparse.csgraph puede ser capaz de manejar esto - 5 millones de nodos * 100 bordes en promedio son 500 millones de pares, en 8 bytes por par (dos ID enteros) es de aproximadamente 4 GB. Creo que csgraph usa compresión por lo que utilizará menos memoria que eso; esto podría funcionar en tu computadora portátil.

csgraph no tiene tantas características como networkx pero usa waaay menos memoria.

Fuente

2016-02-28 16:23:35 amwinter

Respuesta

Cuestiones relacionadas