árbol M

Estructura de datos de árbol

En informática , los árboles M son estructuras de datos de árbol que son similares a los árboles R y B. Se construye utilizando una métrica y se basa en la desigualdad del triángulo para consultas de rango eficiente y k-vecino más cercano (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 evitarla mejor. Además, solo se puede utilizar para funciones de distancia que satisfacen la desigualdad del triángulo, mientras que muchas funciones de disimilitud avanzadas utilizadas en la recuperación de información no la satisfacen. ^[1]

Descripción general

M-Tree 2D visualizado usando ELKI . Cada esfera azul (hoja) está contenida en una esfera roja (nodos de directorio). Las hojas se superponen, pero no demasiado; Los nodos del directorio se superponen mucho más aquí.

Como en cualquier estructura de datos basada en árbol, el árbol M se compone 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 existe 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á como máximo a una distancia máxima de , y cada nodo y hoja con un nodo padre mantiene la distancia de él. ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle l}$ ${\displaystyle N}$ ${\displaystyle r}$ ${\displaystyle N}$ ${\displaystyle n}$ ${\displaystyle l}$ ${\displaystyle N}$

Construcción de árbol 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 principal de Node O _p .
2. Nodos de hoja
   1. Un conjunto de objetos N _O .
   2. Puntero al objeto principal de Node O _p .
3. Objeto de enrutamiento
   1. (Valor de característica de) objeto de enrutamiento O _r .
   2. Radio de cobertura r(O _r ).
   3. Puntero para cubrir el árbol T(O _r ).
   4. Distancia de O _r desde su objeto padre d(O _r ,P(O _r ))
4. Objeto
   1. (Valor característico 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 primero encontrar un nodo hoja N al que pertenece el nuevo objeto O. Si N no está lleno, simplemente conéctelo a N . Si N está lleno , invoque un método para dividir N. El algoritmo es como sigue:

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

  ${\displaystyle N_{e}\gets N}$objetos de enrutamiento u objetos si  N no es una hoja , entonces { /* Busca entradas en las que encaje el nuevo objeto */ sean objetos de enrutamiento del conjunto de objetos de enrutamiento  ${\displaystyle N_{in}}$ ${\displaystyle N_{e}}$ ${\displaystyle N_{RO}}$ de modo 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, 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 busca un objeto con una distancia mínima desde */ /* 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})}$ /* Actualiza 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}}$ demás { /* 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 un nuevo split en este nivel */ más { dividir ( ) ${\displaystyle N,O_{n}}$ } }

• "←" indica asignación . Por ejemplo, " mayor ← artículo " significa que el valor del mayor cambia al valor del artículo .
• " return " finaliza el algoritmo y genera el siguiente valor.

Dividir

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

División de algoritmo Entrada: Nodo N de 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 aquellos en el 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 principal de N ${\displaystyle O_{p}}$  sea el nodo principal 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 . Promover( ) ${\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 N y las entradas de 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 */  ${\displaystyle N_{p}}$ Cree una nueva tienda de nodo raíz y 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 */ Reemplace la entrada con la entrada en  ${\displaystyle O_{p}}$ ${\displaystyle O_{p1}}$ ${\displaystyle N_{p}}$ si no está completa , entonces ${\displaystyle N_{p}}$ { /* El segundo objeto de enrutamiento se almacena en el principal sólo si tiene capacidad libre */ Almacenar en ${\displaystyle O_{p2}}$ ${\displaystyle N_{p}}$ } demás { /*Si no hay capacidad libre, divide el nivel*/ dividir( ) ${\displaystyle N_{p},O_{p2}}$ } }

• "←" indica asignación . Por ejemplo, " mayor ← artículo " significa que el valor del mayor cambia al valor del artículo .
• " return " finaliza el algoritmo y genera el siguiente valor.

consultas de árbol M

Consulta de rango

Una consulta de rango es donde se especifica un valor mínimo de similitud/distancia máxima. Para un objeto de consulta determinado y una distancia de búsqueda máxima , el rango de consulta de rango (Q, r(Q)) selecciona todos los objetos indexados de manera que . ^[2] ${\displaystyle Q\in D}$ ${\displaystyle r(Q)}$ ${\displaystyle O_{j}}$ ${\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 pueden excluirse para conducir a objetos calificados.

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

Salida: todos los objetos de 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}}$   haz { 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)}$  } } } else { 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  suma al resultado; ${\displaystyle oid(O_{j})}$ } } }}

• "←" indica asignación . Por ejemplo, " mayor ← artículo " significa que el valor del mayor cambia al valor del artículo .
• " 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}}$

k -NN consultas

La consulta k -vecino más cercano ( k -NN) toma la cardinalidad del conjunto de entrada como parámetro de entrada. Para un objeto de consulta dado Q ∈ D y un número 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]

Ver también

• Árbol de segmentos
• Árbol de intervalos : un árbol R degenerado para una dimensión (normalmente tiempo)
• Jerarquía de volúmenes delimitadores
• índice espacial
• Esencia
• árbol de cobertura

Referencias

1. Ciaccia, Paolo; Patella, Marco; Zezula, Pavel (1997). "M-tree, un método de acceso eficiente para la búsqueda de similitudes en espacios métricos" (PDF) . Actas de la 23ª Conferencia VLDB Atenas, Grecia, 1997 . Centro de investigación de IBM Almaden: Very Large Databases Endowment Inc. págs. p426 . Consultado el 7 de septiembre de 2010 .
2. P. Ciaccia; M. Patella; F. Rabitti; P. Zezula. "Indización de espacios métricos con árbol M" (PDF) . Departamento de Ciencias e Ingeniería Informática . Universidad de Bolonia. pag. 3 . Consultado el 19 de noviembre de 2013 .