Algoritmos basados en pivotes

Los algoritmos que usan pivotes, son herramientas efectivas para búsquedas de proximidad en espacios métricos. Ellos permiten negociar entre el espacio ocupado y el número de cálculos de distancia desarrollados en tiempo de consulta.

Una vista abstracta de los algoritmos basados en pivotes es la siguiente. Seleccionamos un conjunto de pivotes {$p_1, ..., p_P$}. En tiempo de indexamiento, para cada elemento de la base de datos calculamos y guardamos $\Phi (a) = (d(a,p_1)...d(a,p_P))$. En tiempo de la consulta, dada una consulta $(q,r)_d$, calculamos $\Phi (q) = (d(q,p_1),...,(q,p_P))$. Ahora podemos descartar cada $a \in U$ tal que, para algún pivote $p_i$, $\mid d(q,p_i) - d(a, p_i) \mid > r$, o lo que es lo mismo, descartamos cada tal que

$\max_{1 \leq i \leq k} \mid d(q,p_{i}) - d(a, p_{i}) \mid = L_{\infty} (\Phi (a), \Phi(q)) > r$

Esto muestra que los algoritmos basados en pivotes pueden ser vistos como un mapeo $\Phi$ del espacio métrico original $(X, d)$ a un espacio vectorial -dimensional con la distancia $L_{\infty}$, es decir $(R^{P}, L_{\infty})$.

Los algoritmos kd-trees [Ben75] desarrollan una descomposición binaria jerárquica del espacio vectorial. Para cada nivel las ramificaciones izquierdas y derechas, cuentan con puntos a la izquierda o a la derecha de un umbral en una coordenada particular. Las coordenadas se alternan a cada nivel. Para espacios métricos generales la auscencia de coordenadas hizo urgente el diseño de reglas alternativas para descomposición de espacios y localización de objetos. Una familia entera de algoritmos son directamente descendientes de la estructura de los $kd$-trees. En lugar de usar las coordenadas directamente, estos algoritmos usan la distancia a un conjunto de objetos distinguidos de la base de datos llamados llaves, puntos ventajosos o pivotes. Combinando esto con la desigualdad del triángulo se obtiene una regla de descarte similar a la de los $kd$-trees.

La mayoría de los esquemas descendientes de los $kd$-trees son estructuras de datos basados en árboles que definen una descomposición jerárquica donde las celdas espaciales coinciden con las hojas en los árboles. Un ejemplo simple es el Burkhard-Keller Tree (BKT) [BK73], el cual es una estructura de datos diseñada para una función de distancia con valores discretos. Cada nodo del árbol corresponde a un pivote diferente, y cada rama descendiente está a cierta distancia desde . Esto es, todos los elementos a distancia $i$ de son puestos en el $i$-th subárbol del nodo correspondiente. Los subárboles son construídos recursivamente con la misma regla. Para una consulta $(q,r)_d$, descendemos en el árbol entrando sólo en los subárboles que cumplan con $(q,p)_d - r < (q,r)_d < (q,p)_d + r$, los otros elementos son descartados por la desigualdad del triángulo.