Algoritmos de pivotes

Una explicación intuitiva del problema del porque el problema se más difícil a medida que la dimensión crece esta dada en la sección , en esta sección se dará una medida para cuantificar la dimensión intrínseca [CN99].

Definición: La dimensión intrínseca de un espacio métrico esta definida como $\rho = \frac{\mu^2}{2\sigma^2}$, donde y son la media y la varianza del histograma de distancias correspondiente.

Obsérvese que la dimensión intrínseca crece con la media y con la inversa de la varianza de un histograma de distancias.

Si se pretende conocer el límite inferior de los algoritmos que usan pivotes, para conocer el desempeño del algoritmo, necesitamos relacionar la dimensión intrínseca con la dificultad de la búsqueda con un radio $r$ dado.

Sea $(q,r)_d$ una consulta de rango sobre un espacio métrico indexado por medio de $n_p$ pivotes aleatorios y sea $u$ un elemento de $U$. La probabilidad de que $u$ no pueda ser excluída desde una verificación directa después de considerar los $n_p$ pivotes es exactamente.

$$Pr ( \mid d(q, p_1) - d(u, p_1 \mid \leq r, ..., \mid d(q, p_{n_p}) - d(u, p_{n_p})\mid \leq r)$$ (C.1)

Puesto que todos los pivotes es asumido que son aleatorios y sus distribuciones de distancia variables aleatorias, esta expresión es el producto de probabilidades.

$$Pr ( \mid d(q, p_1) - d(u, p_1 \mid \leq r) \times ... \times Pr(\mid d(q, p_{n_p}) - d(u, p_{n_p})\mid \leq r)$$ (C.2)

las cuales, por la misma razón puede ser simplificado a

$Pr(u$ no descartado $) = Pr(\mid d(q,p) - d(u,p) \mid \leq r)^{n_p}$

para un pivote aleatorio .

Si $X$ y $Y$ son dos variables aleatorias con media y varianza , entonces la media de $X-Y$ es 0, y su varianza es $2 \sigma^2$. Usando la desigualdad de Chebyschev's tenemos que $Pr(\mid X- Y\mid > \varepsilon) < 2 \sigma^2 \varepsilon^2$. por lo tanto,

$Pr(u$ no descartados $) \leq \left( 1 - \frac{2 \sigma^2}{r^2} \right)^{n_p}$

Ahora tenemos que el costo total de la búsqueda es le número de cálculos de distancia internas ($n_p$) más los cálculos externos (aquellos a checar como candidatos), aquellos números es un promedio de $n \times Pr(u no descartados)$. Por lo tanto,

$$costo \geq n_p + n \left( 1- \frac{2 \sigma^2}{r^2} \right)^2$$ (C.3)

es un límite inferior del costo promedio de las búsquedas usando pivotes. Optimizando podemos obtener que el mejor número de pivotes es:

$$n_p = \frac{\ln n + \ln \ln (1/t)}{\ln (1 / t)}$$ (C.4)

donde $t = 1 - 2 \sigma^2/r^2$. Usando este número de pivotes $n_p$, obtenemos un límite inferior absoluto para el costo promedio de cualquier algoritmo basado en pivotes aleatorios.

$$costo \geq \frac{\ln n + \ln \ln (1/t)}{\ln (1 / t)} \geq \frac{\ln n}{ \ln (1/t)} \geq \frac{r^2}{2\sigma^2} \ln n$$ (C.5)

esto muestra que el costo depende fuertemente de $\sigma / r$. Si $r$ incrementa tiende a 1 y el esquema requiere más y más pivotes y por cualquier lado es mas y mas costoso.