Ordenar un vector grande por distancia

Question

Muchas aplicaciones de citas clasifican los resultados por distancia. Eso es, estás en posición $(x, y)$ en el mapa de la Tierra y la aplicación te muestra hasta, digamos, $k$ potencial pareja. No se trata de cualquier persona, sino de la $k$ -más cercano a ti.

Si tengo un vector $v$ con $n$ pares $(x_i, y_i)$ indicando la posición de la gente, calculando la distancia desde mi posición $(x, y)$ a cada posición $(x_i, y_i)$ sería $\Theta(n)$ y seleccionando el $k$ más pequeño sería probablemente también $\Theta(n)$ (en el tiempo de ejecución, probablemente usando minicumuladores o algo parecido).

El problema es que $n$ puede ser enorme (imagina cuántos usuarios utilizan Tinder, Grindr y aplicaciones por el estilo).

Entonces, mi pregunta es, ¿cómo lo hacen tan rápido?

Answer 1

Como se insinuó en el comentario, agrupación es la clave. Un posible escenario podría ser el siguiente:

Cuando inicias la aplicación, ésta te coloca en un cubo (o papelera, o categoría, o como quieras llamarlo). El cubo da una pista sobre tu ubicación, por ejemplo, tu país, ciudad, etc. Esto ocurre con todos los usuarios, por lo que todo el mundo está ya preclasificado en un cubo (agrupación) y esto no debe ocurrir durante la búsqueda real. Ahora bien, cuando hay $N$ cubos con una media de $\bar n$ habitantes, entonces puede buscar primero el $K<<N$ cubos más cercanos a tu cubo, por ejemplo, tu propia ciudad y las más cercanas, y entonces sólo miras esos $\bar n K <<\bar nN=n$ nodos en su gráfico de distancia. Si este número sigue siendo demasiado grande (por ejemplo, una ciudad muy grande), puede considerar la posibilidad de elegir cubos más pequeños o agrupar los cubos también, por ejemplo, los distritos de la ciudad.

Encontrar el $K$ Los cubos más cercanos pueden tomar $\Theta(N)$ pero como los cubos representan ciudades u otras entidades inmutables, sólo se calculará una vez. Por lo tanto, no forma parte de la búsqueda interactiva. Ahora su búsqueda tarda $\Theta(\bar nK)$ pasos que es de esperar que sea mucho menor que $\Theta (n)= \Theta(\bar n N)$ .

Answer 2

Una estructura de datos muy aplicable a este tipo de problemas es el árbol k-d . (Creo que el artículo de la wiki lo explica lo suficientemente bien, pero comenta si tienes dudas). Si almacena sus datos posicionales en un árbol k-d, un búsqueda del vecino más cercano se convierte en $O(\log(n))$ .

No estoy seguro de si esto es precisamente lo que utilizan las aplicaciones de citas (probablemente sólo se agrupan por ciudad donde $n_{\text{city}}$ es lo suficientemente pequeño para la búsqueda bruta), pero los árboles k-d son comunes en el campo de la planificación del movimiento.