Un árbol métrico es cualquier estructura de datos de árbol especializada para indexar datos en espacios métricos . Los árboles métricos explotan propiedades de los espacios métricos, como la desigualdad triangular, para que los accesos a los datos sean más eficientes. Algunos ejemplos incluyen el árbol M , los árboles vp , los árboles de cobertura , los árboles MVP y los árboles BK . [1]
La mayoría de los algoritmos y estructuras de datos para buscar un conjunto de datos se basan en el algoritmo de búsqueda binaria clásico , y las generalizaciones como el árbol kd o el árbol de rango funcionan intercalando el algoritmo de búsqueda binaria sobre las coordenadas separadas y tratando cada coordenada espacial como una restricción de búsqueda independiente. Estas estructuras de datos son adecuadas para problemas de consulta de rango que solicitan cada punto que satisface y .
Una limitación de estas estructuras de búsqueda multidimensionales es que solo están definidas para buscar objetos que se puedan tratar como vectores. No son aplicables para el caso más general en el que al algoritmo solo se le da una colección de objetos y una función para medir la distancia o similitud entre dos objetos. Si, por ejemplo, alguien creara una función que devolviera un valor que indicara cuán similar es una imagen a otra, un problema algorítmico natural sería tomar un conjunto de datos de imágenes y encontrar las que son similares según la función a una imagen de consulta dada.
Si no existe una estructura para la medida de similitud , lo mejor que se puede hacer es una búsqueda de fuerza bruta que requiera la comparación de la imagen consultada con cada imagen del conjunto de datos [ cita requerida ] . Sin embargo, si la función de similitud satisface la desigualdad triangular , entonces es posible utilizar el resultado de cada comparación para podar el conjunto de candidatos a examinar.
El primer artículo sobre árboles métricos, así como el primer uso del término "árbol métrico", publicado en la literatura abierta fue de Jeffrey Uhlmann en 1991. [2] Otros investigadores trabajaban de forma independiente en estructuras de datos similares. En particular, Peter Yianilos afirmó haber descubierto de forma independiente el mismo método, al que llamó árbol de puntos de vista (árbol VP). [3] La investigación sobre las estructuras de datos de árboles métricos floreció a finales de la década de 1990 e incluyó un análisis por parte del cofundador de Google, Sergey Brin, de su uso para bases de datos muy grandes. [4] El primer libro de texto sobre estructuras de datos métricas se publicó en 2006. [1]
metricTreeclase que forma parte de la biblioteca de componentes Tracker gratuita del Laboratorio de Investigación Naval de los Estados Unidos . [5]