М-дерево

редактировать

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

СОДЕРЖАНИЕ

1 Обзор
2 Конструкция M-Tree
- 2.1 Компоненты
- 2.2 Вставить
- 2.3 Сплит
3 запроса M-Tree
- 3.1 Запрос диапазона
- 3.2 k-NN запросов
4 См. Также
5 ссылки

Обзор

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

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

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

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

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

Нелистовые узлы
1. Набор объектов маршрутизации N RO.
2. Указатель на родительский объект узла O стр.
Листовые узлы
1. Набор объектов N O.
2. Указатель на родительский объект узла O стр.
Объект маршрутизации
1. (Значение функции) объект маршрутизации O r.
2. Радиус покрытия r (O r).
3. Указатель на покрывающее дерево T (O r).
4. Расстояние O r от его родительского объекта d (O r, P (O r))
Объект
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}$  $O_{{n}}$  Output: A new instance of MT containing all entries in original MT plus  $O_{n}$  $O_{{n}}$

  $N_{e}\gets 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}$  $N_{{in}}$  be routing objects from  $N_{e}$  $N_{{e}}$ 's set of routing objects  $N_{RO}$  $N_{{RO}}$  such that  $d(O_{r},O_{n})\leq r(O_{r})$  $d(O_{r},O_{n})\leq r(O_{r})$  if  $N_{in}$  $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})$  $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})$  $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})$  $r(O_{r}^{*})\gets d(O_{r}^{*},O_{n})$  } /* Continue inserting in the next level */ return insert( $T(O_{r}^{*}),O_{n}$  $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}$  $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}$  $N,O_{n}$ ) } }

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

Расколоть

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

Algorithm Split Input: Node N of M-Tree MT, Entry  $O_{n}$  $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$  $N\cup O$  if N is not the root then { /*Get the parent node and the parent routing object*/ let  $O_{p}$  $O_{{p}}$  be the parent routing object of N let  $N_{p}$  $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}$  $O_{{p1}}$  and  $O_{p2}$  $O_{{p2}}$ . Promote( $N,O_{p1},O_{p2}$  $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}$  $N,O_{p1},O_{p2},N_{1},N_{2}$ ) /* Store entries in each new routing object */ Store  $N_{1}$  $N_{{1}}$ 's entries in N and  $N_{2}$  $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}$  $N_{{p}}$  Store  $O_{p1}$  $O_{{p1}}$  and  $O_{p2}$  $O_{{p2}}$  in  $N_{p}$  $N_{{p}}$  } else { /* Now use the parent routing object to store one of the new objects */ Replace entry  $O_{p}$  $O_{{p}}$  with entry  $O_{p1}$  $O_{{p1}}$  in  $N_{p}$  $N_{{p}}$  if  $N_{p}$  $N_{{p}}$  is no full then { /* The second routing object is stored in the parent only if it has free capacity */ Store  $O_{p2}$  $O_{{p2}}$  in  $N_{p}$  $N_{{p}}$  } else { /*If there is no free capacity then split the level up*/ split( $N_{p},O_{p2}$  $N_{p},O_{p2}$ ) } }

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

Запросы M-Tree

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

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

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

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

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

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

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

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

k-NN запросы

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

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

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

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