La estructura del FQA

Para empezar la descripción del FQA, primero asumiremos que las distancias son valores discretos. Para cada elemento de la base de datos, se guarda una lista de las distancias a los pivotes. En el FQA, esta lista es considerada como una secuencia de enteros. La estructura simplemente guarda los elementos de la base de datos ordenados lexicográficamente (obsérvese la figura , tabla ``a'' ) por esta secuencia de distancias, esto es, los elementos son primero ordenados por su distancia al primer pivote (columna 1 de la tabla ``a'', figura ), aquellos que tienen la misma distancia al primer pivote son ordenados por su distancia al segundo pivote (columna 2 de la tabla ``a'', figura )y así. A medida que más y más pivotes son agregadas el arreglo está y más ordenado.

El resultado del FQA tiene una fuerte relación al FHFQT (Fixed Height FQT, veáse la figura ) de altura . Si las hojas del FHFQT son recorridas en pre-orden, la salida es precisamente el orden impuesto en el FQA, más aún el algoritmo de búsqueda del FHFQT es inherente al FQA. Cada nodo del FHFQT corresponde a un rango de celdas en el FQA. Si un nodo desciende desde otro en el árbol, este rango es un subrango de otros en el arreglo. De aquí que, para cada vez, que el algoritmo del árbol se mueve desde un nodo a uno de sus hijos en el árbol, simulamos el movimiento en el arreglo, por búsqueda binaria al nuevo rango dentro del actual. Esta búsqueda binaria no desarrolla cálculos de distancia extra, solo compara secuencias de enteros. La complejidad de construcción es $O(Pn)$ cálculos de distancia más el tiempo para ordenar el arreglo lexicográficamente. Esto es $O(k$ log $n)$ [CMN99].

Para hacer una idea más clara, mostramos explícitamente el algoritmo de búsqueda. Dada una consulta $q$ a ser buscada con tolerancia $r$ y pivotes $p_1 ... p_P$, medimos $d_1 = (q, p_1), d_2=(q,p_2), d_n=(q,p_n)$. Ahora, para cada $i$ en el rango $d_i - r$ a $d_i + r$, hacemos una búsqueda binaria en el arreglo del rango donde la primer coordenada es $i$. Una vez que el rango es calculado, para cada $i$ continuamos recursivamente la búsqueda en el subarreglo encontrado, desde el pivote $p_2$. Esto es equivalente a recursivamente visitar en el $i^{esimo}$ nivel del subárbol en el FHFQT. La búsqueda termina cuando usamos los pivotes, y los puntos del subarreglo resultante son revisados secuencialmente. El procedimiento recursivo obviamente termina antes cuando el subarreglo resultante esta vacío.