Navegación

Búsqueda

Búsqueda avanzada

Resultados de búsqueda para espacios métricos

Reducción de la Complejidad Externa en Búsquedas por Similitud usando Técnicas de Clustering

La búsqueda por similitud tiene como finalidad determinar los objetos más semejantes o cercanos a uno dado. Los espacios métricos constituyen un modelo matemático que permite formalizar dicha búsqueda y que han dado lugar a diversos métodos, que tienen como objetivo principal reducir el número de evaluaciones de la función de distancia y el tamaño del índice. Las soluciones existentes son métodos basados en pivotes, que obtienen un número reducido de evaluaciones pero requieren cantidades importantes de espacio, y métodos basados en clustering, que necesitan poco espacio pero incrementan el número de evaluaciones. En este trabajo presentamos una nueva estrategia de clustering con sus algoritmos para búsquedas por rango y kNN que, reduciendo progresivamente el tamaño del cluster, disminuye significativamente la complejidad externa, un componente de la complejidad de los métodos existentes, con lo que se reduce el número de evaluaciones de la función de distancia.

Autores: Luis G. Ares / Nieves R. Brisaboa / Alberto Ordoñez / Oscar Pedreira / 
Palabras Clave: espacios métricos - Reducción de cluster - úsqueda por similitud

Una estructura Métrica Genérica para Búsquedas por Rango sobre una Plataforma Multi-GPU

Actualmente, la búsqueda por similitud en espacios métricos es de interés para la comunidad científica debido a sus múltiples campos de aplicacíon, como reconocimiento de patrones y recuperacíon de la información, entre otros. El uso de índices métricos proporciona un aumento en la eficiencia durante los procesos de búsqueda mediante la reduccíon del número de evaluaciones de distancia. Sin embargo, para aplicaciones reales donde el volumen de datos a procesar es masivo, el tiempo de resolucíon de una consulta es altamente costoso. En este sentido, el procesamiento paralelo permite disminuir los tiempos de búsqueda. Para este propósito, modernas plataformas basadas en GPU/multi-GPU proporcionan impresionantes ratios coste/rendimiento. En este artículo se presenta un análisis experimental de un conjunto de estructuras métricas en sus versiones secuenciales para posteriormente ser evaluadas bajo una plataforma basada en GPU. Finalmente la mejor alternativa es implementada sobre múltiples GPUs. Como conclusíon, una estructura métrica genérica presenta las mejores propiedades para este tipo de plataforma logrando rendimientos que superan en 32 veces los tiempos obtenidos con la mejor versíon secuencial.

Autores: Roberto Uribe-Paredes / Enrique Arias / Diego Cazorla / José L. Sánchez / 
Palabras Clave: Búsqueda por Similitud - espacios métricos - plataformas multi-GPU - procesamiento paralelo

No encuentra los resultados que busca? Prueba nuestra Búsqueda avanzada