Огромная структура графиков - PullRequest
7 голосов
/ 11 мая 2010

Я разрабатываю приложение, в котором мне нужна структура для представления огромного графа (от 1000000 до 6000000 узлов и 100 или 600 ребер на узел) в памяти. Представление ребер будет содержать некоторые атрибуты отношения.

Я пробовал представление карты памяти, массивы, словари и строки для представления этой структуры в памяти, но они всегда вылетали из-за ограничения памяти.

Я хотел бы получить совет о том, как я могу изобразить это или что-то подобное.

Кстати, я использую Python.

Ответы [ 8 ]

14 голосов
/ 11 мая 2010
  1. Если это 100-600 ребер / узел, то речь идет о 3,6 млрд ребер.
  2. Почему все это должно быть в памяти?
  3. Можете ли вы показать нам структуры, которые вы используете в настоящее время?
  4. Сколько памяти нам разрешено (какой лимит памяти вы используете?)

Если единственная причина, по которой вам нужно это в памяти, это то, что вам нужно уметь быстро читать и писать, тогда используйте базу данных. Базы данных читают и пишут очень быстро, часто они могут читать, не заходя на диск вообще.

6 голосов
/ 12 мая 2010

В зависимости от ваших аппаратных ресурсов, все в памяти для графика такого размера, вероятно, не может быть и речи. Два возможных варианта с точки зрения конкретной графической БД:

  • Neo4j - заявляет, что легко обрабатывает миллиарды узлов и давно разрабатывается.
  • FlockDB - недавно выпущенный Twitter, это база данных распределенных графов.

После того, как вы используете Python, вы смотрели на Networkx ? Как далеко вы загрузили график такого размера, если смотрели на него из интереса?

3 голосов
/ 11 мая 2010

Я сомневаюсь, что вы сможете использовать структуру памяти, если у вас не будет много памяти в вашем распоряжении:

Предположим, что вы говорите о 600 направленных ребрах от каждого узла, причем узел является 4-байтовым (целочисленный ключ), а направленный ребро - ПРОСТО ключи целевого узла (4 байта каждый).

Тогда необработанные данные о каждом узле равны 4 + 600 * 4 = 2404 байта x 6 000 000 = более 14,4 ГБ

Это без каких-либо других издержек или дополнительных данных в узлах (или ребрах).

3 голосов
/ 11 мая 2010

Похоже, что у вас очень мало ребер, учитывая количество узлов - это говорит о том, что большинство узлов не являются строго необходимыми. Итак, вместо того, чтобы фактически хранить все узлы, почему бы не использовать разреженную структуру и вставлять их только тогда, когда они используются? Это должно быть довольно легко сделать со словарем; просто не вставляйте узел, пока не используете его для ребра.

Ребра могут быть сохранены с использованием списка смежности на узлах.

Конечно, это применимо, только если вы действительно имеете в виду 100-600 узлов. Если вы имеете в виду на узел, это совсем другая история.

2 голосов
/ 28 февраля 2016

Пакет scipy.sparse.csgraph может справиться с этим - 5 миллионов узлов * 100 ребер в среднем составляют 500 миллионов пар, при 8 байтах на пару (два целых идентификатора) примерно 4ГБ. Я думаю, csgraph использует сжатие, поэтому оно будет использовать меньше памяти; это может работать на вашем ноутбуке.

csgraph не обладает таким количеством функций, как networkx, но использует меньше памяти.

1 голос
/ 11 мая 2010

Предполагая, что вы имеете в виду 600 на узел, вы можете попробовать что-то вроде этого:

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

Используйте массивы (или пустые массивы) для хранения фактических идентификаторов узлов, так как они быстрее.

Обратите внимание, это будет очень очень медленно.

Вы можете использовать многопоточность для предварительной выборки узлов (при условии, что вы знали, в каком порядке вы их обрабатываете), но это будет неинтересно.

0 голосов
/ 11 мая 2010

Если вы все-таки решите использовать какую-то базу данных, я советую посмотреть neo4j и ее привязки к python. Это графическая база данных, способная обрабатывать большие графы. Вот презентация от PyCon этого года.

0 голосов
/ 11 мая 2010

Похоже, вам нужна база данных и итератор для результатов. Тогда вам не нужно будет хранить все это в памяти одновременно, но вы всегда можете иметь к нему доступ.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...