Efficient use of Pivots for Approximate Search in Metric Spaces

Authors

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

DOI:

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

Keywords:

Approximate search, metric spaces, near neighbor, distances.

Abstract

This work focuses on pivot-based fast nearest neighbor search algorithms that can work in any metric space. One of the objectives of these algorithms is to reduce the time consumed during search. Reducing time consumption of such algorithms usually consists in reducing the number of distances for computing, due to the high cost that they have in certain applications. We introduce a new version and improvements for a recently proposed algorithm, PiAESA, a variant of the AESA algorithm, used as baseline for performance measurement for over twenty years. The new version is simpler and allows better understanding of the algorithm and parameters used. Moreover, the efficiency is increased by defining an approximated version. Our empirical results with real and artificial databases confirm a consistent improvement in performance, when retrieving very high percentage of the correct answers (given by the exact algorithm).

Author Biographies

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

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.

Downloads

Published

2013-12-30

Issue

Vol. 17 No. 4 (2013): 17(4) October-December 2013

Section

Articles

License 

Hereby I transfer exclusively to the Journal "Computación y 
Sistemas", published by the Computing Research Center (CIC-IPN),
the Copyright of the aforementioned paper. I also accept that these 
rights will not be transferred to any other publication, in any other 
format, language or other existing means of developing.
I certify that the paper has not been previously disclosed or simultaneo
usly submitted to any other publication, and that it does not contain 
material whose publication would violate the Copyright or other 
proprietary rights of any person, company or institution. I certify that 
I have the permission from the institution or company where I work or 
study to publish this work.
The representative author accepts the responsibility for the publication
of this paper on behalf of each and every one of the authors. 
This transfer is subject to the following conditions:
  • The authors retain all ownership rights (such as patent rights) of this work, except for the publishing rights transferred to the CIC, through this document.
  • Authors retain the right to publish the work in whole or in part in any book they are the authors or publishers. They can also make use of this work in conferences, courses, personal web pages, and so on.
  • Authors may include working as part of his thesis, for non-profit distribution only.