Распределенный поиск по дереву

Алгоритм поиска по распределенному дереву ( DTS ) — это класс алгоритмов для эффективного и распределенного поиска значений. Их цель — перебирать дерево, параллельно работая над несколькими ветвями и объединяя результаты каждой ветви в одно общее решение, чтобы минимизировать время, затрачиваемое на поиск значения в древовидной структуре данных.

Оригинальная статья была написана в 1988 году Крисом Фергюсоном и Ричардом Корфом с факультета компьютерных наук Калифорнийского университета. Для разработки этого алгоритма более широкого диапазона они использовали несколько других шахматных ИИ.

Обзор

Алгоритм поиска по распределенному дереву (также известный как алгоритм Корфа – Фергюсона) был создан для решения следующей задачи: «Дано дерево с неравномерным коэффициентом ветвления и глубиной, ищите его параллельно с произвольным количеством процессоров как можно быстрее. "

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

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

Как только процесс завершает поиск, он рекурсивно отправляет и объединяет результирующий сигнал своему родительскому процессу до тех пор, пока все различные подответы не будут объединены и вся проблема не будет решена. ^[1]

Приложения

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

Одним из основных примеров повседневного использования DTS является сетевая маршрутизация. Интернет можно рассматривать как дерево IP-адресов , а аналогией протокола маршрутизации может служить то, как почтовые отделения работают в реальном мире. Поскольку в настоящее время существует более 4,3 миллиарда IP-адресов, общество во многом зависит от времени, которое требуется данным, чтобы добраться до пункта назначения. Таким образом, IP-маршрутизация делит работу на несколько подблоков, каждый из которых имеет разные масштабы вычислительных возможностей и использует результаты друг друга для очень эффективного поиска маршрута. Это пример DTS, от которого страдают более 43% населения мира по причинам, начиная от развлечений и заканчивая национальной безопасностью. ^[2]

Альтернативы

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

Одним из наиболее противоречивых примеров является обработка больших данных. В таких приложениях, как Google Search Engine, Facebook, YouTube, поиск необходимо оптимизировать, чтобы время ожидания оставалось в пределах разумного окна. Этого можно достичь за счет простого использования DTS, но вместо этого используются и другие алгоритмы (например, хеширование данных в базах данных SQL ) или совместно (алгоритм Facebook Haystack группирует параллельный поиск по дереву, хеширование данных и упорядочивание памяти). сортировка). ^[3]

Одним из наиболее важных ограничений DTS является тот факт, что в качестве входных данных требуется дерево. Деревья — это подэкземпляр структуры данных, известной как графики, что означает, что каждый график можно преобразовать в дерево. Хотя в настоящее время не существует лучшего способа поиска по деревьям, чем алгоритм Корфа-Фергюсона, каждая задача имеет свои особенности, и в большинстве случаев будут существовать более эффективные структуры данных для представления проблемы и ее решения, чем поиск по дереву. Таким образом, существуют экземпляры древовидных структур с циклами, которые не могут быть быстрее, чем поиск по графу в той же структуре с той же вычислительной мощностью.

Споры

Вокруг алгоритма DTS Корфа-Фергюсона мало споров, поскольку он признан очень полным, но простым. Он очень часто используется студентами в качестве трамплина для изучения основ и ключевых концепций распределенного решения проблем.

Самым важным вызовом этой алгоритмической концепции стала статья Крёлля Б. «Сбалансированные распределенные деревья поиска не существуют», в которой критикуется не достоверность или текущая эффективность алгоритма, а скорее тот факт, что сам DTS, независимо от того, сколько в него внесены улучшения (например, предварительная балансировка входного дерева), он никогда не сможет достичь оптимального времени разрешения. ^[4] Это открывает новую точку зрения: не слишком ли много ресурсов используется для завершения DTS, что блокирует исследование и разработку новых алгоритмов с более высоким потенциалом эффективности? Еще одним ограничением DTS является тот факт, что независимо от того, насколько эффективно разделение, координация и объединение решений, оно всегда будет ограничено количеством материалов или процессоров и их вычислительной мощностью.

См. также

Колбрук А., Брюэр Э., Делларокас К., Вейл В., «Алгоритмы деревьев поиска в архитектурах передачи сообщений» (1996)
Колбрук А., Смайт К., Эффективные реализации деревьев поиска в параллельных архитектурах распределенной памяти (1990)
Байер Р., МакКрайт Э., Организация и обслуживание больших упорядоченных индексов. Акта Информатика 1 (1972)
Комер Д., Вездесущее B-дерево (1979)

Ссылки

^ КОРФ Ричард Э., ФЕРГЮСОН Крис (1988). «Распределенный поиск по дереву и его применение для альфа-бета-обрезки» (PDF) . АААИ . Калифорнийский университет, Лос-Анджелес. Архивировано из оригинала (PDF) 31 мая 2016 г.
^ «Что такое IP-маршрутизация?» . МетаСвитч . МетаСвитч Сети. 2016.
^ Вайгель, Питер (30 апреля 2009 г.). «Иголка в стоге сена: эффективное хранение миллиардов фотографий» . Фейсбук . Фейсбук (компания).
^ Крёлль, Бриджит; Видмайер, Питер (16 августа 1995 г.). Акл, Селим Г.; Дене, Франк; Зак, Йорг-Рюдигер; Санторо, Никола (ред.). Сбалансированных распределенных деревьев поиска не существует . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 50–61. дои : 10.1007/3-540-60220-8_50 . hdl : 20.500.11850/68782 . ISBN 9783540602200 .

[1] КОРФ Ричард Э., ФЕРГЮСОН Крис (1988). «Распределенный поиск по дереву и его применение для альфа-бета-обрезки» (PDF) . АААИ . Калифорнийский университет, Лос-Анджелес. Архивировано из оригинала (PDF) 31 мая 2016 г.

[2] «Что такое IP-маршрутизация?» . МетаСвитч . МетаСвитч Сети. 2016.

[3] Вайгель, Питер (30 апреля 2009 г.). «Иголка в стоге сена: эффективное хранение миллиардов фотографий» . Фейсбук . Фейсбук (компания).

[4] Крёлль, Бриджит; Видмайер, Питер (16 августа 1995 г.). Акл, Селим Г.; Дене, Франк; Зак, Йорг-Рюдигер; Санторо, Никола (ред.). Сбалансированных распределенных деревьев поиска не существует . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 50–61. дои : 10.1007/3-540-60220-8_50 . hdl : 20.500.11850/68782 . ISBN 9783540602200 .

[1]

[2]

[3]

[4]