| Participante | Papel |
|---|---|
| José Rafael Chachi Rodriguez | Backend |
| Joaquín Francisco Jordán O'Connor | Backend |
| Juan Diego Castro Padilla | Backend |
| Juan Diego Laredo Yarma | Frontend |
En este proyecto se nos ha pedido dar soporte a las búsquedas y recuperación eficientemente de datos multimedia, imágenes. Se utilizarán distintos algoritmos, además se apoyará de estructuras multidimensionales.
Aplicar los algoritmos de búsqueda y recuperación de la información para archivos multimedia aprendidos en clase.
- Utilizar métodos de indexación para hacer las búsquedas multimedia de manera eficiente.
- Crear una interfaz amigable para la realización de las consultas de imágenes.
El dataset utilizado son rostros de personas famosas de cualquier profesión. Nótese que una imagen no necesariamente contiene el rostro de solo 1 persona.
El archivo zip contiene lo siguiente:
|--- Aaron_Eckhart
| |--- Aaron_Eckhart_0001.jpg
|
|--- Aaron_Guiel
| |--- Aaron_Guiel_0001.jpg
...
...
...Es una carpeta de carpetas con los nombres de los rostros principales. Adicionalmente, dentro de cada carpeta existen entre 1 a más imágenes de rostro referentes al nombre de la carpeta.
Dataset extraído de Face Data.
La búsqueda secuencial, también llamada lineal, es la técnica utilizada al no implementar ningun tipo de indexación. Esta técnica es muy sencilla de implementar; sin embargo, estamos ejerciendo fuerza bruta al calcular la similitud (distancia) entre los datos lo cual lleva a una alta complejidad computacional. Se desarrolló la búsqueda lineal para que se pueda utilizar la búsqueda KNN y la búsqueda por rango basándose en los siguientes esquemas.
En ambas implementaciones calculamos la distancia de la query hacia todos los datos. En la búsqueda por rango se añade al resultado solo si la distancia calculada es menor a lo indicado. Mientras que para la búsqueda secuencial KNN, se utilizó una cola de prioridad y se añade al resultado solo si se encuentra una menor distancia calculada con respecto a las distancias dentro del heap.
La búsqueda KNN en el RTree se realiza utilizando una búsqueda con un rango inicialmente infinito y luego reduciendo este radio a la máxima distancia de los KNN según se evalúan los MBR hoja.
Por otro lado, la búsqueda por rango no se implementa como un método para el índice en la librería rtree de Python, pero se puede simular utilizando la búsqueda por intersección con el MBR {(x-r, y-r),(x+r,y+r)} donde (x,y) es el vector de consulta y luego filtrando aquellos puntos cuya distancia es menor al radio. Esta lógica se puede generalizar a N dimensiones sin ningún problema.
Faiss (Facebook AI Similarity Search) implementa la clase IndexLSH, que permite trabajar de forma eficiente la similitud entre vectores característicos de mayor dimensión. Para ello, el objetivo de esta técnica es asignar vectores característicos que tengan similitudes a los mismos buckets. Mientras que en una tabla hash tradicional el objetivo era minimizar las colisiones, en esta técnica se busca maximizar las colisiones siempre y cuando esta tenga sentido. LSH es usado tanto como para resolver el problema del vecino más cercano como para agrupación de datos. El algoritmo consta de las siguientes partes:
- Dividir los vectores en subpartes (bandas) y en lugar de procesar todo el vector en la funcion hash lo que se hace es pasar cada una de las bandas en la funcion hash.
- Si se tienen b subvectores, pueden usarse b funciones hash o una sola para elegir el bucket donde se asignara el subvector.
- La version mas flexible de este algoritmo indica que si existe una colision entre cualquier par de subvectores se consideran los vectores completos como posibles candidatos.
Desventajas:
- Pueden existir falsos positivos, puesto que el algoritmo considera como candidato un vector que tenga una subparte que colisione con la del input, pero puede que la mayor parte del vector en realidad no sea similar.
- Requieren muchas funciones hash para lograr resultados aceptables, lo que se traduce en memoria adicional.
- La función hash no está adaptada a los datos de entrada (es independiente de los datos). Esto lo vuelve mas sencillo y rapido, pero puede conducir a resultados de elección no tan óptimos en la práctica. En general los resultados son bastante buenos, pero puede darse el caso de que existan mejores.
El árbol-R es una estructura dimensional que agrupa sus elementos en distintos locaciones geográficas. Estas locaciones son fijadas de acuerdo a la dimensión indicada en el árbol. Es por ello que es recomendable aumentar la cantidad de dimensiones del árbol-R para tener los elementos similares agrupados disjuntos. Sin embargo, existe una situación en que si la dimensión es un número demasiado grande. Supongamos una query de un tamaño fijado. Si hacemos la búsqueda KNN en una dimensión, la distancia nos retorna un resultado. Si hacemos la misma consulta en un árbol de 2 dimensiones, la distancia se ve afectada y aumenta. Lo mismo sucederá si se sigue aumentando las dimensiones. En otras palabras, el cálculo de distancias depende de las dimensiones.
Fuente: https://medium.com/@nicolasarrioja/la-maldici%C3%B3n-de-la-dimensionalidad-f7a6248cf9a
| N | Seq | Rtree | HighD |
|---|---|---|---|
| 100 | 0.001 | 0.001 | 0.000 |
| 200 | 0.001 | 0.001 | 0.000 |
| 400 | 0.002 | 0.001 | 0.001 |
| 800 | 0.003 | 0.003 | 0.000 |
| 1600 | 0.006 | 0.005 | 0.000 |
| 3200 | 0.014 | 0.007 | 0.001 |
| 6400 | 0.038 | 0.022 | 0.001 |
| 12800 | 0.050 | 0.066 | 0.001 |
En el gráfico puede observar una mejora cuando se utiliza el RTree y no hay muchos datos; sin embargo, tomando más de 6400 datos, el rendimiento del RTree es peor que el de la consulta secuencial. También vemos que el índice que utiliza LSH supera a ambas técnicas de manera significativa. Esto tiene sentido, pues es una técnica especializada en manejar datos de alta dimensionalidad, como los vectores característicos de imágenes con los que se trabajó en este proyecto de dimensión 128.
-
De forma empirica se determino que el uso del RTree en algunos casos puede resultar en un rendimiento incluso peor que una busqueda sequencial, por lo que es conveniente saber en que casos utilizarlo para obtener buenos resultados.
-
Se concluye que el
IndexLSHes la mejor técnica utilizada en este proyecto por sus resultados indiscutiblemente mejores que las demas. -
Se pudo implementar una aplicacion funcional (de forma academica) que compara 3 metodos de busqueda para comparar su eficiencia, midiendo sus tiempos de ejecucion, y su eficacia, visualizando los resultados obtenidos por cada uno de ellos. Ademas, se cumplio con el objetivo de recuperar informacion relevante (top k) basandose en el contenido de la imagen enviada en la query.
| Joaquín Jordán | Juan Diego Castro | José Chachi | Juan Diego Laredo |
|---|---|---|---|
 |
 |
 |
 |
github.com/jjordanoc |
github.com/ByJuanDiego |
github.com/JoseChachi |
github.com/DarkNeSsJuaN25 |