М-дерево

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

Обзор

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

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

Построение М-дерева

Компоненты

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

1. Нелистовые узлы
   1. Набор объектов маршрутизации N _RO .
   2. Указатель на родительский объект Node _Op .
2. Листовые узлы
   1. Набор объектов N _O .
   2. Указатель на родительский объект Node _Op .
3. Объект маршрутизации
   1. (Значение функции) объекта маршрутизации Или _r .
   2. Радиус покрытия r(O _r ).
   3. Указатель на покрывающее дерево T(O _r ).
   4. Расстояние Or _от родительского объекта d(O _r , P(O _r ))
4. Объект
   1. (Значение признака) объекта O _j .
   2. Идентификатор объекта oid(O _j ).
   3. Расстояние O _j от родительского объекта d(O _j , P(O _j ))

Вставить

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

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

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

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

Сплит

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

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

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

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

Запросы M-дерева

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

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

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

Алгоритм  поиска диапазонаВходные данные: Узел  N  M-Tree MT,  Q  : объект запроса, $r(Q)$: радиус поиска 

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

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

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

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

k -NN запросы

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

См. также

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