Дробное каскадирование - Fractional cascading - Wikipedia

В Информатика, дробное каскадирование это техника для ускорения последовательности бинарный поиск для того же значения в последовательности связанных структур данных. Первый двоичный поиск в последовательности занимает логарифмическое количество времени, что является стандартным для двоичного поиска, но последующие поиски в последовательности выполняются быстрее. Первоначальная версия дробного каскадирования, представленная в двух статьях Chazelle и Гибас в 1986 г. (Шазель и Гибас 1986a; Шазель и Гибас 1986b ), объединил идею каскадирования, возникшую в поиск диапазона структуры данных Люкер (1978) и Уиллард (1978), с идеей дробной выборки, которая зародилась в Шазель (1983). Позднее авторы представили более сложные формы дробного каскадирования, которые позволяют поддерживать структуру данных по мере изменения данных посредством последовательности дискретных событий вставки и удаления.

Пример

В качестве простого примера дробного каскадирования рассмотрим следующую проблему. В качестве входных данных мы получаем набор k упорядоченные списки L_я чисел, таких что общая длина Σ |L_я| всех списков п, и должен обрабатывать их, чтобы мы могли выполнять двоичный поиск значения запроса q в каждом из k списки. Например, с k = 4 и п = 17,

L₁ = 24, 64, 65, 80, 93

L₂ = 23, 25, 26

L₃ = 13, 44, 62, 66

L₄ = 11, 35, 46, 79, 81

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

Второе решение позволяет выполнять более быстрые запросы за счет большего пространства: мы можем объединить все k списки в один большой список L, и связать с каждым элементом Икс из L список результатов поиска Икс в каждом из меньших списков L_я. Если мы опишем элемент этого объединенного списка как Икс[а,б,c,d] куда Икс - числовое значение и а, б, c, и d позиции (первое число имеет позицию 0) следующего элемента размером не менее Икс в каждом из исходных входных списков (или в позиции после конца списка, если такой элемент не существует), тогда у нас будет

L = 11[0,0,0,0], 13[0,0,0,1], 23[0,0,1,1], 24[0,1,1,1], 25[1,1,1,1], 26[1,2,1,1],

35[1,3,1,1], 44[1,3,1,2], 46[1,3,2,2], 62[1,3,2,3], 64[1,3,3,3], 65[2,3,3,3],

66[3,3,3,3], 79[3,3,4,3], 80[3,3,4,4], 81[4,3,4,4], 93[4,3,4,5]

Это объединенное решение позволяет запрос за время O (журнал п + k): просто найдите q в L а затем сообщить о результатах, хранящихся в элементе Икс найдено с помощью этого поиска. Например, если q = 50, поиск q в L находит элемент 62 [1,3,2,3], из которого мы возвращаем результаты L₁[1] = 64, L₂[3] (значение флага, указывающее, что q прошел конец L₂), L₃[2] = 62 и L₄[3] = 79. Тем не менее, это решение требует высокой сложности пространства: оно использует пространство O (кн) как каждый из п предметы в L должен хранить список k результаты поиска.

Дробное каскадирование позволяет решить ту же проблему поиска с ограничениями по времени и пространству, которые соответствуют лучшим из обоих миров: время запроса O (log п + k), а пространство O (пРешением дробного каскадирования является сохранение новой последовательности списков. M_я. Последний список в этой последовательности, M_k, равно L_k; каждый предыдущий список M_я образуется путем слияния L_я с каждым вторым предметом из M_я+1. С каждым предметом Икс в этом объединенном списке мы храним два числа: позиция, полученная в результате поиска Икс в L_я и позиция, полученная в результате поиска Икс в M_я+1. Для приведенных выше данных это даст нам следующие списки:

M₁ = 24[0, 1], 25[1, 1], 35[1, 3], 64[1, 5], 65[2, 5], 79[3, 5], 80[3, 6], 93[4, 6]

M₂ = 23[0, 1], 25[1, 1], 26[2, 1], 35[3, 1], 62[3, 3], 79[3, 5]

M₃ = 13[0, 1], 35[1, 1], 44[1, 2], 62[2, 3], 66[3, 3], 79[4, 3]

M₄ = 11[0, 0], 35[1, 0], 46[2, 0], 79[3, 0], 81[4, 0]

Предположим, мы хотим выполнить запрос в этой структуре для q = 50. Сначала мы выполняем стандартный двоичный поиск для q в M₁, находя значение 64[1,5]. «1» в 64 [1,5] говорит нам, что поиск q в L₁ должен вернуться L₁[1] = 64. "5" в 64[1,5] говорит нам, что приблизительное местоположение q в M₂ это позиция 5. Точнее, двоичный поиск q в M₂ вернет либо значение 79 [3,5] в позиции 5, либо значение 62 [3,3] на одну позицию ранее. Сравнивая q до 62 и, заметив, что он меньше, мы определяем, что правильный результат поиска M₂ 62 [3,3]. Первая цифра «3» в 62 [3,3] говорит нам, что поиск q в L₂ должен вернуться L₂[3], значение флага, означающее, что q находится за концом списка L₂. Вторая цифра «3» в 62 [3,3] говорит нам, что приблизительное местоположение q в M₃ это позиция 3. Точнее, двоичный поиск q в M₃ вернет либо значение 62 [2,3] в позиции 3, либо значение 44 [1,2] на одну позицию ранее. Сравнение q с меньшим значением 44 показывает нам, что правильный результат поиска в M₃ 62 [2,3]. «2» в 62 [2,3] говорит нам, что поиск q в L₃ должен вернуться L₃[2] = 62, а «3» в 62 [2,3] говорит нам, что результат поиска q в M₄ либо M₄[3] = 79 [3,0] или M₄[2] = 46 [2,0]; сравнение q с 46 показывает, что правильный результат - 79 [3,0] и что результат поиска q в L₄ является L₄[3] = 79. Таким образом, мы нашли q в каждом из наших четырех списков, выполняя двоичный поиск в одном списке M₁ с последующим однократным сравнением в каждом из последовательных списков.

В более общем смысле, для любой структуры данных этого типа мы выполняем запрос, выполняя двоичный поиск для q в M₁, и определяя по полученному значению положение q в L₁. Затем для каждого я > 1, используем известное положение q в M_я найти свое место в M_я+1. Значение, связанное с положением q в M_я указывает на позицию в M_я+1 это либо правильный результат двоичного поиска для q в M_я+1 или находится в одном шаге от правильного результата, поэтому я к я +1 требует только одного сравнения. Таким образом, общее время запроса равно O (log п + k).

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

${\displaystyle |L_{i}|+{\frac {1}{2}}|L_{i+1}|+{\frac {1}{4}}|L_{i+2}|+\cdots +{\frac {1}{2^{j}}}|L_{i+j}|+\cdots ,}$

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

${\displaystyle \sum |M_{i}|=\sum |L_{i}|\left(1+{\frac {1}{2}}+{\frac {1}{4}}+\cdots \right)\leq 2n=O(n),}$

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

Общая проблема

Обычно дробное каскадирование начинается с граф каталога, а ориентированный граф в котором каждый вершина помечен упорядоченным списком. Запрос в этой структуре данных состоит из дорожка на графике и значение запроса q; структура данных должна определять положение q в каждом из упорядоченных списков, связанных с вершинами пути. В приведенном выше простом примере граф каталога сам по себе представляет собой путь, состоящий всего из четырех узлов. Возможно, что более поздние вершины в пути будут определяться динамически как часть запроса, в ответ на результаты, найденные в результате поиска в более ранних частях пути.

Для обработки запросов этого типа для графа, в котором каждая вершина имеет не более d входящие и самое большее d исходящие ребра для некоторой постоянной dсписки, связанные с каждой вершиной, дополняются частью элементов от каждого исходящего соседа вершины; дробь должна быть меньше 1 /d, поэтому общая сумма, на которую расширяются все списки, остается линейной по отношению к размеру ввода. Каждый элемент в каждом расширенном списке сохраняет позицию этого элемента в нерасширенном списке, хранящемся в той же вершине, и в каждом из исходящих соседних списков. В простом примере выше d = 1, и мы увеличили каждый список на 1/2 части соседних элементов.

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

Динамическое дробное каскадирование

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

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

Во-вторых, вставка или удаление может вызвать изменение подмножества списка, связанного с узлом, который передается соседним узлам графа каталога. В динамических настройках больше невозможно выбирать это подмножество в качестве элементов на каждом d-я позиция в списке, для некоторых d, так как это подмножество будет слишком сильно меняться после каждого обновления. Скорее, техника, тесно связанная с B-деревья позволяет выбрать часть данных, которая гарантированно меньше 1 /d, с выбранными элементами, которые гарантированно будут разнесены на постоянное количество позиций в полном списке, и так, что вставка или удаление в расширенный список, связанный с узлом, заставляет изменения распространяться на другие узлы для части операций, которые менее 1 /d. Таким образом, распределение данных между узлами удовлетворяет свойствам, необходимым для быстрого алгоритма запроса, гарантируя при этом постоянство среднего числа операций двоичного дерева поиска на одну вставку или удаление данных.

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

• Отображение элементов в расширенном списке узла на небольшие целые числа, так что порядок позиций в расширенном списке эквивалентен порядку сравнения целых чисел, и обратное отображение этих целых чисел обратно в элементы списка. Техника Диц (1982) позволяет эффективно поддерживать эту нумерацию.
• Целочисленная структура данных поиска, такая как дерево ван Эмде Боас для чисел, связанных с входным списком узла. С помощью этой структуры и преобразования элементов в целые числа можно эффективно найти для каждого элемента Икс расширенного списка, элемент, который будет найден при поиске Икс в списке ввода.
• Для каждого соседнего узла в графе каталога аналогичная целочисленная структура данных поиска для чисел, связанных с подмножеством данных, распространяемых из соседнего узла. С помощью этой структуры и преобразования элементов в целые числа можно эффективно найти для каждого элемента Икс расширенного списка, позиция в пределах постоянного числа шагов расположения Икс в расширенном списке, связанном с соседним узлом.

Эти структуры данных позволяют выполнять динамическое дробное каскадирование за время O (logп) на вставку или удаление, а последовательность k бинарный поиск по пути длины k в графе каталога, которое должно быть выполнено за время O (logп + k журнал журналп).

Приложения

Выпуклые слои набора точек, часть эффективной дробно-каскадной структуры данных для отчетов о диапазоне полуплоскостей.

Типичные применения дробного каскадирования включают: поиск по диапазону структуры данных в вычислительная геометрия. Например, рассмотрим проблему полуплоскость отчет о диапазоне: то есть пересечение фиксированного набора п указывает с запросом полуплоскость и перечислить все точки пересечения. Проблема состоит в том, чтобы структурировать точки таким образом, чтобы на запрос этого типа можно было эффективно ответить с точки зрения размера пересечения. час. Одной из структур, которые можно использовать для этой цели, является выпуклые слои набора входных точек, семейство вложенных выпуклые многоугольники состоящий из выпуклый корпус множества точек и рекурсивно построенных выпуклых слоев остальных точек. Внутри одного слоя точки внутри полуплоскости запроса могут быть найдены путем выполнения двоичного поиска наклона граничной линии полуплоскости среди отсортированной последовательности наклонов выпуклых краев многоугольника, ведущей к вершине многоугольника, которая находится внутри половины запроса -плоскости и дальше всего от ее границы, а затем последовательный поиск вдоль ребер многоугольника, чтобы найти все остальные вершины внутри полуплоскости запроса. Проблема сообщения о диапазоне в целом в полуплоскости может быть решена путем повторения этой процедуры поиска, начиная с самого внешнего уровня и продолжаясь внутрь до достижения уровня, который не пересекается с полупространством запроса. Дробное каскадирование ускоряет последовательные бинарные поиски среди последовательностей наклонов краев многоугольника в каждом слое, что приводит к структуре данных для этой проблемы с пространством O (п) и время запроса O (журналп + час). Структура данных может быть построена за время O (п бревноп) по алгоритму Шазель (1985). Как и в нашем примере, это приложение включает двоичный поиск в линейной последовательности списков (вложенная последовательность выпуклых слоев), поэтому граф каталога представляет собой просто путь.

Другое применение дробного каскадирования в геометрических структурах данных касается точка расположения в монотонном подразделении, то есть в таком разбиении плоскости на многоугольники, что любая вертикальная линия пересекает любой многоугольник не более чем в двух точках. В качестве Эдельсбруннер, Гибас и Стольфи (1986) Как было показано, эта проблема может быть решена путем нахождения последовательности многоугольных путей, которые проходят слева направо через подразделение, и двоичного поиска самого нижнего из этих путей, который находится выше точки запроса. Проверка того, находится ли точка запроса выше или ниже одного из путей, сама по себе может быть решена как проблема двоичного поиска, поиск координаты x точек среди координат x вершин пути, чтобы определить, какое ребро пути может быть выше или ниже точка запроса. Таким образом, каждый запрос местоположения точки может быть решен как внешний уровень двоичного поиска среди путей, каждый шаг которого сам выполняет двоичный поиск среди x координат вершин. Дробное каскадирование можно использовать для ускорения внутреннего двоичного поиска, уменьшая общее время запроса до O (logп) с использованием структуры данных с пробелом O (п). В этом приложении граф каталога представляет собой дерево, представляющее возможные последовательности поиска внешнего двоичного поиска.

Помимо вычислительной геометрии, Лакшман и Стилиадис (1998) и Буддхикот, Сури и Вальдфогель (1999) применять дробное каскадирование при проектировании структур данных для быстрого фильтрация пакетов в интернет-маршрутизаторы. Gao et al. (2004) использовать дробное каскадирование в качестве модели для распределения и поиска данных в сенсорные сети.

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

• Аталлах, Михаил Дж.; Блэнтон, Марина; Гудрич, Майкл Т.; Полу, Станислав (2007), «Чувствительное к несовпадениям динамическое дробное каскадирование, поиск доминирующих максимумов и двухмерных ближайших соседей в любой метрике Минковского» (PDF), Алгоритмы и структуры данных, 10-й международный семинар, WADS 2007, Конспект лекций по информатике, 4619, Springer-Verlag, стр. 114–126, arXiv:0904.4670, Дои:10.1007/978-3-540-73951-7_11, ISBN  978-3-540-73948-7, S2CID  2590335.
• Buddhikot, Milind M .; Сури, Субхаш; Вальдфогель, Марсель (1999), "Методы декомпозиции пространства для быстрой коммутации уровня 4" (PDF), Труды шестого международного семинара IFIP TC6 WG6.1 и WG6.4 / IEEE ComSoc по гигабитным сетям VI по протоколам для высокоскоростных сетей., стр. 25–42, архивировано с оригинал (PDF) на 2004-10-20.
• Шазель, Бернар (1983), «Фильтрация поиска: новый подход к ответам на запросы» (PDF), Proc. 24 IEEE FOCS.
• Шазель, Бернар (1985), «О выпуклых слоях точечного множества» (PDF), IEEE Transactions по теории информации, 31 (4): 509–517, CiteSeerX  10.1.1.113.8709, Дои:10.1109 / TIT.1985.1057060.
• Шазель, Бернар; Гибас, Леонидас Дж. (1986), «Дробное каскадирование: I. Метод структурирования данных» (PDF), Алгоритмика, 1 (1–4): 133–162, Дои:10.1007 / BF01840440, S2CID  12745042.
• Шазель, Бернар; Гибас, Леонидас Дж. (1986), «Дробное каскадирование: II. Приложения» (PDF), Алгоритмика, 1 (1–4): 163–191, Дои:10.1007 / BF01840441, S2CID  11232235.
• Шазель, Бернар; Лю, Дин (2004), «Нижние границы для поиска пересечений и дробного каскадирования в более высоком измерении» (PDF), Журнал компьютерных и системных наук, 68 (2): 269–284, CiteSeerX  10.1.1.298.7772, Дои:10.1016 / j.jcss.2003.07.003.
• Дитц, Ф. Пол (1982), «Поддержание порядка в связном списке», 14-й ACM Symp. Теория вычислений, стр. 122–127, Дои:10.1145/800070.802184, ISBN  978-0-89791-070-5, S2CID  24008786.
• Эдельсбруннер, Х.; Guibas, L.J .; Столфи, Дж. (1986), «Оптимальное расположение точки на монотонном участке» (PDF), SIAM Журнал по вычислениям, 15 (1): 317–340, Дои:10.1137/0215023.
• Gao, J .; Guibas, L.J .; Hershberger, J .; Чжан, Л. (2004), «Дробно каскадная информация в сенсорной сети» (PDF), Proc. 3-го Международного симпозиума по обработке информации в сенсорных сетях (IPSN'04), стр. 311–319, Дои:10.1145/984622.984668, ISBN  978-1-58113-846-7, S2CID  1033287.
• JaJa, Joseph F .; Ши, Цинминь (2003), Быстрое дробное каскадирование и его приложения (PDF), Univ. Мэриленда, Тех. Отчет UMIACS-TR-2003-71.
• Lakshman, T. V .; Стилиадис, Д. (1998), "Высокоскоростная пересылка пакетов на основе политик с использованием эффективного многомерного согласования диапазонов", Труды конференции ACM SIGCOMM '98 по приложениям, технологиям, архитектурам и протоколам для компьютерной связи, стр. 203–214, CiteSeerX  10.1.1.39.697, Дои:10.1145/285237.285283, ISBN  978-1-58113-003-4, S2CID  15363397.
• Люкер, Джордж С. (1978), "Структура данных для запросов ортогонального диапазона", Proc. 19-й симпозиум Основы информатики, IEEE, стр. 28–34, Дои:10.1109 / SFCS.1978.1, S2CID  14970942.
• Мельхорн, Курт; Нахер, Стефан (1990), «Динамическое дробное каскадирование», Алгоритмика, 5 (1): 215–241, Дои:10.1007 / BF01840386, S2CID  7721690.
• Сен, С. Д. (1995), "Повторное посещение дробного каскадирования", Журнал алгоритмов, 19 (2): 161–172, Дои:10.1006 / jagm.1995.1032.
• Уиллард, Д. Э. (1978), Алгоритмы поиска в базе данных, ориентированные на предикаты, Кандидат наук. докторская диссертация, Гарвардский университет.
• Яп, Чи; Чжу, Юньюэ (2001), «Еще один взгляд на дробное каскадирование: B-графы с приложением к местоположению точки», Труды 13-й Канадской конференции по вычислительной геометрии (CCCG'01), стр. 173–176.