Подтвердить что ты не робот

Хранение очень больших графиков на алгоритмах разделения дисков/потоковых графов?

Предположим, что у меня есть очень большой неориентированный, невзвешенный граф (начиная с сотен миллионов вершин, ~ 10 ребер на вершину), не распределенный и обрабатываемый только одним потоком, и что я хочу выполнить поиск в первой строке Это. Я ожидаю, что они будут связаны с I/O-привязкой, поэтому мне нужен макет страницы с хорошим для BFS диском, дисковое пространство не является проблемой. Поиски могут начинаться с каждой вершины с равной вероятностью. Интуитивно это означает минимизацию количества ребер между вершинами на разных страницах диска, что является проблемой разбиения графа.

Сам граф выглядит как спагетти, думайте о случайном множестве точек, случайно связанных между собой, с некоторым смещением к более коротким ребрам.

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

ИЛИ, может быть, есть альтернатива графу разделения для получения макета диска, который хорошо работает с BFS?

Сейчас в качестве приближения я использую тот факт, что вершины имеют прикрепленные к ним пространственные координаты и помещают вершины на диск в порядке сортировки Гильберта. Таким образом, пространственно закрытые вершины приземляются на одной странице, но наличие или отсутствие края между ними полностью игнорируется. Могу ли я лучше?

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

Некоторые вещи, на которые я уже посмотрел:

Разделение реализаций (если я не ошибаюсь, все они должны соответствовать графику в памяти):

EDIT: информация о том, как выглядят графики и что BFS может начинаться повсюду. EDIT: идея разбиения подграфов

4b9b3361

ОТВЕТЫ

Ответ 1

Никакой алгоритм действительно не должен "вписываться в память" - вы всегда можете вставлять страницы туда и сюда по мере необходимости. Но вы не хотите, чтобы вычисления выполнялись неоправданно долго, а глобальное разбиение графов в общем случае представляет собой NP-полную проблему, которая является "необоснованно длинной" для большинства проблем, которые даже не вписываются в память.

К счастью, вы хотите выполнить поиск по ширине, что означает, что вы хотите формат, в котором вначале это простое вычисление. Я не знаю никаких алгоритмов, которые делают это, но вы можете создать свой собственный макет ширины, если вы готовы разрешить немного дополнительного дискового пространства.

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

  • Выберите случайный набор вершин в качестве отправных точек из всего набора данных.
  • Для каждой вершины собирайте все соседние вершины (выполняется одна прокрутка по набору данных).
  • Для каждого набора соседних вершин собирайте множество соседей-соседей и оценивайте их в соответствии с тем, сколько ребер связано с ними. Если у вас нет места на странице, чтобы сохранить их все, сохраните наиболее связанные вершины. Если у вас есть место, чтобы сохранить их все, вы можете захотеть выбросить наименее полезные (например, если фракция ребер, содержащихся в пределах страницы/доли вершин, требующих коэффициента хранения, падает "слишком низко" - где "слишком мало", будет зависеть от того, насколько сильно нужны ваши поиски, и можете ли вы сделать обрезку и т.д. - тогда не включайте тех, кто находится по соседству.
  • Повторите процесс сбора и ранжирования соседей, пока ваш район не будет заполнен (например, заполняет какой-то размер страницы, который вам подходит). Затем проверьте повторы между случайно выбранными запусками. Если у вас есть небольшое количество вершин, появляющихся в обоих случаях, удалите их из одного или другого, в зависимости от того, что нарезает меньше ребер. Если у вас есть большое количество вершин, появляющихся в обоих, сохраните окрестности с наилучшим соотношением (вершины в окрестности/сломанной кромке) и выбросьте другую сторону.

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

Если вам не нужны соседние районы для слишком большого кластера, вы отложите вершины, которые вы сгруппировали в окрестности, и повторите процесс по оставшимся данным до тех пор, пока не будут учтены все вершины. Вы меняете каждый идентификатор вершины на (вершину, окрестности), и все готово: при следующих краях вы точно знаете, какую страницу захватывать, и большинство из них будут близки по заданной конструкции.

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

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

вероятно, сделает трюк.

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

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

Ответ 2

Вы можете посмотреть HDF5. Несмотря на то, что H для Иерархического, он может хранить графики, проверять документацию под ключевым словом "Группы" и предназначен для очень больших наборов данных. Если я правильно понимаю, что файлы HDF5 можно распространять на несколько файлов o/s. Теперь HDF5 представляет собой только структуру данных, а также набор библиотек для низкоуровневых манипуляций структуры данных. В верхней части моей головы я понятия не имею о потоковых алгоритмах разбиения графов, но я придерживаюсь понятия, что если вы получите правильные алгоритмы структуры данных, их проще реализовать.

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

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

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