Búsquedas en espacios métricos: árbol de aproximación espacial dinámico

Abstract

La búsqueda es un problema fundamental en Ciencias de la Computación, presente virtualmente en cada aplicación de computación. Las aplicaciones simples tienen problemas de búsqueda simples, mientras que las aplicaciones más complejas requerirán en general, una forma más sofisticada de búsqueda. Las bases de datos tradicionales se construyen basándose en el concepto de búsqueda exacta. Las consultas a la base de datos retornan todos aquellos registros cuyas claves coinciden con la aportada en la búsqueda. Las búsquedas mas sofisticadas como búsqueda de rangos sobre claves numéricas o búsqueda de prefijos sobre claves alfabéticas todavía se basan en el concepto que dos claves son o no son iguales, y en la existencia de un orden lineal sobre las claves de búsqueda. Actualmente las bases de datos han incluido la capacidad de almacenar nuevos tipos de datos tales como imágenes, sonido, video, etc.. Estos tipos de datos son difíciles de estructurar para adecuarlos al concepto tradicional de búsqueda. Así, han surgido aplicaciones en grandes bases de datos en las que se desea buscar objetos ,similares . Este tipo de búsqueda se conoce con el nombre de búsqueda aproximada o búsqueda por similitud, y surge en áreas tales como reconocimiento de voz, reconocimiento de imágenes, etc. La necesidad de una respuesta rápida y adecuada, y un eficiente uso de memoria, hace necesaria la existencia de estructuras de datos especializadas que incluyan estos aspectos.