Un árbol de métricas es cualquier estructura de datos de árbol especializada para indexar datos en espacios de métricas . Los árboles métricos aprovechan las propiedades de los espacios métricos, como la desigualdad del triángulo, para hacer que el acceso a los datos sea más eficiente. Los ejemplos incluyen la M-árbol , vp-árboles , árboles de la cubierta , MVP árboles , y BK-árboles . [1]
Búsqueda multidimensional
La mayoría de los algoritmos y estructuras de datos para buscar un conjunto de datos se basan en el algoritmo de búsqueda binario clásico , y las generalizaciones como el árbol kd o el árbol de rangos 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 consultas de rango que solicitan cada punto que satisface y .
Una limitación de estas estructuras de búsqueda multidimensionales es que solo se definen para buscar objetos que pueden tratarse como vectores. No son aplicables para el caso más general en el que al algoritmo se le da solo 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 devuelva un valor que indique qué tan 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 un determinado imagen de consulta.
Estructuras de datos métricas
Si no hay 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 de la consulta con cada imagen del conjunto de datos [ cita requerida ] . Sin embargo, si la función de similitud satisface la desigualdad del triángulo, entonces es posible utilizar el resultado de cada comparación para podar el conjunto de candidatos que se examinarán.
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 por Jeffrey Uhlmann en 1991. [2] Otros investigadores estaban trabajando independientemente en estructuras de datos similares. En particular, Peter Yianilos afirmó haber descubierto de forma independiente el mismo método, al que llamó árbol de punto de vista (VP-tree). [3] La investigación sobre estructuras de datos de árboles métricos floreció a fines de la década de 1990 e incluyó un examen del cofundador de Google, Sergey Brin, sobre 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]
Implementaciones de código abierto
- Matlab : los árboles métricos se implementan en la
metricTree
clase que forma parte de la biblioteca gratuita de componentes de seguimiento del Laboratorio de Investigación Naval de los Estados Unidos . [5]
Referencias
- ↑ a b Samet, Hanan (2006). Fundamentos de estructuras de datos multidimensionales y métricas . Morgan Kaufmann. ISBN 978-0-12-369446-1.
- ^ Uhlmann, Jeffrey (1991). "Satisfacer consultas generales de proximidad / similitud con árboles métricos". Cartas de procesamiento de información . 40 (4). doi : 10.1016 / 0020-0190 (91) 90074-r .
- ^ Yianilos, Peter N. (1993). "Estructuras de datos y algoritmos para la búsqueda de vecinos más cercanos en espacios métricos generales" . Actas del cuarto Simposio anual ACM-SIAM sobre algoritmos discretos . Sociedad de Matemáticas Industriales y Aplicadas Filadelfia, PA, EE. UU. págs. 311–321. pny93 . Consultado el 7 de marzo de 2019 .
- ^ Brin, Sergey (1995). "Búsqueda de vecinos cercanos en grandes espacios métricos" (PDF) . 21ª Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB) .
- ^ "Biblioteca de componentes del rastreador" . Repositorio de Matlab . Consultado el 5 de enero de 2019 .