M-árboles son estructuras de datos de árboles que son similares a R-árboles y los árboles 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 evitar la superposición. Además, solo se puede usar para funciones de distancia que satisfacen la desigualdad del triángulo, mientras que muchas funciones avanzadas de disimilitud utilizadas en la recuperación de información no satisfacen esto. [1]
Descripción general
Como en cualquier estructura de datos basada en árboles, M-Tree 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 hay un radioque define una bola en el espacio métrico deseado. Por lo tanto, cada nodo y hoja residiendo en un nodo en particular está a la mayor distancia de y cada nodo y hoja con el padre del nodo mantén la distancia de él.
Construcción M-Tree
Componentes
Un M-Tree tiene estos componentes y subcomponentes:
- Nodos no foliares
- Un conjunto de objetos de enrutamiento N RO .
- Puntero al objeto padre de Node O p .
- Nodos de hoja
- Un conjunto de objetos N O .
- Puntero al objeto padre de Node O p .
- Objeto de enrutamiento
- (Valor de característica de) objeto de enrutamiento O r .
- Radio de cobertura r (O r ).
- Puntero para cubrir el árbol T (O r ).
- Distancia de O r desde su objeto padre d (O r , P (O r ))
- Objeto
- (Valor de característica del) objeto O j .
- Identificador de objeto oid (O j ).
- Distancia de O j de 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 es completa, entonces simplemente adjuntarlo a N . Si N es completa, entonces invocar un método para dividir N . El algoritmo es como sigue:
Inserto de algoritmo Entrada: Nodo N de M-Tree MT , Entrada Resultado: Una nueva instancia de MT que contiene todas las entradas en MT original más
enruta objetos u objetos si N no es una hoja, entonces { / * Busque entradas en las que encaja el nuevo objeto * / dejar estar enrutando objetos desde conjunto de objetos de enrutamiento tal que Si no está vacío entonces { / * Si hay una o más entradas, busque una entrada más cercana al nuevo objeto * / } demás { / * Si no hay tal entrada, busque un objeto con una distancia mínima de * / / * el borde de su radio de cobertura hasta el nuevo objeto * / / * Actualiza los nuevos radios de la entrada * / } / * Continuar insertando en el siguiente nivel * / retorno inserto); demás { / * Si el nodo tiene capacidad, simplemente inserte el nuevo objeto * / si N no está lleno, entonces { store () } / * El nodo está a plena capacidad, entonces es necesario hacer una nueva división en este nivel * / else { dividir () } }
- "←" denota asignación . Por ejemplo, " más grande ← artículo significa" que el valor de los mayores cambios en el valor del elemento .
- " return " termina el algoritmo y genera el siguiente valor.
Separar
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 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 y almacenar estos nuevos nodos en el nodo principal de original de N . La división debe repetirse si no tiene suficiente capacidad para almacenar . El algoritmo es el siguiente:
División de algoritmo Entrada: Nodo N de M-Tree MT , Entrada Resultado: 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 { / * Obtener el nodo principal y el objeto de enrutamiento principal * / dejar ser el objeto de enrutamiento padre de N letser el nodo padre de N } / * Este nodo contendrá parte de los objetos del nodo a dividir * / Crea un nuevo nodo N ' / * Promocionar dos objetos de enrutamiento del nodo para que se dividan, para que sean nuevos objetos de enrutamiento * / Crea nuevos objetos y . Promover( ) / * Elija qué objetos del nodo que se está dividiendo actuarán como nuevos objetos de enrutamiento * / Dividir( ) / * Almacenar entradas en cada nuevo objeto de enrutamiento * / Tienda entradas en N y's entradas en N' si N es la raíz actual, entonces { / * Cree un nuevo nodo y configúrelo como nueva raíz y almacene los nuevos objetos de enrutamiento * / Crea un nuevo nodo raíz Tienda y en } demás { / * Ahora use el objeto de enrutamiento padre para almacenar uno de los nuevos objetos * / Reemplazar entrada con entrada en Si no está lleno entonces { / * El segundo objeto de enrutamiento se almacena en el padre solo si tiene capacidad libre * / Tienda en } demás { / * Si no hay capacidad libre, divida el nivel hacia arriba * / separar() } }
- "←" denota asignación . Por ejemplo, " más grande ← artículo significa" que el valor de los mayores cambios en el valor del elemento .
- " return " termina 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 máxima de búsqueda , el rango de consulta rango (Q, r (Q)) selecciona todos los objetos indexados tal que . [2]
El algoritmo RangeSearch comienza desde el nodo raíz y atraviesa de forma recursiva todas las rutas que no pueden excluirse de conducir a objetos calificados.
Rango de algoritmoEntrada: Nodo N de M-Tree MT, Q : objeto de consulta, : radio de búsqueda
Salida: todos los objetos DB tales que
{ dejar ser el objeto padre del nodo N ; si N no es una hoja, entonces { para cada entrada () en N hacer { si luego { Compute; Si luego RangeSearch (* ptr ()), Q ,); } } } else { para cada entrada () en N hacer { si luego { Compute; Si ≤ luego agrega al resultado; } } }}
- "←" denota asignación . Por ejemplo, " más grande ← artículo significa" que el valor de los mayores cambios en el valor del elemento .
- " return " termina el algoritmo y genera el siguiente valor.
- es el identificador del objeto que reside en un archivo de datos separado.
- es un subárbol - el árbol que cubre de
consultas k-NN
K La consulta del 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 entero k ≥ 1, la consulta k-NN NN (Q, k) selecciona los k objetos indexados que tienen la distancia más corta de Q, de acuerdo con la función de distancia d. [2]
Ver también
- Árbol de segmentos
- Árbol de intervalo: un árbol R degenerado para una dimensión (generalmente tiempo).
- Jerarquía de volumen delimitador
- Índice espacial
- Esencia
Referencias
- ^ 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 23a Conferencia VLDB Atenas, Grecia, 1997 . IBM Almaden Research Center: Very Large Databases Endowment Inc. págs. 426–435. p426 . Consultado el 7 de septiembre de 2010 .
- ^ a b P. Ciaccia; M. Patella; F. Rabitti; P. Zezula. "Indexación de espacios métricos con árbol M" (PDF) . Departamento de Ingeniería y Ciencias de la Computación . Universidad de Bolonia. pag. 3 . Consultado el 19 de noviembre de 2013 .