Indices y particiones

Dado un conjunto $X$, una partición $\pi (X)=\{\pi_{1}, \pi_{2},...\}$ es un subconjunto del conjunto potencia $P(X)$ tal que cada elemento del conjunto pertenece exactamente a una partición, es decir, $\cup \pi_{i} = X$ y $\forall i \neq j,$ $\pi_{i} \cap \pi_{j} = 0$

Una relación, es denotada por $\sim$, es un subconjunto del producto cruz $X \times X$ (el conjunto de pares ordenados). Dos elementos $x,y$ se dice que están relacionados, denotado por $x \sim y$, si el par $(x,y)$ están en el mismo subconjunto. Una relación $\sim$ se dice que es una relación de equivalencia si satisface, para todo $x,y,z \in X$, las propiedades de:

a) $(x \sim x)$ Reflexividad 


b) $(x \sim y \Leftrightarrow y \sim x)$ Simetria


c) $(x \sim y \bigwedge y \sim z \Rightarrow x \sim z)$ Transitividad 

Se muestra que cada partición $\pi (X)$ induce una relación de equivalencia $\sim$ e inversamente cada relación de equivalencia induce una partición. Dos elementos están relacionados si ellos pertenecen a la misma partición [Chi95]. Cada elemento $\pi_{i}$ de la partición es entonces llamado una clase de equivalencia. Una clase de equivalencia es a menudo llamada representativa (cualquier elemento de $\pi_{i}$ puede ser tomado como un representativo). Una definición alternativa de una clase de equivalencia de un elemento $x$ es el conjunto de todos $y$ tales que $x \sim y$. Denotaremos la clase de equivalencia de $x$ como $[x]= \{y \colon x \sim y\}$.

Por ejemplo, dado un conjunto de números reales $R$, la relación $x \sim y \Leftrightarrow [x] = [y]$ es una relación de equivalencia. Un ejemplo de una clase equivalente en esta partición es el conjunto de todos los números reales tales que su suelo es uno. Las clases de equivalencia del número 1 ($[1]$) y del número 1.5 ($[1.5]$) son la misma (lo mismo ocurre en el intervalo entre los números 1 y 2 representado como $[1,2)$), hemos cambiado sólo su representación.

Dado un conjunto $X$ y una relación de equivalencia $\sim$, obtenemos el cociente $\pi(X) = X / \sim$. Esto indica que el conjunto de clases equivalentes o co-conjuntos, son obtenidos cuando aplicamos la relación de equivalencia al conjunto $X$. En el ejemplo citado, los co-conjuntos obtenidos de los números reales con la relación de equivalencia dado son los intervalos $[i, i+1)$, para todos los enteros $i$.

La relevancia de las clases de equivalencia en este trabajo viene de la posibilidad de usarlas en un espacio métrico así que el nuevo espacio métrico es derivado del conjunto cociente. Este nuevo espacio métrico es una versión engrosada del original.

Las clases de equivalencia obtenidas con una relación de equivalencia de un espacio métrico pueden ser consideradas por sí mismas como puntos en un nuevo espacio métrico, así que definimos una función de distancia en su nuevo espacio métrico.

Introducimos una nueva función $Do \colon \pi(X) \times \pi(X) \longrightarrow R$ definida ahora en el cociente. Dado que $Do$, está definida entre clases equivalentes, una selección natural es $Do([x],[y]) = \inf_{x\in[x],y\in[y]}\{d(x,y)\}$, así que esto da los valores máximos posibles que mantienen el mapeo contractivo (Por ejemplo $Do([x],[y]) \leq d(x,y)$ para algún $x,y$). Desafortunadamente, $Do$ no satisface la desigualdad del triángulo, solo las propiedades de positivo, positividad estricta y reflexividad. Por lo tanto, $Do$ por sí misma no es conveniente para propósitos de indexamiento.

Podemos usar cualquier distancia $D$ que satisfaga las propiedades del espacio métrico y su límite inferior $Do$ (Por ejemplo $D([x],[y]) \leq Do([x],[y])$). Llamamos $D$ la extensión de $d$. De aquí que $D$ es una distancia, $(X \mid \sim D)$ es un espacio métrico y sin embargo podemos hacer consultas en el co-conjunto de la misma manera que hemos hecho en el conjunto. Redefinimos la salida de una consulta en el co-conjunto como $([q],r)_{D}=\{u \in U, D([u],[q]) \leq r\}$ (aunque formalmente deberíamos recuperar las clases, no los elementos). Dado que el mapeo es contractivo $(D([x],[y]) \leq d(x,y))$ podemos convertir un problema de búsqueda en otro, esperemos que en un más simple. Para una consulta dada $(q,r)_d$ descubrimos cuales clases de equivalencia pertenecen al punto de consulta $q$ (por ejemplo $[q]$). Entonces, usando la nueva función de distancia $D$ la consulta es transformada en $([q],r)_D$. Como el mapeo es contractivo, tenemos $(q,r)_d \subseteq ([q],r)_D$. Esto es, $([q],r)_D$ es en efecto una lista candidata, así esto es suficiente para desarrollar una búsqueda exhaustiva en la lista candidata (ahora usando la distancia original), para obtener la salida real de la consulta $(q,r)_d$.

El procedimiento antes citado es de hecho usado en cada algoritmo de indexamiento. En otras palabras.

Todos los algoritmos de indexamiento para búsqueda de proximidad consisten en construir un conjunto de clases de equivalencia, descartando algunas clases, y buscando exhaustivamente en el resto.

En la figura podemos ver esquemáticamente un ejemplo de esta idea. Dividimos el espacio en varias regiones (clases de equivalencia). Los puntos dentro de cada región son indistinguibles. Podemos considerarlos como puntos en un nuevo espacio métrico. Para encontrar la respuesta, en lugar de examinar exhaustivamente el diccionario completo, solo examinamos las clases que contienen puntos potencialmente interesantes, en la imagen del lado derecho en la figura estas regiones de interés se muestran sombreadas. En otras palabras, si una clase puede contener un punto que debe ser regresado en la salida de una consulta, entonces la clase será examinada.

Figura: Modelo usado para indexar y consultar en espacio métricos