М-дерево

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

Обзор

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. разделения Алгоритм следующий:

Algorithm Insert
  Input: Node N of M-Tree MT, Entry $O_{n}$
  Output: A new instance of MT containing all entries in original MT plus $O_{n}$

  $N_{e}\gets N$'s routing objects or objects
  if N is not a leaf then
  {
       /* Look for entries that the new object fits into */
       let $N_{in}$ be routing objects from $N_{e}$'s set of routing objects $N_{RO}$ such that $d(O_{r},O_{n})\leq r(O_{r})$
       if $N_{in}$ is not empty then
       {
          /* If there are one or more entry, then look for an entry such that is closer to the new object */
          $O_{r}^{*}\gets \min _{O_{r}\in N_{in}}d(O_{r},O_{n})$
       }
       else
       {
          /* If there are no such entry, then look for an object with minimal distance from */ 
          /* its covering radius's edge to the new object */
          $O_{r}^{*}\gets \min _{O_{r}\in N_{in}}d(O_{r},O_{n})-r(O_{r})$
          /* Upgrade the new radii of the entry */
          $r(O_{r}^{*})\gets d(O_{r}^{*},O_{n})$
       }
       /* Continue inserting in the next level */
       return insert($T(O_{r}^{*}),O_{n}$);
  else
  {
       /* If the node has capacity then just insert the new object */
       if N is not full then
       { store($N,O_{n}$) }
       /* The node is at full capacity, then it is needed to do a new split in this level */
       else
       { split($N,O_{n}$) }
  }

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

Сплит

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

Algorithm Split
  Input: Node N of M-Tree MT, Entry $O_{n}$
  Output: A new instance of MT containing a new partition.

  /* The new routing objects are now all those in the node plus the new routing object */
  let be NN entries of $N\cup O$
  if N is not the root then
  {
     /*Get the parent node and the parent routing object*/
     let $O_{p}$ be the parent routing object of N
     let $N_{p}$ be the parent node of N
  }
  /* This node will contain part of the objects of the node to be split */
  Create a new node N'
  /* Promote two routing objects from the node to be split, to be new routing objects */
  Create new objects $O_{p1}$ and $O_{p2}$.
  Promote($N,O_{p1},O_{p2}$)
  /* Choose which objects from the node being split will act as new routing objects */
  Partition($N,O_{p1},O_{p2},N_{1},N_{2}$)
  /* Store entries in each new routing object */
  Store $N_{1}$'s entries in N and $N_{2}$'s entries in N'
  if N is the current root then
  {
      /* Create a new node and set it as new root and store the new routing objects */
      Create a new root node $N_{p}$
      Store $O_{p1}$ and $O_{p2}$ in $N_{p}$
  }
  else
  {
      /* Now use the parent routing object to store one of the new objects */
      Replace entry $O_{p}$ with entry $O_{p1}$ in $N_{p}$
      if $N_{p}$ is no full then
      {
          /* The second routing object is stored in the parent only if it has free capacity */
          Store $O_{p2}$ in $N_{p}$
      }
      else
      {
           /*If there is no free capacity then split the level up*/
           split($N_{p},O_{p2}$)
      }
  }

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

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

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

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

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

Algorithm RangeSearch
Input: Node N of M-Tree MT,  Q: query object, $r(Q)$: search radius

Output: all the DB objects such that $d(Oj,Q)\leq r(Q)$

{ 
  let $O_{p}$ be the parent object of node N;

  if N is not a leaf then { 
    for each entry($O_{r}$) in N do {
          if $|d(O_{p},Q)-d(O_{r},O_{p})|\leq r(Q)+r(O_{r})$ then { 
            Compute $d(O_{r},Q)$;
            if $d(O_{r},Q)\leq r(Q)+r(O_{r})$ then
              RangeSearch(*ptr($T(O_{r}$)),Q,$r(Q)$); 
          }
    }
  }
  else { 
    for each entry($O_{j}$) in N do {
          if $|d(O_{p},Q)-d(O_{j},O_{p})|\leq r(Q)$ then { 
            Compute $d(O_{j},Q)$;
            if $d(O_{j},Q)$ ≤ $r(Q)$ then
              add $oid(O_{j})$ to the result;
          }
    }
  }
}

• « ←» означает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого изменяется на значение элемента .
• « 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-дерево для одного измерения (обычно времени).
• Иерархия ограничивающих объемов
• Пространственный индекс
• Суть
• Покровное дерево