Algoritmos de búsqueda por proximidad
Cuándo |
05/03/2013 de 12:00 a 13:00 |
---|---|
Dónde | Salón "Graciela Salicrup" |
Agregar evento al calendario |
vCal iCal |
Resumen:
La búsqueda exacta consiste en localizar un objeto dentro de una colección. Es un problema fundamental en computación que está presente en prácticamente cualquier aplicación de computadora, desde bases de datos, minería, algoritmos numéricos, y un largo etcétera. Este problema acepta soluciones en tiempo constante, independiente del tamaño de la colección; es una de las razones de la super escalabilidad de la web.
Por otro lado, el problema de búsqueda por proximidad (encontrar un objeto "cercano" a uno dado en una colección) tiene instancias en las que no acepta siquiera soluciones sublineales y está detrás de aplicaciones como búsqueda multimedia, reconocimiento de patrones, búsqueda por contenido, detección de duplicados, clasificación y en general, aplicaciones en donde no tiene sentido comparar dos objectos de manera exacta.
Discutiremos el problema y algunas de las soluciones más ingeniosas que se han reportado en la literatura.