Uso eficiente de pivotes aplicado a la búsqueda aproximada en algoritmos rápidos sobre espacios métricos

Autores/as

  • Raisa Socorro Llanes Instituto Superior Politécnico José Antonio Echeverría
  • María Luisa Micó Andrés Universidad de Alicante

DOI:

https://doi.org/10.13053/cys-17-4-1364

Palabras clave:

Búsqueda aproximada, espacios métricos, vecino más cercano, distancias.

Resumen

El contexto de este trabajo es la búsqueda rápida de vecinos más cercanos en espacios métricos. Uno de los objetivos de estos algoritmos es la reducción del tiempo de respuesta durante la búsqueda. Reducir el tiempo de respuesta consiste muchas veces en reducir el número de distancias a calcular, debido al alto coste computacional que de por sí pueden tener las distancias a utilizar en ciertas aplicaciones. Nosotros proponemos una nueva versión y mejoras de un algoritmo recientemente publicado, PiAESA, variante del algoritmo AESA, usado como referencia en este área por sus buenos resultados desde hace más de 20 años. La nueva versión es más simple y permite una mejor comprensión del algoritmo y sus parámetros. Además, se ha conseguido aumentar la eficiencia definiendo una versión aproximada. Los resultados empíricos obtenidos utilizando datos artificiales y reales confirman una mejora en los resultados de la versión aproximada, con un alto porcentaje de una respuesta correcta (dada por un algoritmo exacto).

Biografía del autor/a

Raisa Socorro Llanes, Instituto Superior Politécnico José Antonio Echeverría

Es Ingeniera Informática y Master en Ciencias por el Instituto Superior Politécnico José Antonio Echeverría (CUJAE), Cuba. En estos momentos tiene más de 20 publicaciones, la mayoría de caracter internacional. Ha participado en más de 5 proyectos de investigación de caracter nacional y en 2 internacionales. Dirige el programa de Aplicaciones de Reconocimiento de Patrones en el Centro de Investigaciones de Tecnologías Integradas en la CUJAE y pertenece a la Asociación Cubana de Reconocimiento de Patrones. Su interés científico se centra en algoritmos de búsqueda por similitud, aprendizaje automático, procesamiento de imágenes y las aplicaciones de reconocimiento de patrones en general.

María Luisa Micó Andrés, Universidad de Alicante

Licenciada en Ciencias Físicas y Doctora en Informática por la Universidad Politécnica de Valencia. En estos momentos tiene 48 publicaciones, en su mayoría de ámbito internacional. Sus publicaciones han recibido más de 500 citas según el Google Scholar. Además, ha participado en 11 proyectos de investigación, de los cuales ha dirigido 3, y en las redes de excelencia PASCAL y PASCAL2 financiadas por la Unión Europea. Actualmente es miembro de la Junta Directiva de la Asociación Española de Reconocimiento de Formas y Análisis de Imágenes y coordinadora de uno de los Workpackages y miembro del Comité Técnico del proyecto CONSOLIDER INGENIO 2010 en el queparticipa. Es revisora habitual en revistas del campo de Reconocimiento de Formas y miembro del comité científico de varias conferencias relacionadas con el área. Su interés científico se centra en algoritmos de búsqueda por similitud, aprendizaje automático, optimización y definición de métricas y las aplicaciones de reconocimiento de formas a la sociedad de la información, el ámbito industrial y el de consumo.

Descargas

Publicado

2013-12-30

Número

Vol. 17 Núm. 4 (2013): 17(4) octubre-diciembre 2013

Sección

Artículos

Licencia

Transfiero exclusivamente a la revista “Computación y Sistemas”, editada por el Centro de Investigación en Computación (CIC), los Derechos de Autor del artículo antes mencionado, asimismo acepto que no serán transferidos a ninguna otra publicación, en cualquier formato, idioma, medio existente (incluyendo los electrónicos y multimedios) o por desarrollar.

Certifico que el artículo, no ha sido divulgado previamente o sometido simultáneamente a otra publicación y que no contiene materiales cuya publicación violaría los Derechos de Autor u otros derechos de propiedad de cualquier persona, empresa o institución. Certifico además que tengo autorización de la institución o empresa donde trabajo o estudio para publicar este Trabajo.

El autor, representante acepta la responsabilidad por la publicación del Trabajo en nombre de todos y cada uno de los autores.

Esta Transferencia está sujeta a las siguientes reservas:

  • Los autores conservan todos los derechos de propiedad (tales como derechos de patente) de este Trabajo, con excepción de los derechos de publicación transferidos al CIC, mediante este documento.
  • Los autores conservan el derecho de publicar el Trabajo total o parcialmente en cualquier libro del que ellos sean autores o editores y hacer uso personal de este trabajo en conferencias, cursos, páginas web personal, etc.