Definiciones

Espacios métricos y consultas de proximidad

A continuación se muestra la notación básica del problema de búsquedas, las cuales satisfacen la proximidad y el modelo usado [CNBYM99].

El conjunto $X$ denotará el universo de objetos válidos. Un subconjunto finito de ellos, $U$, de tamaño $n = \mid$U$\mid$, es el conjunto de objetos donde se aplicará la búsqueda. $U$ podría ser llamado diccionario, base de datos o simplemente nuestro conjunto de puntos. La función

$d : X \times X \rightarrow R$

Denotará una medida de distancia entre objetos (por ejemplo la distancia más pequeña, la más cercana o más similar a la que están los objetos). La función de distancia [NBY00] tiene las siguientes propiedades:

a) $\forall x,y \in X, d(x,y) \geq 0$ Positiva  


b) $\forall x,y \in X, d(x,y) = d(y,x)$ Simetrica  


c) $\forall x \in X, d(x,x)=0$ Reflexiva 


y en algunos de los casos 


d) $\forall x,y \in X, x \neq y \Rightarrow d(x,y) > 0$ Positividad estricta

Las propiedades de similaridad mencionadas arriba solo garantizan una definición consistente de la función y no pueden ser usadas para guardar comparaciones en una consulta de proximidad. Si $d$ es una distancia, y si satisface la desigualdad del triángulo, es decir,

e) $\forall x,y,z \in X, d(x,y) \leq d(x,z) + d(z,y)$

entonces el par $(X, d)$ es llamado un espacio métrico.

Si la función de distancia no satisface la propiedad de estrictamente positiva (d) entonces el espacio es llamado espacio pseudo-métrico Sin embargo por simplicidad no consideramos espacios pseudo-métricos en este trabajo, todas las técnicas presentadas son fácilmente adaptadas a ellos por sencillez identificamos todos los objetos a distancia cero son el mismo objeto, tomando en cuenta esto, tenemos que

$d(x, y) = 0 \Rightarrow \forall z, d(x,z) = d(y,z)$

Existen básicamente tres tipos de consultas de interés en espacios métricos

a) Consulta de rango o de proximidad.- La cual consiste en recuperar todos los elementos los cuales están dentro de una distancia $r$ de $q$. Esto es $\{ u \in U \mid d(q,u) \leq r \}$. Denotaremos esta consulta por $(q,r)_d$.

b) Consulta del vecino más cercano.- Este tipo de consulta recupera el elemento más cercano a $q$, en $U$, Esto es, $\{ u \in U \mid \forall v \in U, d(q,u) \leq d(q,v)$ } Podemos dar una distancia máxima r$\ast$ tal que si el elemento más cercano esta a una distancia mayor que r$\ast$ no queremos ningún reporte.

c) Consulta de los k-vecinos más cercanos.- En la cual se recuperan los $K$ elementos más cercanos a $q$ en $U$. Esto es, recuperar un conjunto $A \subset U$ tal que $\mid A \mid = k$ y $\forall u \in A, v \in U - A, d(q,u) \leq d(q,v)$.

El tipo básico de consulta es el correspondiente al inciso (a), en la figura se ilustra este tipo de consulta. Una consulta de proximidad será por lo tanto, un par $(q,r)_d$. El conjunto $\{u \in U, d(q,u) \leq r\}$ será llamado resultado de la consulta de proximidad.

Figura: Ejemplo de una consulta de rango (q) en un conjunto de puntos ( )

Existen otros dos tipos de consultas que son solucionados usando una variante de la consulta de rango. Por ejemplo, la consulta de tipo (b) la cual es normalmente solucionada con una consulta de rango donde el radio $r$ inicialmente es infinito y este es reducido con los elementos más cercanos a la consulta a medida que son encontrados. Normalmente se trata de obtener los elementos más cercanos tan rápido como sea posible (el problema es siempre más fácil para radios pequeños). El otro tipo de consulta (el tipo c) es normalmente solucionado como una variante del tipo (b), donde los $K$ elementos más cercanos son guardados y la $r$ activa es la distancia más larga de estos elementos a la consulta (Los elementos más lejanos no son de interés).

Es claro que cualquier tipo de consulta puede ser resuelta examinando el diccionario completo $U$. De hecho, si no pudiéramos preprocesar los datos, por ejemplo construir una estructura de datos indexada, entonces una examinación exhaustiva es la única manera de proceder. En nuestro modelo la función de distancia $d$ es costosa y por lo tanto, el número de cálculos de distancia procesadas será la medida de complejidad del algoritmo.

Ahora bien un algoritmo de indexamiento es un procedimiento independiente para construir una estructura de datos (o índice), diseñada para ahorrar cálculos de distancia cuando se responde a una consulta de proximidad. Esta estructura de datos puede ser costosa de construir, pero ahorrará cálculos de distancia sobre muchas consultas a la base de datos. Todos los algoritmos de indexamiento trabajan en base a descartar elementos usando la desigualdad del triángulo (de hecho la única propiedad para ahorrar cálculos de distancia).

Finalmente, el objetivo de este trabajo, es realizar un algoritmo que sea capaz de encontrar a todos los $K$ vecinos más cercanos, utilizando un índice de complejidad lineal en su construcción, y con esto reducir el número de cálculos de distancia, que se compara con la solución al problema aplicando fuerza bruta, el cual es resuelto usando $n^2$ cálculos de distancia.