Árbol M

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

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. ${\estilo de visualización r}$ ${\estilo de visualización n}$ ${\estilo de visualización l}$ ${\estilo de visualización N}$ ${\estilo de visualización r}$ ${\estilo de visualización N}$ ${\estilo de visualización n}$ ${\estilo de visualización l}$ ${\estilo de visualización N}$

Construcción de árboles M

Componentes

Un árbol M tiene estos componentes y subcomponentes:

Nodos que no son hojas
1. Un conjunto de objetos de enrutamiento N _RO .
2. Puntero al objeto padre del nodo O _p .
Nodos de hojas
1. Un conjunto de objetos N _O .
2. Puntero al objeto padre del nodo O _p .
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 ))
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 $O_{n}$  
  Salida: Una nueva instancia de  $MT$  que contiene todas las entradas en  $el MT$  original más $O_{n}$

   $N_{e}\obtiene 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  $N_{in}$  $N_{e}$  $Estilo de visualización NRO$  de tal manera que  $d(O_{r},O_{n})\leq r(O_{r})$ 
       si  no está vacío entonces $N_{in}$ 
       {
          /* Si hay una o más entradas, entonces busque una entrada que esté más cerca del nuevo objeto */
           $O_{r}^{*}\obtiene \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 */
           $O_{r}^{*}\obtiene \min _{O_{r}\in N_{in}}d(O_{r},O_{n})-r(O_{r})$ 
          /*Actualizar los nuevos radios de la entrada*/
           $r(O_{r}^{*})\obtiene d(O_{r}^{*},O_{n})$ 
       }
       /*Continuar insertando en el siguiente nivel*/
       devolver insertar( );  $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( ) $N,O_{n}$  }
       /* El nodo está a plena capacidad, entonces es necesario hacer una nueva división en este nivel */
       de lo contrario 
       { dividir( ) $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: $Estilo de visualización N_{1}$ $Estilo de visualización N_{2}$ $Estilo de visualización N_{p}$ $Estilo de visualización N_{p}$ $Estilo de visualización N_{2}$

Algoritmo de división
  Entrada: Nodo  $N$  del M-Tree  $MT$  , Entrada $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 $N\cup O$ 
   
  {
     /*Obtener el nodo principal y el objeto de enrutamiento principal*/
     sea el objeto de enrutamiento padre de  $N$  $O_{p}$ 
      sea el nodo padre de  $N$  $Estilo de visualización 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( ) $Estilo de visualización O_{p1}}$  $Estilo de visualización O_{p2}}$  $N,O_{p1},O_{p2}$ 
  /* Elija qué objetos del nodo que se está dividiendo actuarán como nuevos objetos de enrutamiento */
  Partición( ) $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$  $Estilo de visualización N_{1}$  $Estilo de visualización 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  $Estilo de visualización N_{p}$ 
      y almacena en $Estilo de visualización O_{p1}}$  $Estilo de visualización O_{p2}}$  $Estilo de visualización N_{p}$ 
  }
  demás
  {
      /* Ahora use el objeto de enrutamiento principal para almacenar uno de los nuevos objetos */
      Reemplazar entrada con entrada en  $O_{p}$  $Estilo de visualización O_{p1}}$  $Estilo de visualización N_{p}$ 
      si  no está completo entonces $Estilo de visualización N_{p}$ 
      {
          /* El segundo objeto de enrutamiento se almacena en el padre solo si tiene capacidad libre */
          Guardar en $Estilo de visualización O_{p2}}$  $Estilo de visualización N_{p}$ 
      }
      demás
      {
           /*Si no hay capacidad libre entonces divide el nivel*/
           dividir( ) $Estilo de visualización 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 $Q\en D$ una distancia $r(Q)$ de búsqueda máxima , la consulta de rango range ( Q, r(Q)) selecciona todos los objetos indexados de manera $O_{j}$ que . [ 2 $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 rango
Entrada: Nodo  $N$  del M-Tree MT,    $Q$  : objeto de consulta, : radio de búsqueda
 $r(Q)$

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

{ 
   sea  el objeto padre del nodo  $N$  ; $O_{p}$  

  si   $N$  no es una hoja entonces { 
     para cada  entrada ( ) en  $N$  $O_{r}$    hacer {
           si  $|d(O_{p},Q)-d(O_{r},O_{p})|\leq r(Q)+r(O_{r})$   entonces { 
             Calcular ;  $d(O_{r},Q)$ 
            si  $d(O_{r},Q)\leq r(Q)+r(O_{r})$   entonces 
              RangeSearch (*ptr( )),  $Q$  , ); $T(O_{r}$  $r(Q)$  
          }
    }
  }
  de lo contrario { 
     para cada  entrada ( ) en  $N$  $O_{j}$    hacer {
           si  $|d(O_{p},Q)-d(O_{j},O_{p})|\leq r(Q)$   entonces { 
             Calcular ;  $d(O_{j},Q)$ 
            si  ≤  $d(O_{j},Q)$  $r(Q)$  entonces 
              agregar al resultado; $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.

$oid(O_{j})$ es el identificador del objeto que reside en un archivo de datos separado.
$T(O_{r})$ es un subárbol: el árbol que cubre $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

^ 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 .
^ ab 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 .

[p426-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 .

[Univ_Bologna_Range-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 .