Indexamiento

En esta sección se explicará como se realiza el indexamiento de la base de datos, es decir, la construcción del FQTrie; el modelo que se utilizó fue basado en el FQA y el modelo de un árbol, obteniendo una estructura la cual es una parte árbol y una parte arreglo. La implementación de este algoritmo es el siguiente:

Dado una base de datos con objetos (aleatorios) los cuales pueden ser palabras, imágenes, etc.; para construir la estructura del FQTrie se llevan acabo los siguientes pasos:

• Selección de pivotes.- Los primeros N objetos de la base de datos (aleatorios) los llamaremos pivotes y servirán para construir las firmas necesarias para la construcción del árbol. Véase la figura .

  Figura: Base de datos marcando la selección de los pivotes

  

• Cálculos de distancia a los pivotes.- Una vez que se seleccionaron los pivotes, se realiza el cálculo de distancia (en el apéndice se presenta un ejemplo de lo que podría ser un cálculo de distancia entre palabras) de cada uno de todos los pivotes a los elementos de la base de datos incluyendo a los pivotes restantes, para ilustrar este paso obsérvese la figura siguiente . Cada una de las distancias calculadas es almacenada (para cada pivote) conservando el número del elemento con el cual fue medido.

  Figura: Cálculo de distancia de un pivote a toda la Base de Datos (por simplicidad no se muestran todas la líneas)

  

• Generación de firmas.- Una vez que se tienen todos los cálculos de distancia de cada pivote, se ordenan estas distancias (para cada pivote), y se establecen $2^{bits}$ divisiones, lo que representa a generar $2^{bits}$ anillos en torno al pivote, obsérvese las figuras , , , , cada uno de estos anillos tiene una etiqueta asignada donde cada una de estas nuevas etiquetas (00, 01, 10,....) corresponden a los bits (el número de bits es uno de los parámetros dados por el usuario, por ejemplo, para la etiqueta 00 el parámetro fue 2 bits) que se escribirán en un byte para cada elemento. Cada elemento tiene un número de bytes destinado para almacenar la firma, el cual depende del número de pivotes y el número de bits. El diagrama de la firma para el punto $q$ de la figura se muestra en la tabla (usando 4 pivotes y 2 bits), donde los dos primeros $bits$ corresponden al anillo en el que se encuentra este elemento del pivote 1, los dos siguientes bits al pivote 2 y así sucesivamente, si el número de bits por el número de pivotes es mayor que 8, serán necesarios más de un byte para la firma (no aplica para el caso de ejemplo). Finalmente cuando se tienen ya estas firmas para cada elemento, se ordenan lexicográficamente y esto será utilizado en el siguiente paso.

  Figura: Construcción de la firma. En la figura se muestran los anillos generados para el pivote 1

  

  Figura: Construcción de la firma. En la figura se muestran los anillos generados para el pivote 2

  

  Figura: Construcción de la firma. En la figura se muestran los anillos generados para el pivote 3

  

  Figura: Construcción de la firma. En la figura se muestran los anillos generados para el pivote 4

  

  
  

  Tabla: Esquema del uso de un byte para almacenar una firma usando 4 pivotes y 2 bits

  01	01	10	10
  pivote 1	pivote 2	pivote 3	pivote 4

  
  

• Construcción del árbol.- Una vez que se tienen las firmas de todos los elementos y que éstas están ordenadas, la construcción del árbol se realiza de la siguiente manera. Para el primer nivel del árbol se toma en cuenta solo el pedazo de la firma correspondiente al primer pivote de todos los elementos (en la tabla corresponde a los dos primeros bits), es decir, todos los elementos que estén en el mismo anillo de un pivote estarán en la misma rama, para cada nivel del árbol se sigue este mismo procedimiento usando solo los siguientes pivotes, es decir, para el segundo nivel se usa el pivote 2 y así sucesivamente. Una vez que en alguna de las ramas, en cualquier nivel del árbol, solo queda un elemento, en esta rama se crea un arreglo con el resto de la firma de ese elemento. Para ilustrar esto obsérvese el ejemplo de la figura , una vez que se tiene construido el árbol, ya se pueden realizar consultas de la siguiente manera.

  Figura: Representación gráfica de un FQTrie (Fixed Query Trie).

• Recorrido en el árbol.- Dada una consulta $q$, antes de hacer el recorrido a través del árbol se calcula la firma de $q$ como se hizo para cada elemento de la base de datos. Inicialmente se tiene un radio $r$, así que se visitan solo aquellas ramas que cumplen con , donde $p_i$ es pivote correspondiente en un nivel del árbol. Una vez que se llega a una hoja se analiza la firma de $q$ contra la firma de la hoja es decir solo se comparan las dos firmas (que finalmente son solo secuencias de bits en un byte) y se determina si la firma del elemento(s) es próspera, de ser así, se calcula $q$ directamente contra ese elemento. Este procedimiento termina una vez que son recorridas todas la ramas potenciales.