Кэш-память kd-Tree

Структуры данных kd-tree, не обращающие внимания на кэш, — отличная утилита, выполняющая поиск в многомерном ортогональном диапазоне. Одним из основных терминов kd-деревьев является разбиение двоичного пространства, которое периодически делит пространство на два выпуклых множества с использованием гиперплоскостей в качестве разбиения.

В этой статье основное внимание уделяется подробному обсуждению следующих тем:

1. Кэш Oblivious kd-tree.
2. Макет Ван Эмде Боаса.
3. Работа с Cache Oblivious деревом kd.
4. Преимущества Cache Oblivious kd-tree.
5. Ограничения Cache Oblivious kd-tree.

Cache-Oblivious kd-tree

• Cache oblivious kd tree отвечает на запросы и обновления в определенной передаче памяти.
• Структура может быть увеличена для поддержки запросов d-мерного диапазона с той же границей обновления.
• Для продвижения структуры используются некоторые структуры, не обращающие внимания на кэш, такие как макет ван Эмде Боаса и экспоненциальные деревья поиска.
• kd-дерево, предложенное Джоном Луисом Бентли, представляет собой бинарное дерево высоты O(log ₂ N) с N точками, размещенными в листьях дерева. Внутренние узлы (которые также являются поддеревьями) показывают периодическую декомпозицию плоскости с помощью ортогональных линий, которые разбивают набор точек на два подмножества одинакового размера.
• На четных уровнях дерева разделительные линии горизонтальные, а на нечетных — вертикальные. Таким образом, прямоугольная область A _v спонтанно связана с каждым узлом v, а узлы на любом отдельном уровне дерева разбивают плоскость на непересекающиеся области. Есть несколько агрегаторов, чтобы решить, какое значение будет по оси x и оси y плоскости, если для определенного обоснования выбрана ось x, все точки меньше x перейдут в левое поддерево, а все точки больше чем x пойдет в правильное поддерево.

Макет Ван Эмде Боаса

• Компоновка Ван Эмде Боаса — это калиброванный способ установки сбалансированного дерева в памяти таким образом, чтобы можно было эффективно пройти путь от корня к листу в модели без учета кеша.
• ВЭБ имеет свойства предоставлять доступ к функционированию ассоциированного массива. Такие как Insert, Delete, Lookup, FindNext, FindPrevious, которые затем используются для размещения пар ключ-значение в памяти.
• Ван Эмде Боас заметил, что если ключи настроены на набор {1, 2, 3, …, n}, то все операции могут быть выполнены за время O (log log n) и пространство O (n).

Работа с Cache Oblivious kd-tree

Этот раздел посвящен обсуждению трех операций над Cache Oblivious kd-tree-.

1. Вставка
2. Запрос
3. Удаление

Давайте подробно обсудим каждую из этих операций.

1. Вставка:

С помощью макета Ван Эмде Боаса разъясняется экспоненциальный макет. В этом макете сбалансированное двоичное дерево T с N листьями рекурсивно разбивается на набор компонентов, каждый из которых размещается с использованием свойства INSERT макета Ван Эмде Боаса.

Предположим для анализа структуры, что N имеет вид 22 ^ C, где C — целое неотрицательное число.

• Формат памяти: способ построения сбалансированного двоичного дерева на уровне класса — это макет Ван Эмде Боаса. Путь корня-листа в этом макете может систематически проходить в модели без кеша.

Двоичное дерево T высоты O(log ₂ N) с N листьями может быть размещено в O(N) смежных ячейках памяти, так что любой путь корневого листа может быть пройден без кеша за O(logN) передач памяти.

• В этом макете сбалансированное двоичное дерево T с N листьями рекурсивно разбивается на набор компонентов, каждый из которых размещается с использованием макета Ван Эмде Боаса. Мы определяем компонент C ₀ как состоящий из первых 1/2 log ₂ N уровней T . C ₀ содержит Θ(√N) узлов и называется N -компонентой, поскольку ее корень является корнем дерева (T) с N листьями.
• Цель состоит в том, чтобы получить экспоненциальный макет T , используя макет Ван Эмде Боаса.
• Прежде всего, заготовьте C ₀ с использованием макета ван Эмде Боаса, немедленно сопровождая рекурсивную компоновку √N поддеревьев, T ₁ , T ₂ , …, T _√N , размером √N под C ₀ в T , инструктируя слева направо. Рекурсия останавливается, когда поддерево имеет 2 листа; такой 2-х компонент разложен в 3-х последовательных ячейках памяти.

• Смысл экспоненциальной схемы естественным образом определяет разложение T на log ₂ log ₂ N +2 слоев, где i -й слой состоит из N ^{1/2^i−1} компонентов. X -компонента имеет размер Θ(√X) и ее √X/2 листа соединены с √X -компонентами. Таким образом, корень X -компоненты является корнем kd-дерева, содержащего X точек.

2. Запрос:

• Рассмотрим экспоненциальную компоновку сбалансированного бинарного дерева F с W листьями, и пусть e будет корнем в поддереве F _e дерева F, содержащего W листьев. Любой обход F _e может быть выполнен за O(1) передач памяти.
• Узел e хранится внутри X-компоненты с F ≤ X ≤ F ² . X-компонент имеет размер O(F) и поэтому хранится в блоках O(1). При этом та часть F _e , которая не входит в X-компоненту, сохраняется в памяти последовательно блоками O(1). Следовательно, оптимальная стратегия подкачки может гарантировать, что любой обход T будет выполняться за O(1) передач памяти, просто загрузив O(1) релевантных блоков.

Как выполняется запрос?

• Мы периодически отвечаем на запрос диапазона C на не обращающем внимания на кеш kd-дереве Q, начиная с корня: в узле e мы двигаемся по запросу к дочернему элементу e _c узла e, если C пересекает область Rec, связанную _{с e c .}
• Градационный способ ограничить количество узлов в Q, посещенных при ответе на запрос C, или аналогичный, количество узлов _e , где Re пересекает C, состоит в том, чтобы сначала ограничить количество узлов _e , где Re пересекает вертикальную линию j . .
• Область Rr, связанная с корнем _r , очевидно, пересекается j, но поскольку области, связанные с двумя его дочерними элементами, представляют собой подразделение Rr вертикальной линией, пересекается только область _Rrc , связанная _с одним из этих дочерних элементов _rc . . Поскольку область Rr _c подразделяется горизонтальной линией, области, связанные с обоими дочерними элементами r _c , пересекаются.
• Поскольку каждый из этих дочерних элементов содержит N/4 точки , рекуррентность для количества областей, пересекаемых j, равна:

C(N)=2+2C(N/4) = O(√N). 

• Следовательно, мы можем сказать, что количество областей, пересекаемых горизонтальной линией, равно O(√N) . Это означает, что количество областей, пересекаемых границей C, равно O(√N) . Количество дополнительных узлов, посещенных при ответе C, ограничено O(Q), поскольку их соответствующие области полностью содержатся в C. Таким образом, всего посещается O(√N + Q) узлов.
• Он поддерживает обновления за O(log ₂ N/B · log _M/B N) = O(log ² _B N) передач. «В» здесь — блок памяти.

3. Удаление:

• Есть два инварианта, когда мы пытаемся удалить точку из kd-дерева, выложенного с использованием расслабленной экспоненциальной схемы. Мы должны найти соответствующий лист W и удалить его и его родителя.
• Первый инвариант: удаление W может привести к нарушению этого инварианта для каждой из компонент O(log log N) на пути от корня T к W.
• Пусть C будет самой верхней компонентой, в которой нарушается инвариант 1.
• Пусть _V — корень C, а TV — поддерево с корнем в V.
• Если T _V является X-компонентой, то она содержит X/2 − 1 точку.
• Чтобы восстановить инвариант, мы сначала собираем X/2 − 1 точку в T _V , а также X/2 ≤ X` ≤ 2X точек в поддереве <sub>TV` с</sub> корнем в соседнем V` дерева V, и уничтожаем T <sub>V</sub> , <sub>TV V`</sub> и их родитель Y.
• Затем мы строим kd-дерево T` по собранным K точкам. Если X − 1 ≤ K ≤ 2X, мы размещаем T` в пространстве, ранее занятом T _v и T <sub>v`,</sub> используя экспоненциальное расположение, и соединяем прародитель v с корнем T`.
• По сути, мы объединяем T _v и T _{v`</sub> в T`. Поскольку T` содержит от X − 1 до 2X точек в первом случае, а T <sub>U</sub> и T <sub>U`} содержат от X до 5X/4 точек во втором случае, мы можем в обоих вышеупомянутых случаях расположить построенные деревья так, что их корни являются корнями X-компоненты. Таким образом, инвариант 1 восстанавливается.

• Поиск листа W требует O(log _B N) передач памяти.
• Общая амортизированная стоимость восстановления первого инварианта равна:

∑ _i=0 ^{log log N} O( 1/B log_M/B N^1/2i) = O( 1/B log_B N) = O(log_B N) memory transfers.

• Второй инвариант: удаление w может привести к нарушению этого инварианта в узлах на пути от корня T до l.
• Пусть v будет самым верхним узлом, в котором нарушается инвариант 2, и пусть K будет количеством точек в поддереве T _{v с} корнем в v.
• Если v находится в X-компоненте, O(√X) поддеревьев T ₁ , … T _{O(√X )} T _v ниже X-компоненты, содержащей v, используют более 4 КБ смежных ячеек памяти.
• Инвариант 2 можно восстановить, сжав все поддеревья.
• Во-первых, сжать поддерево T _i , содержащее |T _i | узлы путем обхода T _i и пересмотра узлов в |T _i | соседние ячейки памяти. Сжатая компоновка T _i сразу же сопровождается в памяти сжатой компоновкой T _i +1 — эффективно выталкивая все неиспользуемое пространство в каждом поддереве за конец последнего поддерева — теперь поддеревья используют менее 2 КБ соседних ячеек памяти и инвариант 2 восстановлен.

Преимущества Cache Oblivious kd-tree:

• При построении kd-дерева в модели RAM kd-дерево на N точках может быть установлено периодически за время O(N log ₂ N); корень, разделяющий линию, находится с использованием алгоритма медианы времени O (N), точки распределяются на два набора, как заявлено этой линией, за время O (N), и два поддерева строятся периодически.
• Строительство идет быстро.

Ограничения Cache Oblivious kd-tree:

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

использованная литература

• Ван Эмде Боас Дерево
• Структуры данных без кэширования для поиска в ортогональном диапазоне
• Кэш-независимые структуры данных