Хранение очень больших графиков на алгоритмах разделения диска/потоковой диаграммы?
Предположим, что у меня есть очень большой неориентированный, невзвешенный график (запускающийся в сотнях миллионов вершин, ~10 краях на вершину), нераспределенный и обработанный единственным потоком только и что я хочу сделать поиски в ширину на нем. Я ожидаю, что они будут I/O-bound, таким образом мне нужен хороший для BFS дисковый макет страницы, дисковое пространство не является проблемой. Поиски могут запуститься на каждой вершине с равной вероятности. Интуитивно это означает минимизировать количество краев между вершинами на различных дисковых страницах, которое является проблемой разделения графика.
Сам график похож на спагетти, думайте о случайном наборе точек, случайным образом взаимосвязанном, с некоторыми склоняют к более коротким краям.
Проблема, как один раздел изображает в виде графика это большое? Доступный график partitioners, которому я нашел работу с графиками, которые вписываются в память только. Я не мог найти описания, ни реализации никакой потоковой диаграммы, делящей алгоритмы.
ИЛИ, возможно, существует альтернатива разделению графика для получения структуры диска, которая работает хорошо с BFS?
Прямо сейчас как приближение я использую то, что вершинам присоединили пространственные координаты к ним и помещают вершины на диск в Гильбертовом порядке сортировки. Этот путь пространственно закрывает землю вершин на той же странице, но присутствие или отсутствие края между ними полностью проигнорированы. Я могу добиться большего успеха?
Как альтернатива, я могу разделить график на части с помощью Гильбертова порядка сортировки для вершин, разделить подграфы, сшить их назад и принять плохое разделение на швах.
Некоторые вещи я уже изучил:
- Как снабдить большой направленный невзвешенный график миллиардами узлов и вершин
- http://neo4j.org/ - Я нашел нулевую информацию о том, как она делает расположение графика на диске
Разделение реализаций (если я не ошибаюсь, все они должны вместить график в память):
- http://glaros.dtc.umn.edu/gkhome/views/metis
- http://www.sandia.gov/~bahendr/chaco.html
- http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/
- http://www.cerfacs.fr/algor/Softs/MESHPART/
Править: информация о том, как графики похожи и который BFS может запустить везде. Править: идея разделить подграфы
2 ответа
Ни один алгоритм не должен "вписываться в память" - вы всегда можете вставлять и выставлять все по мере необходимости. Но вы хотите избежать того, чтобы вычисления занимали неоправданно долгое время, и глобальное разбиение графиков в общем случае является NP-завершенной проблемой, которая "неоправданно долго" для большинства проблем, которые даже не умещаются в памяти.
К счастью, вы хотите выполнять поиск по широте, что означает, что вам нужен формат, в котором широта - это простое вычисление. Я не знаю ни одного алгоритма, который делал бы это вручную, но вы можете построить свою собственную компоновку для начала, если вы хотите предоставить немного дополнительного дискового пространства.
Если края не смещены в сторону локальных взаимодействий, то разобрать граф будет сложно. Если они смещены в сторону локальных взаимодействий, то я предлагаю такой алгоритм, как:
- Выберите случайный набор вершин в качестве исходных точек со всего массива данных.
- Для каждой вершины соберите все соседние вершины (сделайте один проход по всему массиву данных).
- Для каждого множества соседних вершин собираем множество соседних вершин и ранжируем их в соответствии с количеством рёбер, с которыми они соединяются. Если на странице не хватает места для их хранения, сохраните наиболее связанные вершины. Если у вас есть место, чтобы сохранить их все, вы можете выбросить наименее полезные (например, если доля ребер, хранящихся в пределах страницы / доля вершин, нуждающихся в хранении, упадет "слишком низко" - где "слишком низко" будет зависеть от того, насколько широта ваших поисков действительно нужна, и сможете ли вы сделать какую-нибудь обрезку и т.д. - тогда не включайте те, которые находятся поблизости.
- Повторяйте процесс сбора и ранжирования соседей до тех пор, пока ваш район не будет заполнен (например, заполните страницу какого-нибудь подходящего вам размера). Затем проверьте, нет ли повторов среди случайно выбранных стартов. Если в обеих вершинах появляется небольшое количество вершин, удалите их из той или иной, в зависимости от того, какая вершина разбивает меньшее количество рёбер. Если у вас большое количество вершин, появляющихся в обеих, держите окрестность в лучшем соотношении (вершины в окрестности/ломаное ребро) и выкидывайте другую.
Теперь у вас есть некоторые локальные окрестности, которые приблизительно локально оптимальны в том случае, если поиск по ширине - первый поиск имеет тенденцию к попаданию внутрь. Если ваш поиск в первую очередь достаточно эффективно подрезает непродуктивные ветви, то, вероятно, этого вполне достаточно. Если нет, то, скорее всего, вы хотите, чтобы соседние районы были сконцентрированы.
Если вам не нужно, чтобы соседние районы слишком много группировались, отложите в сторону вершины, которые вы сгруппировали по районам, и повторите процесс на оставшихся данных, пока не будут учтены все вершины. Вы меняете идентификатор каждой вершины на (вершина, окрестность), и все: когда вы следуете за рёбрами, вы точно знаете, какую страницу захватить, и большинство из них будет близко по заданной конструкции.
Если вам действительно нужны соседние районы, то вам нужно будет следить за своими растущими соседями. Вы повторяете предыдущий процесс (выбираете случайным образом растущие кварталы), но теперь ранжируйте соседей по количеству рёбер внутри квартала и , какая часть их рёбер, покидающих квартал, входит в существующую группу. Вам могут понадобиться весовые коэффициенты, но что-то вроде
score = (# edges within) - (# neighborhoods outside) - (# neighborhoodless edges outside)
, вероятно, поможет.
Сейчас это не глобально или даже локально оптимально, но это или что-то в этом роде должно дать красивую локально связанную структуру, и должно позволить вам создать покрывающий набор соседей, которые имеют относительно высокую взаимосвязанность.
Опять же, это зависит от того, будет ли ваш первый широковещательный поиск обрезать ветви или нет. Если это так, то дешевле всего будет максимизировать локальную взаимосвязанность. Если это не так, то нужно минимизировать внешнюю взаимосвязь - и в этом случае я бы предложил просто собрать первые по ширине наборы до некоторого размера и сохранить их (с дублированием по краям наборов - вы ведь не сильно ограничены местом на жестком диске, не так ли?).
Вы можете посмотреть HDF5 . Несмотря на то, что Hierarchical, он может хранить графики, проверьте документацию по ключевому слову «Группы», и он предназначен для очень больших наборов данных. Если я пойму правильно правильно HDF5 «Файлы», могут быть распространены по нескольким операциям O / S 'файлы ». Теперь HDF5 является только структурой данных, а также набор библиотек для манипуляций низко- и высокого уровня структуры данных. В верхней части моей головы у меня нет подсказки о потоковых алгоритмах разбивающих графиков, но я придерживаюсь понятия, что если вы получите правильные алгоритмы в структуре данных, становятся легче реализации.
Что вы уже знаете о мега-графе? Естественно ли разбит в густых подграфах, которые сами редко связаны? Будет ли топологический сорт графика лучшей основой для хранения на диске, чем существующий пространственный сортировк?
Неспособность четких ответов на такие вопросы, может быть, вам просто нужно кусать пулю и прочитать график несколько раз, чтобы построить разделы, В этом случае вы просто хотите самого быстрого ввода / вывода, и сложный макет разделов на узлах приятно, но не так важно. Если вы сможете разбивать график на подмассы, которые сами имеют отдельные края к другим подмагам, которые вы можете сделать проблему более прочную.
Вы хотите, чтобы макет хорошего для BFS, но BFS обычно применяется к деревьям. У вашего графика есть уникальный root, от которого начинать все BFSES? Если нет, то макет для BFS из одной вершины будет неоптимальным для BFS из другой вершины.