Поиск предков

Ключевые слова и синонимы

Задача о поиске предков, задача о поиске потомков, просмотр информации об IP-адресе

Постановка задачи

Рассмотрим упорядоченную совокупность U и множество T [math]\displaystyle{ \subset }[/math] U, |T| = n. Целью является предварительная обработка T таким образом, чтобы можно было эффективно отвечать на следующий запрос: пусть задан элемент [math]\displaystyle{ x \in U }[/math], требуется найти предка [math]\displaystyle{ x }[/math], т. е. [math]\displaystyle{ max \{ y \in T | y \lt x \} }[/math]. Также можно рассмотреть динамическую задачу, когда элементы вставляются в T и удаляются из него. Обозначим за [math]\displaystyle{ t_q }[/math] время выполнения запроса, а за [math]\displaystyle{ t_u }[/math] – время обновления.

Это фундаментальная задача поиска, которая очень широко применяется во множестве областей. Далее в качестве примеров будут рассматриваться просмотр информации об IP-адресе (пересылка пакетов в сети Интернет), запросы в ортогональном диапазоне и неизменяемые структуры данных.

Эта задача рассматривалась во многих вычислительных моделях. Фактически большинство ниже приводимых моделей изначально были определены для изучения задачи о поиске предков.

Модель сравнения: задача может быть решена с помощью бинарного поиска за [math]\displaystyle{ \Theta(lg \; n) }[/math] сравнений. Существует множество работ по адаптивным границам, которые могут быть сублогарифмическими. Такие границы могут зависеть от расстояния между пальцами, рабочего множества, энтропии и т. д.

Бинарные деревья поиска: поиск предков является одним из фундаментальных мотивов для бинарных деревьев поиска. В рамках этой ограничивающей модели можно рассчитывать на оптимальный (конкурентный) алгоритм. Попытки достичь этого описаны в работе O(log log n)-конкурентные бинарные деревья поиска (2004; Demaine, Harmon, Iacono, P˘atra¸scu).

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

Традиционно принято считать, что совокупность имеет вид [math]\displaystyle{ U = \{ 1, ..., 2^{\ell} \} }[/math], т. е. мы имеем дело с [math]\displaystyle{ \ell }[/math]-битными целыми числами. Представление с плавающей точкой было разработано таким образом, что порядок сохраняется, когда значения интерпретируются как целые числа, поэтому любой алгоритм будет работать и для [math]\displaystyle{ \ell }[/math]-битных чисел с плавающей точкой.

Стандартное трансдихотомическое предположение состоит в том, что [math]\displaystyle{ b = \ell }[/math], так что входное целое число представляется в виде слова. Из этого следует [math]\displaystyle{ b \ge lg \; n }[/math].

Модель клеточного зонда: это неоднородная модель, более сильная, чем пословная RAM-машина, в которой операции являются произвольными функциями от слов памяти (ячеек), которые уже были прозондированы. Таким образом, [math]\displaystyle{ t_q }[/math] подсчитывает только количество зондирований ячеек. Это идеальная модель с точки зрения нижних границ, поскольку она не зависит от операций, реализуемых конкретным компьютером.

Коммуникативные игры: предположим, что у Алисы есть запрос x, а у Боба – множество T. Они пытаются найти предка [math]\displaystyle{ x }[/math] с помощью [math]\displaystyle{ \tau }[/math] раундов коммуникации, где в каждом раунде Алиса посылает [math]\displaystyle{ m_A }[/math] бит, а Боб отвечает с использованием [math]\displaystyle{ m_B }[/math] бит.

Этот подход может имитировать модель клеточного зонда, когда [math]\displaystyle{ m_B = b }[/math], а [math]\displaystyle{ m_A }[/math] – логарифм от объема памяти. Тогда [math]\displaystyle{ \tau \le t_q }[/math], и можно использовать коммуникационную сложность для получения нижних границ клеточного зонда.

Внешняя память: единицей доступа является страница, содержащая B слов по [math]\displaystyle{ \ell }[/math] бит каждое. B-деревья решают задачу со временем запроса и обновления [math]\displaystyle{ O(log_B \; n) }[/math]; этого также можно достичь, не обращая внимания на значение B (см. B-деревья без явного задания параметров кэша). Модель клеточного зонда с [math]\displaystyle{ b = B \cdot \ell }[/math] сильнее данной модели.

[math]\displaystyle{ AC^0 }[/math]-RAM: это вариант пословной RAM-машины, в котором допустимыми операциями являются функции, имеющие постоянную глубину, с неограниченными схемами объединения по входу. Это исключает умножение из стандартного набора операций.

RAMBO: это вариант пословной RAM-машины с нестандартной памятью, в котором биты в словах памяти могут перекрываться. В статическом случае это по сути эквивалентно обычной RAM-машине; в динамическом случае обновление может происходить быстрее из-за перекрытия слов [5].

Логарифмическая граница для сравнительного поиска в наихудшем случае не особенно информативна в ситуациях, когда важна эффективность. На практике при работе с огромными массивами данных стандартным подходом является использование B-деревьев и их вариантов. Решения, основанные на изобретательном использовании оперативной памяти, подходят для случаев, когда набор данных не особенно велик, но быстрое время выполнения запроса имеет решающее значение – как, например, в программных решениях для поиска информации об IP-адресах [7].

Основные результаты

Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили соответствующие верхние и нижние границы для статической задачи на моделях пословной RAM-машины, клеточного зонда, внешней памяти и коммуникативной игры.

Пусть S – количество слов доступной памяти. (В случае внешней памяти это эквивалентно S/B страниц). Определим [math]\displaystyle{ a = lg \; S \cdot \ell / n }[/math]. Также определим [math]\displaystyle{ lg \; x = \left \lceil log_2(x + 2) \right \rceil }[/math] таким образом, что [math]\displaystyle{ lg \; x \ge 1 }[/math], даже если [math]\displaystyle{ x \in [0, 1] }[/math]. Тогда оптимальное время поиска составляет, с точностью до константных коэффициентов:

(1) [math]\displaystyle{ min \begin{cases} log_b \; n = \Theta(min \{ log_B \; n, log_{\ell} \; n \}) \\ \\ lg \frac{\ell - lg \; n}{a} \\ \\ \frac{lg \frac{\ell}{a}}{lg(\frac{a}{lg \; n} \cdot lg \frac{\ell}{a})} \\ \\ \frac{lg \frac{\ell}{a}}{lg(\frac{lg \frac{\ell}{a}}{lg \frac{lg \; n}{a}})} \end{cases} }[/math]

Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства S структура данных может быть построена за время O(S) с помощью рандомизированного алгоритма, начиная с множества T, заданного в отсортированном порядке. Обновления выполняются за ожидаемое время [math]\displaystyle{ t_q + O(S/n) }[/math]. Таким образом, помимо нахождения элемента за один запрос о предке, обновления изменяют минимальную часть структуры данных.

Нижние границы справедливы для мощной модели клеточного зонда и выполняются даже для рандомизированных алгоритмов. Когда [math]\displaystyle{ S \ge n^{1 + \varepsilon} }[/math], оптимальный компромисс для коммуникативных игр совпадает с (1). Заметим, что случай [math]\displaystyle{ S = n^{1 + o(1)} }[/math] практически устраняется при сведении к коммуникационной сложности, поскольку сообщения Алисы зависят только от lg S. Таким образом, нет асимптотической разницы между [math]\displaystyle{ S = O(n) }[/math] и, скажем, [math]\displaystyle{ S = O(n^2) }[/math].

Верхние границы

Следующие алгоритмические техники дают оптимальный результат:

• B-деревья обеспечивают время запроса [math]\displaystyle{ O(log_B \; n) }[/math] при линейном объеме памяти.

• Деревья слияния, предложенные Фредманом и Уиллардом [10], дают время запроса [math]\displaystyle{ O(log_b \; n) }[/math]. В основе этого результата лежит узел слияния – структура, которая может выполнять поиск среди [math]\displaystyle{ b^{\varepsilon} }[/math] значений за постоянное время. Это достигается путем признания того, что только несколько бит каждого значения являются важными, и упаковки соответствующей информации обо всех значениях в одно слово.

• Поиск ван Эмде Боаса [18] способен решить задачу за время [math]\displaystyle{ O(lg \; \ell) }[/math] путем бинарного поиска длины самого длинного общего префикса между запросом и значением в T. Начиная поиск с просмотра таблицы на основе первых lg n бит и заканчивая, когда достаточно места для хранения всех ответов, можно сократить время запроса до [math]\displaystyle{ O(lg((\ell - lg \; n)/a)) }[/math].

• Методика Бима и Фич [4] позволяет выполнять многоходовый поиск самого длинного общего префикса, поддерживая точный баланс между [math]\displaystyle{ \ell }[/math] и n. Это актуально, когда объем памяти составляет не менее [math]\displaystyle{ n^{1 + \varepsilon} }[/math], и дает третью ветвь (1). Петрашку и Торуп [15] показывают, как можно реализовать родственные идеи при меньшем объеме памяти, что дает последнюю ветвь (1).

Заметим, что внешняя память участвует в достижении оптимального компромисса только за счет члена [math]\displaystyle{ O(log_B \; n) }[/math], приходящегося на B-деревья. Таким образом, оптимальным является либо использование стандартных B-деревьев, основанных на сравнении, либо использование наилучшей стратегии пословной RAM-машины, полностью обходящейся без внешней памяти.

Нижние границы

Все нижние границы до выхода работы [15] были показаны на модели коммуникативной игры. Айтай [1] первым представил суперконстантную нижнюю границу. Его результаты, с поправкой Милтерсена [12], показывают, что для полиномиального объема памяти существует n как функция от [math]\displaystyle{ \ell }[/math], позволяющая получить время запроса [math]\displaystyle{ \Omega(\sqrt{lg \; \ell}) }[/math], и аналогично существует [math]\displaystyle{ \ell }[/math] как функция от n, позволяющая получить сложность запроса [math]\displaystyle{ \Omega(\sqrt[3]{lg \; n}) }[/math].

Милтерсен и другие [13] пересмотрели доказательство Айтая, распространив его на рандомизированные алгоритмы. Что более важно, они отразили суть доказательства в лемме о независимом исключении раунда, которая служит важным инструментом при доказательстве нижних границ в асимметричной коммуникации.

Бим и Фич [4] улучшили нижние границы Айтая до [math]\displaystyle{ \Omega(lg \; \ell / lg \; lg \; \ell) }[/math] и [math]\displaystyle{ \Omega(\sqrt{lg \; n / lg \; lg \; n}) }[/math], соответственно. Сен и Венкатеш [17] позже представили улучшенную лемму об исключении раунда, которая обосновывает эти нижние границы в том числе и для рандомизированных алгоритмов.

Наконец, используя лемму о сжатии сообщений из работы [6] (являющемся альтернативой исключению раунда), Петрашку и Торуп [15] предложили оптимальный компромисс для коммуникативных игр. Он также является оптимальной нижней границей в других моделях, в которых [math]\displaystyle{ S \ge n^{1 + \varepsilon} }[/math], но не подходит для меньшего объема памяти.

Что более важно, в [15] были разработаны первые инструменты для доказательства нижних границ, превышающих коммуникационную сложность, для случаев [math]\displaystyle{ S = n^{1 + o(1)} }[/math]. Здесь впервые было проведено разделение между структурой данных полиномиального размера и структурой размера, близкого к линейному. Его принципиально невозможно получить при помощи нижней границы для прямых коммуникаций, поскольку редукция к коммуникативным играм зависит только от lg S.

Полный результат Петрашку и Торупа [15] представляет собой компромисс (1). Первоначально он был показан только для детерминированных алгоритмов запросов, но со временем был распространен и на нижнюю границу рандомизированного алгоритма [16]. Среди удивительных последствий этого результата было то, что классический поиск ван Эмде Боаса является оптимальным для почти линейного объема памяти (и, следовательно, для динамических структур данных), тогда как при наличии квадратичного объема памяти он может уступать технике Бима и Фич.

С технической точки зрения идея работы [15] заключается в одновременном анализе нескольких запросов. Затем рассматривается коммуникативная игра, включающая все запросы, и доказывается версия леммы об исключении раунда с прямой суммой. Возможно, доказательство в данном случае даже проще, чем у обычной леммы об исключении раунда. Это достигается за счет рассмотрения более сильной модели индуктивного анализа, в которой алгоритму разрешается отклонить большую часть запросов, прежде чем приступить к зондированию.

Группировка

Развитая рекурсивная структура задачи может быть использована не только для выполнения быстрых запросов, но и для оптимизации памяти и времени на выполнение обновлений – конечно, в пределах (1). Идея заключается в том, чтобы поместить диапазоны последовательных значений в группы, или блоки, и включить одного представителя каждого блока в структуру предков. После выполнения запроса к структуре предков (теперь имеющей меньшее количество элементов) поиск нужно производить только в соответствующем блоке.

Поскольку блоки размером [math]\displaystyle{ w^{(O(1)} }[/math] могут обрабатываться деревьями слияния за константное время, из этого следует, что коэффициенты w объема памяти не имеют значения. Более экстремальное применение этой идеи дают экспоненциальные деревья [3]. Здесь блоки имеют размер [math]\displaystyle{ \Theta(n^{1 - \gamma}) }[/math], где [math]\displaystyle{ \gamma }[/math] – достаточно небольшая константа. Блоки обрабатываются рекурсивно таким же образом, что дает в итоге O(lg lg n) уровней. Если начальное время запроса не меньше [math]\displaystyle{ t_q \ge lg^{\varepsilon} \; n }[/math], то время запроса на каждом уровне уменьшается в геометрической прогрессии, так что общее время растет только на постоянный коэффициент. Однако при соответствующем выборе [math]\displaystyle{ \gamma }[/math] любое полиномиальное требование к памяти сводится к линейному. Кроме того, экспоненциальное дерево может быть обновлено за время [math]\displaystyle{ O(t_q }[/math]), даже если исходная структура данных была статической.

Применение

Возможно, наиболее важным применением задачи поиска предков является просмотр информации об IP-адресах. Эту задачу решают маршрутизаторы для каждого пакета в Интернете, когда выбирают, в какую подсеть направить пакет. Таким образом, это, вероятно, самая часто выполняемая алгоритмическая задача в мире. Формально это запрос о поиске в интервале, который эквивалентен поиску предка в статическом случае [9]. Поскольку при решении этой задачи эффективность исключительно важна, необходимо отметить, что самые быстро внедряемые программные решения [7] используют стратегии целочисленного поиска (не основанные на сравнении), как и предсказывают теоретические результаты.

Кроме того, поиск предков широко используется в структурах данных при редукции задач к пространству рангов. Пусть имеется множество T. Часто требуется переразметить его в более простое {1, ..., n} «пространство рангов», сохранив при этом отношения порядка. Если новые значения представляются динамически, возникает необходимость в запросе на поиск предка. Вот несколько наглядных примеров:

• При запросах в ортогональном диапазоне поддерживается набор точек в [math]\displaystyle{ U^d }[/math] и выполняются запросы на точки в некотором прямоугольнике [math]\displaystyle{ [a_1, b_1] \times \cdot \cdot \cdot \times [a_d, b_d] }[/math]. Хотя границы обычно растут экспоненциально с увеличением размерности, зависимость от совокупности можно факторизовать. Во время запроса сначала выполняются 2d запросов предков, преобразующих совокупность в [math]\displaystyle{ \{1, ..., n \}^d }[/math].

• Чтобы сделать структуры данных с указателями постоянными [8], исходящая ссылка заменяется вектором указателей, каждый из которых действителен в течение некоторого периода времени. Решение о том, по какой ссылке идти (учитывая время запроса), представляет собой задачу поиска предка.

Наконец, любопытно отметить, что нижние границы в задаче поиска предка оказываются применимы, путем редукции, ко всем описанным выше приложениям. Чтобы сделать такие редукции возможными, нижние границы на самом деле показаны для более слабой задачи поиска цвета предка. В этой задаче значения множества T окрашены в красный или синий цвет, и запрос должен найти только цвет предшественника.

Открытые вопросы

Подход к реализации деревьев слияния с инструкциями [math]\displaystyle{ AC^0 }[/math] известен [2], но для других стратегий запросов это не так. Каков наилучший компромисс между запросами, достижимый для RAM-машины [math]\displaystyle{ AC^0 }[/math]? В частности, может ли поиск ван Эмде Боаса быть реализован с помощью инструкций [math]\displaystyle{ AC^0 }[/math]?

Можно ли сделать время обновления детерминированным при решении динамической задачи? В частности, можно ли реализовать поиск ван Эмде Боаса с быстрым детерминированным обновлением? Это очень интересная задача, находящая применение в детерминированных словарях [14]. Кроме того, можно ли детерминированным образом обновлять узлы слияния за константное время? Атомарные кучи [11] достигают этого результата при поиске только среди [math]\displaystyle{ (lg \; n)^{\varepsilon} }[/math] элементов, а не [math]\displaystyle{ b^{\varepsilon} }[/math].

Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить [math]\displaystyle{ t_u = o(t_q) }[/math], сохранив при этом эффективное время запроса?

См. также

• B-деревья без явного задания параметров кэша
• O(log log n)-конкурентное бинарное дерево поиска

Литература

1. Ajtai, M.: A lower bound for finding predecessors in Yao's cell probe model. Combinatorica 8(3), 235-247 (1988)

2. Andersson, A., Miltersen, P.B., Thorup, M.: Fusion trees can be implemented with AC0 instructions only. Theor. Comput. Sci. 215(1-2),337-344(1999)

3. Andersson, A., Thorup, M.: Dynamic ordered sets with exponential search trees. CoRR cs.DS/0210006. See also FOCS'96, STOC'00, 2002

4. Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comput. Syst. Sci. 65(1), 38-72 (2002). See also STOC'99

5. Brodnik, A., Carlsson, S., Fredman, M.L., Karlsson, J., Munro, J.I.: Worst case constant time priority queue. J. Syst. Softw. 78(3), 249-256 (2005). See also SODA'01

6. Chakrabarti, A., Regev, O.: An optimal randomised cell probe lower bound for approximate nearest neighbour searching. In: Proc. 45th IEEE Symposium on Foundations of Computer Science (FOCS), 2004, pp. 473-482

7. Degermark, M., Brodnik, A., Carlsson, S., Pink, S.: Small forward ing tables for fast routing lookups. In: Proc. ACM SIGCOMM, 1997, pp. 3-14

8. Driscoll, J.R., Sarnak, N., Sleator, D.D., Tarjan, R.E.: Making data structu res persi stent. J. Com put. Syst. Sci. 38( 1), 86-124 (1989). See also STOC'86

9. Feldmann, A., Muthukrishnan, S.: Tradeoffs for packet classification. In: Proc. IEEE INFOCOM, 2000, pp. 1193-1202

10. Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424-436 (1993). See also STOC'90

11. Fredman, M.L., Willard, D.E.:Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48(3), 533-551 (1994). See also FOCS'90

12. Miltersen, P.B.: Lower bounds for Union-Split-Find related problems on random access machines. In: 26th ACM Symposium on Theory of Computing (STOC), 1994, pp. 625-634

13. Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. J. Comput. Syst. Sci. 57(1), 37-49 (1998). See also STOC'95

14. Pagh, R.: A trade-off for worst-case efficient dictionaries. Nord. J. Comput. 7,151-163 (2000). See also SWAT'00

15. Patrajcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. 38th ACM Symposium on Theory of Computing (STOC), 2006, pp. 232-240

16. Patrajcu, M.,Thorup, M.: Randomization does not help search ing predecessors. In: Proc. 18th ACM/SIAM Symposium on Discrete Algorithms (SODA), 2007

17. Sen, P., Venkatesh, S.: Lower bounds for predecessor search ing in the cell probe model. arXiv:cs.CC/0309033. See also ICALP'01,CCC'03, 2003

18. van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Math. Syst. Theor. 10, 99-127 (1977). Announced by van Emde Boas alone at FOCS'75