М-дерево - M-tree

М-деревья находятся древовидные структуры данных которые похожи на R-деревья и B-деревья. Он построен с использованием метрика и полагается на неравенство треугольника для эффективного диапазона и k-ближайший сосед (k-NN) запросы. Хотя M-деревья могут хорошо работать во многих условиях, дерево также может иметь большое перекрытие, и нет четкой стратегии, как лучше всего избежать перекрытия. Кроме того, его можно использовать только для функции расстояния которые удовлетворяют неравенству треугольника, в то время как многие расширенные функции различия, используемые в поиск информации не удовлетворите это.^[1]

Обзор

2D M-Tree, визуализированное с помощью ELKI. Из-за масштабов осей сферы выглядят эллипсоидальными. Каждая синяя сфера (лист) содержится в красной сфере (узлы каталога). Листья перекрывают друг друга, но не слишком сильно.

Как и в любой структуре данных на основе дерева, M-дерево состоит из узлов и листьев. В каждом узле есть объект данных, который однозначно его идентифицирует, и указатель на поддерево, в котором находятся его дочерние элементы. На каждом листе есть несколько объектов данных. Для каждого узла есть радиус ${\displaystyle r}$ который определяет шар в желаемом метрическом пространстве. Таким образом, каждый узел ${\displaystyle n}$ и лист ${\displaystyle l}$ проживающий в конкретном узле ${\displaystyle N}$ на наибольшем расстоянии ${\displaystyle r}$ из ${\displaystyle N}$, и каждый узел ${\displaystyle n}$ и лист ${\displaystyle l}$ с родителем узла ${\displaystyle N}$ держитесь от него на расстоянии.

Конструкция M-Tree

Составные части

M-Tree состоит из следующих компонентов и подкомпонентов:

1. Нелистовые узлы
   1. Набор объектов маршрутизации N_RO.
   2. Указатель на родительский объект узла O_п.
2. Листовые узлы
   1. Набор предметов N_О.
   2. Указатель на родительский объект узла O_п.
3. Объект маршрутизации
   1. (Значение функции) объект маршрутизации O_р.
   2. Радиус покрытия r (O_р).
   3. Указатель на покрывающее дерево T (O_р).
   4. Расстояние O_р от своего родительского объекта d (O_р, P (O_р))
4. Объект
   1. (Значение свойства) объект O_j.
   2. Идентификатор объекта oid (O_j).
   3. Расстояние O_j от своего родительского объекта d (O_j, P (O_j))

Вставлять

Основная идея - сначала найти листовой узел N где новый объект О принадлежит. Если N не заполнен, просто прикрепите его к N. Если N заполнено, затем вызовите метод для разделения N. Алгоритм следующий:

Алгоритм Вставить ввод: узел N M-Tree MT, Вход ${\displaystyle O_{n}}$  Выход: новый экземпляр MT содержащий все записи в оригинале MT плюс ${\displaystyle O_{n}}$

  ${\displaystyle N_{e}\gets N}$объекты маршрутизации или объекты если N это не лист тогда  {/ * Ищите записи, в которые вписывается новый объект * / позволять ${\displaystyle N_{in}}$ маршрутизировать объекты из ${\displaystyle N_{e}}$набор объектов маршрутизации ${\displaystyle N_{RO}}$ такой, что ${\displaystyle d(O_{r},O_{n})\leq r(O_{r})}$       если ${\displaystyle N_{in}}$ не пусто тогда       {/ * Если есть одна или несколько записей, ищите такую, которая ближе к новому объекту * / ${\displaystyle O_{r}^{*}\gets \min _{O_{r}\in N_{in}}d(O_{r},O_{n})}$       }       еще       {/ * Если такой записи нет, то ищите объект с минимальным расстоянием от * / / * края радиуса покрытия до нового объекта * / ${\displaystyle O_{r}^{*}\gets \min _{O_{r}\in N_{in}}d(O_{r},O_{n})-r(O_{r})}$          / * Обновляем новые радиусы записи * / ${\displaystyle r(O_{r}^{*})\gets d(O_{r}^{*},O_{n})}$       } / * Продолжаем вставку на следующем уровне * / возвращаться вставлять(${\displaystyle T(O_{r}^{*}),O_{n}}$);  еще  {/ * Если узел имеет емкость, просто вставьте новый объект * / если N не полный тогда       { хранить(${\displaystyle N,O_{n}}$) } / * Узел загружен на полную мощность, тогда необходимо сделать новое разбиение на этом уровне * / еще       { расколоть(${\displaystyle N,O_{n}}$) }  }

• «←» означает назначение. Например, "самый большой ← элемент"означает, что стоимость самый большой изменяет стоимость элемент.
• "возвращаться"завершает алгоритм и выводит следующее значение.

Расколоть

Если метод разделения достигает корня дерева, он выбирает два объекта маршрутизации из N, и создает два новых узла, содержащих все объекты в исходном N, и сохраните их в новом корне. Если методы разделения доходят до узла N это не корень дерева, метод выбирает два новых объекта маршрутизации из N, перегруппируйте каждый объект маршрутизации в N в двух новых узлах ${\displaystyle N_{1}}$ и ${\displaystyle N_{2}}$, и сохраните эти новые узлы в родительском узле ${\displaystyle N_{p}}$ оригинального N. Разделение необходимо повторить, если ${\displaystyle N_{p}}$ не хватает емкости для хранения ${\displaystyle N_{2}}$. Алгоритм следующий:

Алгоритм Разделение ввода: узел N M-Tree MT, Вход ${\displaystyle O_{n}}$  Выход: новый экземпляр MT содержащий новый раздел.

  / * Новые объекты маршрутизации теперь все те, что находятся в узле, плюс новый объект маршрутизации * / пусть будет NN записи ${\displaystyle N\cup O}$  если N это не корень тогда  {/ * Получить родительский узел и родительский объект маршрутизации * / позволять ${\displaystyle O_{p}}$ быть родительским объектом маршрутизации N     позволять ${\displaystyle N_{p}}$ быть родительским узлом N  } / * Этот узел будет содержать часть объектов узла, который будет разделен * / Создаем новый узел N '  / * Перемещение двух объектов маршрутизации из узла, который нужно разделить, в новые объекты маршрутизации * / Создание новых объектов ${\displaystyle O_{p1}}$ и ${\displaystyle O_{p2}}$.  Продвигать(${\displaystyle N,O_{p1},O_{p2}}$) / * Выберите, какие объекты из разделяемого узла будут действовать как новые объекты маршрутизации * / Partition (${\displaystyle N,O_{p1},O_{p2},N_{1},N_{2}}$) / * Сохранять записи в каждом новом объекте маршрутизации * / Магазин ${\displaystyle N_{1}}$записи в N и ${\displaystyle N_{2}}$записи в N '  если N текущий корень тогда  {/ * Создайте новый узел и установите его как новый корень и сохраните новые объекты маршрутизации * / Создайте новый корневой узел ${\displaystyle N_{p}}$      Магазин ${\displaystyle O_{p1}}$ и ${\displaystyle O_{p2}}$ в ${\displaystyle N_{p}}$  }  еще  {/ * Теперь используйте родительский объект маршрутизации для хранения одного из новых объектов * / Заменить запись ${\displaystyle O_{p}}$ с входом ${\displaystyle O_{p1}}$ в ${\displaystyle N_{p}}$      если ${\displaystyle N_{p}}$ не полный тогда      {/ * Второй объект маршрутизации сохраняется в родительском только в том случае, если у него есть свободная емкость * / Магазин ${\displaystyle O_{p2}}$ в ${\displaystyle N_{p}}$      }      еще      {/ * Если свободных мест нет, разделите уровень вверх * / расколоть(${\displaystyle N_{p},O_{p2}}$)      }  }

• «←» означает назначение. Например, "самый большой ← элемент"означает, что стоимость самый большой изменяет стоимость элемент.
• "возвращаться"завершает алгоритм и выводит следующее значение.

Запросы M-Tree

Запрос диапазона

В запросе диапазона указывается минимальное значение сходства / максимального расстояния. Для данного объекта запроса ${\displaystyle Q\in D}$ и максимальное расстояние поиска${\displaystyle r(Q)}$, запрос диапазона классифицировать(Q, r (Q)) выбирает все проиндексированные объекты ${\displaystyle O_{j}}$ такой, что ${\displaystyle d(O_{j},Q)\leq r(Q)}$.^[2]

Алгоритм RangeSearch начинается с корневого узла и рекурсивно просматривает все пути, которые нельзя исключить из ведущих к квалифицируемым объектам.

Алгоритм RangeSearchInput: узел N компании M-Tree MT, Q: объект запроса, ${\displaystyle r(Q)}$: радиус поиска

Вывод: все объекты БД такой, что ${\displaystyle d(Oj,Q)\leq r(Q)}$

{   позволять ${\displaystyle O_{p}}$ быть родительский объект узла N;  если N не является лист тогда {     для каждого Вход(${\displaystyle O_{r}}$) в N делать {          если ${\displaystyle |d(O_{p},Q)-d(O_{r},O_{p})|\leq r(Q)+r(O_{r})}$ тогда {             Вычислить ${\displaystyle d(O_{r},Q)}$;            если ${\displaystyle d(O_{r},Q)\leq r(Q)+r(O_{r})}$ тогда              RangeSearch(* птр (${\displaystyle T(O_{r}}$)),Q,${\displaystyle r(Q)}$);           }    }  }  еще {     для каждого Вход(${\displaystyle O_{j}}$) в N делать {          если ${\displaystyle |d(O_{p},Q)-d(O_{j},O_{p})|\leq r(Q)}$ тогда {             Вычислить ${\displaystyle d(O_{j},Q)}$;            если ${\displaystyle d(O_{j},Q)}$ ≤ ${\displaystyle r(Q)}$ тогда              Добавить ${\displaystyle oid(O_{j})}$ к результату;          }    }  }}

• «←» означает назначение. Например, "самый большой ← элемент"означает, что стоимость самый большой изменяет стоимость элемент.
• "возвращаться"завершает алгоритм и выводит следующее значение.

• ${\displaystyle oid(O_{j})}$ - это идентификатор объекта, который находится в отдельном файле данных.
• ${\displaystyle T(O_{r})}$ поддерево - покрывающее дерево ${\displaystyle O_{r}}$

k-NN запросы

Запрос K Nearest Neighbor (k-NN) принимает мощность входного набора в качестве входного параметра. Для заданного объекта запроса Q ∈ D и целого числа k ≥ 1 запрос NN (Q, k) k-NN выбирает k индексированных объектов, которые имеют кратчайшее расстояние от Q в соответствии с функцией расстояния d.^[2]

Смотрите также

• Сегментное дерево
• Дерево интервалов - Вырожденное R-дерево для 1 измерения (обычно времени).
• Иерархия ограничивающего объема
• Пространственный индекс
• Суть

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

1. Чаччиа, Паоло; Пателла, Марко; Зезула, Павел (1997). «M-tree - эффективный метод доступа для поиска сходства в метрических пространствах» (PDF). Материалы 23-й конференции VLDB Афины, Греция, 1997 г.. Исследовательский центр IBM Almaden: Фонд очень больших баз данных, Inc., стр. 426–435. p426. Получено 2010-09-07.
2. П. Чаччиа; М. Пателла; Ф. Рабитти; П. Зезула. «Индексирование метрических пространств с помощью M-дерева» (PDF). Департамент компьютерных наук и инженерии. Болонский университет. п. 3. Получено 19 ноября 2013.