Понимание Fusion Trees?

Question

Я наткнулся на страницу Википедии для них:

Fusion tree

И я прочитал PDF-файлы с примечаниями к классу, связанные внизу, но они разбираются в самой структуре данных и подробно рассказывают о sketch(x) функция. Я думаю, что часть моей путаницы заключается в том, что статьи пытаются быть очень общими, и я хотел бы представить конкретный пример.

Подходит ли эта структура данных для хранения данных на основе произвольных 32- или 64-битных целочисленных ключей? Чем он отличается от B-дерева? Есть один раздел, который говорит, что это в основном B-дерево с фактором ветвления B = (lg n)^(1/5), Для полностью заполненного дерева с 32-битными ключами B будет 2. Это просто станет бинарным деревом? Предназначена ли эта структура данных для использования гораздо более длинных битовых строк в качестве ключей?

Мой Google не нашел ничего страшного, но я бы приветствовал любые хорошие ссылки на эту тему. Это на самом деле просто мимолетное любопытство, поэтому я не был готов платить за PDF-файлы на portal.acm.org еще.

Answer 1

Я прочитал (просто быстрый проход) оригинальную статью и кажется интересным. Он также отвечает на большинство ваших вопросов на первой странице.

Вы можете скачать статью здесь

НТН!

Answer 2

Вы задали здесь несколько замечательных вопросов:

1. Является ли дерево слияния хорошей структурой данных для хранения 32-битных или 64-битных чисел? Или он предназначен для хранения более длинных битовых строк?
2. Чем дерево слияния отличается от B-дерева?
3. Дерево слияния выбирает b = w^1/5, где w - размер машинного слова. Означает ли это, что b = 2 на 32-битной машине, и делает ли это просто двоичное дерево?
4. Почему так много разговоров о дереве слияния сосредоточено на создании эскизов?
5. Доступна ли визуализация дерева слияния, чтобы помочь понять, как работает структура?

Я хотел бы ответить на каждый из этих вопросов по очереди.

Q1: Что вы храните в дереве слияния? Подойдут ли они для 32-битных целых чисел?

Ваш первый вопрос был о том, для чего предназначены деревья слияния. Структура данных Fusion Tree специально разработана для хранения целых чисел, которые помещаются в одно машинное слово. В результате на 32-битной машине вы использовали бы дерево слияния для хранения целых чисел длиной до 32 бит, а на 64-битной машине вы использовали бы дерево слияния для хранения целых чисел до 64 бит.

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

Но прежде чем мы пойдем дальше, я должен сделать одну важную оговорку: деревья слияния представляют только теоретический интерес. Хотя кажется, что деревья слияния имеют отличные гарантии времени выполнения (O (log_w n) время на операцию, где w - размер машинного слова), фактические детали реализации таковы, что скрытые постоянные факторы огромны и являются серьезным препятствием для практического внедрения. Первоначальная статья о деревьях слияния была в основном направлена ​​на доказательство того, что можно превзойти нижнюю границу Ω(log n) для операций BST с помощью параллелизма на уровне слов и без учета затрат времени выполнения настенных часов. В этом смысле, если ваша цель в понимании деревьев слияния состоит в том, чтобы использовать их на практике, я бы рекомендовал остановиться здесь и поискать другую структуру данных. С другой стороны, если вам интересно узнать, сколько скрытой силы доступно в простых машинных словах, то, пожалуйста, продолжайте читать!

Q2: Чем дерево слияния отличается от обычного B-дерева?

На высоком уровне вы можете думать о дереве слияния как о обычном B-дереве с добавлением некоторой дополнительной магии для ускорения поиска.

Напомним, B-дерево порядка b - это дерево многостороннего поиска, где интуитивно каждый узел хранит (примерно) b ключей. B-дерево - это многостороннее дерево поиска, что означает, что ключи в каждом узле хранятся в отсортированном порядке, а дочерние деревья хранят элементы, упорядоченные относительно этих ключей. Например, рассмотрим этот узел B-дерева:

             +-----+-----+-----+-----+
             | 103 | 161 | 166 | 261 |
             +-----+-----+-----+-----+
            /      |     |     |      \
           /       |     |     |       \
          A        B     C     D        E

Здесь A, B, C, D и E - поддеревья корневого узла. Поддерево A состоит из ключей строго меньше чем 103, так как оно находится слева от 103. Поддерево B состоит из ключей от 103 до 161, поскольку поддерево B зажато между 103 и 161. Аналогично поддерево C состоит из ключей от 161 до 166, поддерево D состоит из ключей от 166 до 261, а поддерево E состоит из ключей более 261.

Чтобы выполнить поиск в B-дереве, вы начинаете с корневого узла и неоднократно спрашиваете, в какое поддерево вам нужно спуститься, чтобы продолжить поиск. Например, если бы я хотел найти 137 в приведенном выше дереве, мне нужно было бы каким-то образом определить, что 137 находится в поддереве B. Есть два "естественных" способа выполнить этот поиск:

• Выполните линейный поиск по клавишам, чтобы найти место, куда нам нужно идти. Время: O(b), где b - количество ключей в узле.
• Выполните двоичный поиск ключей, чтобы найти то место, куда нам нужно идти. Время: O(log b), где b - количество ключей в узле.

Поскольку каждый узел в B-дереве имеет коэффициент ветвления b или больше, высота B-дерева порядка b равна O(log_b n). Следовательно, если мы используем первую стратегию (линейный поиск), чтобы найти, в какое дерево спуститься, работа в худшем случае, необходимая для поиска, составляет O (b log_b n), поскольку мы выполняем O (b) работу на уровень через O(log_b n) уровней. Интересный факт: величина b log_b n минимизируется, когда b = e, и становится все хуже, когда мы увеличиваем b сверх этого предела.

С другой стороны, если мы используем двоичный поиск, чтобы найти дерево, в которое нужно спуститься, время выполнения окажется равным O(log b · log_b n). Используя замену базовой формулы для логарифмов, обратите внимание, что

журнал b · журнал_b n = журнал b · (журнал n / журнал b) = журнал n,

поэтому время выполнения поиска таким образом - O(log n), независимо от b. Это соответствует временным рамкам поиска обычного сбалансированного BST.

Магия дерева слияния заключается в том, чтобы найти способ определить, в какое поддерево спуститься за время O(1). Позвольте этому погрузиться на минутку - у нас может быть несколько дочерних элементов на узел в нашем B-дереве, хранящихся в отсортированном порядке, и все же мы можем найти, между какими двумя ключами находится наш элемент за время O(1)! Сделать это определенно нетривиально, и это основная часть волшебства дерева слияния. Но пока, предполагая, что мы можем это сделать, обратите внимание, что время выполнения поиска в дереве слияния будет O(log_b n), поскольку мы выполняем O(1) раз O(log_b слоев) в дереве!

Теперь вопрос в том, как это сделать.

Q3: дерево слияния выбирает b = w^1/5, где w - размер машинного слова. Означает ли это, что b = 2 на 32-битной машине, и делает ли это просто двоичное дерево?

По техническим причинам, которые станут понятнее позже, дерево слияния работает, выбирая в качестве параметра ветвления для B-дерева значение b = w^1/5, где w - размер машинного слова. На 32-битной машине это означает, что мы выбрали бы

b = w^1/5 = (2⁵)^1/5 = 2,

а на 64-битной машине мы бы выбрали

b = w^1/5 = (2⁶)^1/5 = 2^6/5 ≈ 2,29,

которое мы, вероятно, округлим до 2. Значит ли это, что дерево слияния - это просто двоичное дерево?

Ответ - "не совсем". В B-дереве каждый узел хранит от b - 1 до 2b - 1 общих ключей. При b = 2 это означает, что каждый узел хранит от 1 до 3 общих ключей. (Другими словами, наше B-дерево будет деревом 2-3-4, если вы знакомы с этой прекрасной структурой данных). Это означает, что мы будем ветвиться немного больше, чем обычное двоичное дерево поиска, но не намного.

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

С другой стороны, если бы мы работали, скажем, на машине, размер слова которой составлял 32768 бит (я не затаил дыхание, увидев одну из них в своей жизни), то мы получили бы коэффициент ветвления b = 8, и мы действительно можем начать видеть что-то, что превосходит обычный BST.

Q4: Почему так много обсуждений дерева слияния сосредоточено на эскизах?

Как упоминалось выше, "секретным соусом" дерева слияния является возможность дополнить каждый узел в B-дереве некоторой вспомогательной информацией, которая позволяет эффективно (за время O(1)) определить, какое поддерево B- дерево, в которое нужно спуститься. Как только у вас появится возможность заставить этот шаг работать, остальная часть структуры данных будет в основном обычным B-деревом. Следовательно, имеет смысл подробно (исключительно?) Сосредоточиться на том, как работает этот шаг.

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

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

             +-----+-----+-----+-----+
             | 103 | 161 | 166 | 261 |
             +-----+-----+-----+-----+
            /      |     |     |      \
           /       |     |     |       \
         T0       T1    T2    T3       T4

Это тот же рисунок, что и раньше, но вместо того, чтобы маркировать поддеревья A, B, C, D и E, я пометил их T0, T1, T2, T3 и T4.

Представим, что я хочу найти 162. Это должно поместить меня в поддерево T2. Один из способов увидеть это состоит в том, что 162 больше, чем 161, и меньше, чем 166. Но есть и другая точка зрения, которую мы можем здесь принять: мы хотим искать T2, потому что 162 больше, чем 103 и 161, два ключа, которые идут перед ним. Интересно - нам нужен индекс дерева 2, а мы больше двух ключей в узле. Хммм.

Теперь найдите 196. Это помещает нас в дерево T3, и 196 оказывается больше, чем 103, 161 и 166, всего три ключа. Интересный. А как насчет 17? Это будет в дереве T0, а 17 больше нуля ключей.

Это намекает на ключевую стратегию, которую мы собираемся использовать, чтобы заставить работать дерево слияния:

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

Ключевым моментом в дереве слияния является то, как это сделать за время O(1).

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

Параллельный ранг: учитывая ключ k, который является небольшим целым числом, и фиксированный набор небольших целых чисел x₁,..., x_b, определите, сколько из x_i меньше или равно k.

Например, у нас может быть набор 6-битных чисел, например 31, 41, 59, 26 и 53, и затем мы могли бы выполнять запросы типа "сколько из этих чисел меньше или равно 37?"

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

00111110101001011101100110100110101
0  31  0  41  0  59  0  26  0  53

Теперь предположим, что мы хотим увидеть, сколько из этих чисел меньше или равно 37. Для этого мы начинаем с формирования целого числа, которое состоит из нескольких реплицированных копий числа 37, каждой из которых предшествует 1 бит. Это выглядело бы так:

11001011100101110010111001011100101
1  37  1  37  1  37  1  37  1  37  

Что-то очень интересное произойдет, если мы вычтем первое число из второго числа. Смотри:

  11001011100101110010111001011100101    1  37  1  37  1  37  1  37  1  37
- 00111110101001011101100110100110101  - 0  31  0  41  0  59  0  26  0  53
  -----------------------------------    ---------------------------------
  10001100111100010101010010110110000    1   6  0  -4  0  -12 1   9  0 -16
  ^      ^      ^      ^      ^          ^      ^      ^      ^      ^

Биты, которые я здесь выделил, - это дополнительные биты, которые мы добавили в начало каждого числа. Обратите внимание, что

• если верхнее число больше или равно нижнему числу, то бит перед результатом вычитания будет равен 1, и
• если верхнее число меньше нижнего числа, то бит перед результатом вычитания будет равен 0.

Чтобы понять, почему это так, если верхнее число больше или равно нижнему числу, тогда, когда мы выполняем вычитание, нам никогда не придется "заимствовать" лишний 1 бит, который мы помещаем перед верхним числом, так что этот бит останется 1. В противном случае верхнее число будет меньше, поэтому, чтобы вычитание сработало, мы должны заимствовать из этого 1 бита, отмечая его как ноль. Другими словами, эту единственную операцию вычитания можно рассматривать как параллельное сравнение исходного ключа и каждого из маленьких чисел. Мы делаем одно вычитание, но, по логике, это пять сравнений!

Если мы сможем подсчитать, сколько из отмеченных битов равны единицам, тогда мы получим желаемый ответ. Оказывается, это требует некоторого дополнительного творчества для работы за время O(1), но это действительно возможно.

Эта операция параллельного ранжирования показывает, что если у нас есть много действительно маленьких ключей - настолько маленьких, что мы можем упаковать их в машинное слово - мы действительно можем пойти и вычислить ранг нашего ключа поиска за время O(1), что скажет нам, в какое поддерево нам нужно спуститься. Однако есть одна загвоздка - эта стратегия предполагает, что наши ключи действительно маленькие, но в целом у нас нет причин предполагать это. Если мы храним полные 32-битные или 64-битные машинные слова в качестве ключей, мы не сможем упаковать их большое количество в одно машинное слово. Мы можем поместить в машинное слово ровно один ключ!

Чтобы решить эту проблему, деревья слияния используют другое понимание. Давайте представим, что мы выбираем фактор ветвления нашего B-дерева очень маленьким по сравнению с количеством битов в машинном слове (скажем, b = w^1/5). Если у вас небольшое количество машинных слов, главное, что вам нужно, это то, что только несколько битов в этих машинных словах действительно важны для определения порядка. Например, предположим, что у меня есть следующие 32-битные числа:

A: 00110101000101000101000100000101
B: 11001000010000001000000000000000
C: 11011100101110111100010011010101
D: 11110100100001000000001000000000

А теперь представьте, что я хотел отсортировать эти числа. Для этого мне действительно нужно взглянуть на некоторые детали. Например, некоторые числа различаются своим первым битом (у верхнего числа A там 0, а у остальных - 1). Итак, я запишу, что мне нужно посмотреть на первый бит числа. Второй бит этих чисел на самом деле не помогает сортировать вещи - все, что отличается во втором бите, уже отличается в первом бите (вы понимаете, почему?). Третий бит числа аналогичным образом помогает нам ранжировать их, потому что числа B, C и D, которые имеют один и тот же первый бит, расходятся в третьем бите на группы (B, C) и D. Мне также потребуется посмотрите на четвертый бит, который разделяет (B, C) на B и C.

Другими словами, чтобы сравнить эти числа друг с другом, нам нужно будет сохранить только эти отмеченные биты. Если мы обработаем эти биты по порядку, нам никогда не придется смотреть на другие:

A: 00110101000101000101000100000101
B: 11001000010000001000000000000000
C: 11011100101110111100010011010101
D: 11110100100001000000001000000000
   ^ ^^

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

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

Q5: Доступна ли визуализация дерева слияния, чтобы помочь понять, как работает структура?

Да и нет. Я скажу "да", потому что есть ресурсы, которые показывают, как работают разные шаги. Однако я скажу "нет", потому что я не верю, что есть какая-то картина, на которую вы можете смотреть, которая заставит всю структуру данных внезапно щелкнуть в фокусе.

Я преподаю курс по продвинутым структурам данных и провел две 80-минутные лекции, построив дерево слияния с использованием методов параллелизма на уровне слов. Обсуждение здесь основано на этих лекциях, которые более подробно рассматривают каждый шаг и включают визуализацию различных подшагов (как вычислить ранг за постоянное время, как работает шаг зарисовки и т. Д.), И каждый из этих шагов может индивидуально даст вам лучшее представление о том, как работает вся структура. Ссылки на эти материалы приведены здесь:

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

• Во второй части исследуется полная версия дерева слияния, представляя основы этапа создания эскиза (который я называю "кодами Патрисии" на основании связи с деревом Патрисии).

Обобщить

В итоге:

• Дерево слияния - это модификация B-дерева. Базовая структура соответствует структуре обычного B-дерева, за исключением того, что каждый узел имеет некоторую вспомогательную информацию для ускорения поиска.

• На данный момент деревья слияния представляют чисто теоретический интерес. Скрытые постоянные факторы слишком высоки, а фактор ветвления слишком мал, чтобы значимо конкурировать с бинарными деревьями поиска.

• Деревья слияния используют параллелизм на уровне слов для ускорения поиска, обычно путем упаковки нескольких чисел в одно машинное слово и использования отдельных операций для имитации параллельной обработки.

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

• Есть слайды с лекциями, в которых это более подробно описано.

Надеюсь это поможет!

Answer 3

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

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

Он должен иметь B в своих искусственных B-деревьях, довольно маленьких для реальных машин (B=5 для 32 бит, возможно 10 для 64 бит). Это много указателей в значительной степени помещается в строку кэша. После первого касания строки кэша (которого он не может избежать) из нескольких сотен циклов вы можете в значительной степени выполнить линейный поиск по ключам за несколько циклов на ключ, что означает, что традиционная реализация тщательно кодированного B-дерева выглядит так должен опередить слияние деревьев. (Я построил такой код B-дерева для поддержки нашей системы преобразования программ).

Он претендует на список заявок, но сравнительных цифр нет.

У кого-нибудь есть веские доказательства? (Реализации и сравнения?)

Answer 4

Идея дерева слияния на самом деле довольно проста. Предположим, у вас есть w-битные (скажем, 64-битные) ключи, идея состоит в том, чтобы сжимать (т.е. создавать эскизы) каждые последовательные 64 ключа в массив из 64 элементов. Функция создания эскиза обеспечивает отображение постоянного времени между исходными ключами и индексом массива для данной группы. Затем поиск ключа становится поиском группы, содержащей ключ, который является O(log(n/64)). Как видите, основной проблемой является функция зарисовки.