Árbol M

Estructura de datos de árbol

En informática , los árboles M son estructuras de datos en forma de árbol similares a los árboles R y B. Se construyen utilizando una métrica y se basan en la desigualdad triangular para consultas eficientes de rango y de k-vecinos más cercanos (k-NN). Si bien los árboles M pueden funcionar bien en muchas condiciones, el árbol también puede tener una gran superposición y no existe una estrategia clara sobre cómo evitar mejor la superposición. Además, solo se puede utilizar para funciones de distancia que satisfacen la desigualdad triangular, mientras que muchas funciones de disimilitud avanzadas utilizadas en la recuperación de información no la satisfacen. ^[1]

Descripción general

Árbol M 2D visualizado con ELKI . Cada esfera azul (hoja) está contenida en una esfera roja (nodos de directorio). Las hojas se superponen, pero no demasiado; los nodos de directorio se superponen mucho más aquí.

Como en cualquier estructura de datos basada en árboles, el árbol M está compuesto de nodos y hojas. En cada nodo hay un objeto de datos que lo identifica de forma única y un puntero a un subárbol donde residen sus hijos. Cada hoja tiene varios objetos de datos. Para cada nodo hay un radio que define una bola en el espacio métrico deseado. Por lo tanto, cada nodo y hoja que reside en un nodo particular está a una distancia máxima de , y cada nodo y hoja con un nodo padre mantiene la distancia con respecto a él. ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle l}$ ${\displaystyle N}$ ${\displaystyle r}$ ${\displaystyle N}$ ${\displaystyle n}$ ${\displaystyle l}$ ${\displaystyle N}$

Construcción de árboles M

Componentes

Un árbol M tiene estos componentes y subcomponentes:

1. Nodos que no son hojas
   1. Un conjunto de objetos de enrutamiento N _RO .
   2. Puntero al objeto padre del nodo O _p .
2. Nodos de hojas
   1. Un conjunto de objetos N _O .
   2. Puntero al objeto padre del nodo O _p .
3. Objeto de enrutamiento
   1. (Valor de la característica de) objeto de enrutamiento O _r .
   2. Radio de cobertura r(O _r ).
   3. Puntero al árbol de cobertura T(O _r ).
   4. Distancia de O _r desde su objeto padre d(O _r ,P(O _r ))
4. Objeto
   1. (Valor de la característica) del objeto O _j .
   2. Identificador de objeto oid(O _j ).
   3. Distancia de O _j desde su objeto padre d(O _j ,P(O _j ))

Insertar

La idea principal es encontrar primero un nodo hoja N al que pertenece el nuevo objeto O. Si N no está lleno, simplemente adjúntelo a N. Si N está lleno, invoque un método para dividir N. El algoritmo es el siguiente:

Inserción de algoritmo Entrada: Nodo N del M-Tree MT , Entrada ${\displaystyle O_{n}}$ Salida: Una nueva instancia de MT que contiene todas las entradas en el MT original más ${\displaystyle O_{n}}$

  ${\displaystyle N_{e}\gets N}$Los objetos de ruta o los objetos si  N no es una hoja entonces { /* Busque entradas en las que encaje el nuevo objeto */ Sea un objeto de enrutamiento del conjunto de objetos de enrutamiento  ${\displaystyle N_{in}}$ ${\displaystyle N_{e}}$ ${\displaystyle N_{RO}}$ de tal manera que  ${\displaystyle d(O_{r},O_{n})\leq r(O_{r})}$ si no está vacío entonces ${\displaystyle N_{in}}$ { /* Si hay una o más entradas, entonces busque una entrada que esté más cerca del nuevo objeto */  ${\displaystyle O_{r}^{*}\gets \min _{O_{r}\in N_{in}}d(O_{r},O_{n})}$ } demás { /* Si no existe tal entrada, entonces busque un objeto con una distancia mínima de */ /* el borde de su radio de cobertura hasta el nuevo objeto */  ${\displaystyle O_{r}^{*}\gets \min _{O_{r}\in N_{in}}d(O_{r},O_{n})-r(O_{r})}$ /*Actualizar los nuevos radios de la entrada*/  ${\displaystyle r(O_{r}^{*})\gets d(O_{r}^{*},O_{n})}$ } /*Continuar insertando en el siguiente nivel*/ devolver insertar( );  ${\displaystyle T(O_{r}^{*}),O_{n}}$ de lo contrario { /* Si el nodo tiene capacidad entonces simplemente inserte el nuevo objeto */ Si  N no está lleno entonces { store( ) ${\displaystyle N,O_{n}}$ } /* El nodo está a plena capacidad, entonces es necesario hacer una nueva división en este nivel */ de lo contrario { dividir( ) ${\displaystyle N,O_{n}}$ } }

• "←" denota asignación . Por ejemplo, " el elemento más grande ← " significa que el valor del elemento más grande cambia al valor del elemento .
• " return " finaliza el algoritmo y genera el siguiente valor.

Dividir

Si el método split llega a la raíz del árbol, entonces elige dos objetos de ruta de N y crea dos nuevos nodos que contienen todos los objetos en el N original y los almacena en la nueva raíz. Si el método split llega a un nodo N que no es la raíz del árbol, el método elige dos nuevos objetos de ruta de N , reorganiza cada objeto de ruta en N en dos nuevos nodos y y almacena estos nuevos nodos en el nodo padre del N original . La división debe repetirse si no tiene suficiente capacidad para almacenar . El algoritmo es el siguiente: ${\displaystyle N_{1}}$ ${\displaystyle N_{2}}$ ${\displaystyle N_{p}}$ ${\displaystyle N_{p}}$ ${\displaystyle N_{2}}$

Algoritmo de división Entrada: Nodo N del M-Tree MT , Entrada ${\displaystyle O_{n}}$ Salida: Una nueva instancia de MT que contiene una nueva partición.

 /* Los nuevos objetos de enrutamiento ahora son todos los del nodo más el nuevo objeto de enrutamiento */ sean NN entradas de si N no es la raíz entonces ${\displaystyle N\cup O}$   { /*Obtener el nodo principal y el objeto de enrutamiento principal*/ sea ​​el objeto de enrutamiento padre de N ${\displaystyle O_{p}}$  sea el nodo padre de N ${\displaystyle N_{p}}$ } /* Este nodo contendrá parte de los objetos del nodo a dividir */ Crear un nuevo nodo N' /* Promocionar dos objetos de enrutamiento del nodo que se va a dividir para que sean nuevos objetos de enrutamiento */ Crea nuevos objetos y . Promote( ) ${\displaystyle O_{p1}}$ ${\displaystyle O_{p2}}$ ${\displaystyle N,O_{p1},O_{p2}}$ /* Elija qué objetos del nodo que se está dividiendo actuarán como nuevos objetos de enrutamiento */ Partición( ) ${\displaystyle N,O_{p1},O_{p2},N_{1},N_{2}}$ /* Almacenar entradas en cada nuevo objeto de enrutamiento */ Almacene las entradas de en N y las entradas de en N ${\displaystyle N_{1}}$ ${\displaystyle N_{2}}$  si  N es la raíz actual , entonces { /* Crea un nuevo nodo y configúralo como nueva raíz y almacena los nuevos objetos de enrutamiento */ Crea un nuevo nodo raíz  ${\displaystyle N_{p}}$ y almacena en ${\displaystyle O_{p1}}$ ${\displaystyle O_{p2}}$ ${\displaystyle N_{p}}$ } demás { /* Ahora use el objeto de enrutamiento principal para almacenar uno de los nuevos objetos */ Reemplazar entrada con entrada en  ${\displaystyle O_{p}}$ ${\displaystyle O_{p1}}$ ${\displaystyle N_{p}}$ si no está completo entonces ${\displaystyle N_{p}}$ { /* El segundo objeto de enrutamiento se almacena en el padre solo si tiene capacidad libre */ Guardar en ${\displaystyle O_{p2}}$ ${\displaystyle N_{p}}$ } demás { /*Si no hay capacidad libre entonces divide el nivel*/ dividir( ) ${\displaystyle N_{p},O_{p2}}$ } }

• "←" denota asignación . Por ejemplo, " el elemento más grande ← " significa que el valor del elemento más grande cambia al valor del elemento .
• " return " finaliza el algoritmo y genera el siguiente valor.

Consultas de árboles M

Consulta de rango

Una consulta de rango es aquella en la que se especifica un valor de similitud mínima/distancia máxima. Para un objeto de consulta dado y ${\displaystyle Q\in D}$una distancia ${\displaystyle r(Q)}$ de búsqueda máxima , la consulta de rango range ( Q, r(Q)) selecciona todos los objetos indexados de manera ${\displaystyle O_{j}}$ que . [ 2 ${\displaystyle d(O_{j},Q)\leq r(Q)}$^]

El algoritmo RangeSearch comienza desde el nodo raíz y recorre recursivamente todas las rutas que no se pueden excluir de conducir a objetos calificados.

Algoritmo de búsqueda por rangoEntrada: Nodo N del M-Tree MT, Q : objeto de consulta, : radio de búsqueda ${\displaystyle r(Q)}$

Salida: todos los objetos de la base de datos tales que ${\displaystyle d(Oj,Q)\leq r(Q)}$

{ sea el objeto padre del nodo N ; ${\displaystyle O_{p}}$  si  N  no es una hoja entonces { para cada  entrada ( ) en N ${\displaystyle O_{r}}$   hacer { si  ${\displaystyle |d(O_{p},Q)-d(O_{r},O_{p})|\leq r(Q)+r(O_{r})}$  entonces { Calcular ;  ${\displaystyle d(O_{r},Q)}$ si  ${\displaystyle d(O_{r},Q)\leq r(Q)+r(O_{r})}$  entonces  RangeSearch (*ptr( )), Q , ); ${\displaystyle T(O_{r}}$ ${\displaystyle r(Q)}$  } } } de lo contrario { para cada  entrada ( ) en N ${\displaystyle O_{j}}$   hacer { si  ${\displaystyle |d(O_{p},Q)-d(O_{j},O_{p})|\leq r(Q)}$  entonces { Calcular ;  ${\displaystyle d(O_{j},Q)}$ si ≤  ${\displaystyle d(O_{j},Q)}$ ${\displaystyle r(Q)}$ entonces  agregar al resultado; ${\displaystyle oid(O_{j})}$ } } }}

• "←" denota asignación . Por ejemplo, " el elemento más grande ← " significa que el valor del elemento más grande cambia al valor del elemento .
• " return " finaliza el algoritmo y genera el siguiente valor.

• ${\displaystyle oid(O_{j})}$es el identificador del objeto que reside en un archivo de datos separado.
• ${\displaystyle T(O_{r})}$es un subárbol: el árbol que cubre ${\displaystyle O_{r}}$

a-Consultas NN

La consulta de k -vecinos más cercanos ( k -NN) toma la cardinalidad del conjunto de entrada como parámetro de entrada. Para un objeto de consulta dado Q ∈ D y un entero k ≥ 1, la consulta k -NN NN(Q, k) selecciona los k objetos indexados que tienen la distancia más corta desde Q, de acuerdo con la función de distancia d. ^[2]

Véase también

• Árbol de segmentos
• Árbol de intervalos : un árbol R degenerado para una dimensión (generalmente tiempo)
• Jerarquía de volumen delimitador
• Índice espacial
• Esencia
• Árbol de cobertura

Referencias

1. Ciaccia, Paolo; Patella, Marco; Zezula, Pavel (1997). "M-tree An Efficient Access Method for Similarity Search in Metric Spaces" (PDF) . Actas de la 23.ª Conferencia VLDB Atenas, Grecia, 1997 . IBM Almaden Research Center: Very Large Databases Endowment Inc. pp. 426–435. p426 . Consultado el 7 de septiembre de 2010 .
2. P. Ciaccia; M. Patella; F. Rabitti; P. Zezula. "Indexing Metric Spaces with M-tree" (PDF) . Departamento de Ciencias Informáticas e Ingeniería . Universidad de Bolonia. p. 3 . Consultado el 19 de noviembre de 2013 .