Обход графа внешней памяти - External memory graph traversal

Обход графа внешней памяти это тип обход графа оптимизирован для доступа к внешней памяти.

Фон

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

Модель внешней памяти

За алгоритмы внешней памяти модель внешней памяти Аггарвала и Виттера^[1] используется для анализа. Машина определяется тремя параметрами: M, B и D.M это размер внутренней памяти, B размер блока диска и D - количество параллельных дисков. Показателем производительности алгоритма внешней памяти является количество выполняемых им операций ввода-вывода.

Поиск в ширину внешней памяти

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

Мунагала и Ранаде

Визуализация для вычисления L (t) в системе Munagala-Ranade-поиск в ширину алгоритм.

Для неориентированного графа ${\displaystyle G}$, Мунагала и Ранаде^[2] предложил следующий алгоритм внешней памяти:

Позволять ${\displaystyle L(t)}$ обозначим узлы на уровне поиска в ширину t и пусть ${\displaystyle A(t):=N(L(t-1))}$ - множество соседей уровня t-1. Для каждого t ${\displaystyle L(t)}$ может быть построен из ${\displaystyle A(t)}$ преобразовав его в набор и исключив из него ранее посещенные узлы.

1. Создавать ${\displaystyle A(t)}$ путем доступа к списку смежности каждой вершины в ${\displaystyle L(t-1)}$. Этот шаг требует ${\displaystyle O(|L(t-1)|+|A(t)|/(D\cdot B))}$ Ввод / вывод.
2. Следующий ${\displaystyle A'(t)}$ создан из ${\displaystyle A(t)}$ удалив дубликаты. Это может быть достигнуто путем сортировки ${\displaystyle A(t)}$, за которым следует этап сканирования и уплотнения, требующий ${\displaystyle O(\operatorname {sort} (|A|))}$ Ввод / вывод.
3. ${\displaystyle L(t):=A'(t)\backslash \{L(t-1)\cup L(t-2)\}}$ рассчитывается путем параллельного сканирования по ${\displaystyle L(t-1)}$ и ${\displaystyle L(t-2)}$ и требует ${\displaystyle O((|A(t)|+|L(t-1)|+|L(t-2)|)/(D\cdot B))}$ Ввод / вывод.

Общее количество операций ввода-вывода этого алгоритма следует с учетом того, что ${\displaystyle \sum _{t}|A(t)|=O(m)}$ и ${\displaystyle \sum _{t}|L(t)|=O(n)}$ и является ${\displaystyle O(n+\operatorname {sort} (n+m))}$.

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

Мельхорн и Мейер

Мельхорн и Мейер^[3] предложили алгоритм, основанный на алгоритме Мунагала и Ранаде (MR) и улучшивший их результат.

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

На этапе предварительной обработки граф разбивается на несвязные подграфы. ${\displaystyle S_{i},\,0\leq i\leq K}$ с малым диаметром. Он дополнительно разбивает списки смежности соответственно, создавая внешний файл ${\displaystyle F=F_{0}F_{1}\dots F_{K-1}}$, куда ${\displaystyle F_{i}}$ содержит список смежности для всех узлов в ${\displaystyle S_{i}}$.

Фаза поиска в ширину аналогична алгоритму MR. Кроме того, алгоритм поддерживает отсортированный внешний файл. ${\displaystyle H}$. Этот файл инициализируется с помощью ${\displaystyle F_{0}}$. Кроме того, узлы любого созданного уровня поиска в ширину несут идентификаторы файлов. ${\displaystyle F_{i}}$ их соответствующих подграфов ${\displaystyle S_{i}}$. Вместо использования случайного доступа для построения ${\displaystyle L(t)}$ файл ${\displaystyle H}$ используется.

1. Выполнить параллельное сканирование отсортированного списка ${\displaystyle L(t-1)}$ и ${\displaystyle H}$. Извлеките списки смежности для узлов ${\displaystyle v\in L(t-1)}$, которые можно найти в ${\displaystyle H}$.
2. Списки смежности для оставшихся узлов, которые не могут быть найдены в ${\displaystyle H}$ нужно получить. Сканирование поверх ${\displaystyle L(t-1)}$ дает идентификаторы разделов. После сортировки и удаления дубликатов соответствующие файлы ${\displaystyle F_{i}}$ может быть объединен во временный файл ${\displaystyle F'}$.
3. Списки недостающих смежностей можно извлечь из ${\displaystyle F'}$ со сканированием. Затем оставшиеся списки смежности объединяются в ${\displaystyle H}$ за один проход.
4. ${\displaystyle A(t)}$ создается простым сканированием. Информация о разделах прикреплена к каждому узлу в ${\displaystyle A(t)}$.
5. Алгоритм работает как алгоритм MR.

Края могут сканироваться чаще в ${\displaystyle H}$, но неструктурированный ввод-вывод для получения списков смежности сокращается.

Общее количество операций ввода-вывода для этого алгоритма составляет ${\displaystyle O({\sqrt {n\cdot (n+m)/(D\cdot B)}}+\operatorname {sort} (n+m))}$

Поиск во внешней памяти в глубину

Алгоритм поиска в глубину исследует граф вдоль каждой ветви как можно глубже, прежде чем выполнять обратную трассировку.

За направленный графики Бухсбаума, Гольдвассера, Венкатасубраманиана и Уэстбрука^[4] предложил алгоритм с ${\displaystyle O((V+E/B)\log _{2}(V/B)+\operatorname {sort} (E))}$ Ввод / вывод.

Этот алгоритм основан на структуре данных, называемой буферизованное дерево репозитория (BRT). В нем хранится набор элементов из упорядоченного юниверса. Предметы обозначены ключом. БТР предлагает две операции:

• вставить (T, x), который добавляет элемент Икс к Т и потребности ${\displaystyle O(1/B\log _{2}(N/B))}$ амортизированные операции ввода-вывода. N - количество предметов, добавленных в BTR.
• экстракт (T, k), который сообщает и удаляет из Т все предметы с ключом k. Это требует ${\displaystyle O(\log _{2}(N/B)+S/B)}$ Ввод / вывод, где S размер набора, возвращаемого извлекать.

Алгоритм имитирует внутренний алгоритм поиска в глубину. Стек S узлов удерживается. Во время итерации для узла v на вершине S столкнуть незаметного соседа на S и повторить. Если нет непосещенных соседей поп v.

Сложность состоит в том, чтобы определить, не посещен ли узел, не выполняя ${\displaystyle \Omega (1)}$ Количество входов / выходов на край. Чтобы сделать это для узла v входящие края (х, v) помещены в BRT D, когда v впервые обнаружен. Далее исходящие ребра (v,Икс) помещаются в приоритетную очередь п(v), с ключом ранга в списке смежности.

Для вершины ты на вершине S все края (ты,Икс) извлекаются из D. Такие ребра существуют, только если Икс был обнаружен с последнего раза ты был на вершине S (или с начала алгоритма, если ты впервые на вершине S). Для каждого ребра (ты,Икс) удаление (Икс) операция выполняется на п(ты). Наконец операция удаления мин на P (u) дает следующий непосещенный узел. Если п(ты) пусто, ты выскакивает из S.

Псевдокод этого алгоритма приведен ниже.

1  процедура BGVW-поиск в глубину (грамм,v): 2 лет S быть стеком, п[] приоритетная очередь для каждого узла и D BRT3 S.толкать(v)4      пока S не пусто5 v = S.top () 6 если v не отмечен: 7 баллов (v) 8 извлеките все края (v, x) из D, ${\displaystyle \forall }$Икс: п[v].Удалить(Икс)9          если ты=п[v] .delete-min () не null10 S.толкать(ты)11         еще12             S.pop () 13 процедура отметка(v) 14 ставим все края (Икс,v) в D15      ${\displaystyle \forall }$ (v,Икс): положить Икс в п[v]

Рекомендации

1. Аггарвал, Алок; Виттер, Джеффри (1988). «Сложность ввода / вывода сортировки и связанных с ней проблем». Коммуникации ACM. 31 (9): 1116–1127. Дои:10.1145/48529.48535.
2. Мунагала, Камешвар; Ранаде, Абхирам (1999). «I / O-сложность графовых алгоритмов». Материалы десятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. SODA '99. Балтимор, Мэриленд, США: Общество промышленной и прикладной математики. С. 687–694.
3. Мельхорн, Курт; Мейер, Ульрих (2002). «Поиск во внешней памяти в ширину с сублинейным вводом-выводом». Алгоритмы - ESA 2002. ESA 2002. Рим, Италия: Springer Berlin Heidelberg. С. 723–735.
4. Buchsbaum, Adam L .; Гольдвассер, Майкл; Венкатасубраманиан, Майкл; Вестбрук, Суреш (2000). «Об обходе графа внешней памяти». Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. SODA '00. Сан-Франциско, Калифорния, США: Общество промышленной и прикладной математики. С. 859–860.