Esta es una pregunta realmente interesante que podemos resumir en lo siguiente:
“¿Cómo indexa Google sus datos espaciales y geográficos?”
A lo que hay una respuesta bastante interesante llamada la celda S2:
- ¿Hay alguna lista de problemas de árbol AVL similares a los problemas de árbol binario de Stanford?
- ¿Cómo surgieron las estructuras de datos y los algoritmos?
- Entiendo cómo leer la recursividad pero no sé cómo resolverlos.
- ¿Qué algoritmos necesito aprender para resolver al menos 5 problemas en los concursos de CodeChef Long?
- Cómo hacer que esta declaración se entienda a un chico de 18 años
(crédito a Christian Perone por su excelente escrito: S2 de Google, geometría en la esfera, celdas y curva de Hilbert )
Entonces, ¿qué es una celda S2 y cómo nos ayuda a indexar el mundo? Básicamente, las células S2 rasterizan el mundo. Es decir, lo dividen en “píxeles” de resolución cada vez más alta al comenzar con una sola celda, subdividiéndola en celdas de grano más fino y repitiendo hasta que decidamos que nuestra resolución es lo suficientemente buena como para definir una ubicación distinta en la Tierra. En este punto, tu mente debería estar pensando que esto suena muy parecido a un árbol, y de hecho esa es una forma útil de pensarlo.
A partir de una celda S2 “hoja” (correspondiente a, por ejemplo, su ubicación actual). Podemos subir al árbol S2 para encontrar células vecinas. Al indexar lugares relevantes (por ejemplo, estaciones de servicio) por su celda S2, podemos consultar de manera rápida y eficiente las estaciones de servicio cercanas a la ubicación actual del usuario .
¿Cómo funciona esto debajo del capó?
Podemos representar una celda S2 individual en nuestro árbol con un entero de 64 bits como lo ilustra la siguiente imagen:
Para dar sentido a este formato, necesitamos entender dos cosas: las curvas de Hilbert y las seis caras de la Tierra .
Puede pensar en la curva de Hilbert como una cadena infinitamente larga que sigue el patrón de la imagen de arriba, pero con niveles de detalle cada vez más finos. Eventualmente, dada la longitud suficiente, la cuerda cubrirá cualquier posición en el espacio.
Pero la Tierra, por supuesto, no es un cuadrado, es un objeto esférico 3D. Para evitar esto, puede imaginarse encerrando la Tierra en un gran cubo que encierra su área:
(crédito a Sven Kreiss por su informe sobre las celdas S2: celdas S2 y curvas de relleno de espacio: claves para construir mejores herramientas de mapas digitales para ciudades )
Como puede ver en la imagen de arriba, ahora hemos proyectado seis cuadrados en la superficie de la Tierra, es decir, seis caras. Entonces, dada la cara del cubo y la posición en la curva proyectada, podemos representar cualquier posición en la Tierra con un solo entero de 64 bits.
¿Por qué pasar por todos estos problemas en lugar de usar un árbol KD u otra estructura de indexación espacial? ¡Para escalar, por supuesto! Estamos hablando de Google después de todo. Resulta que puede distribuir su índice mucho más fácilmente usando celdas S2 que una estructura de datos más compleja como un árbol KD. Esto se debe a que las celdas S2, a diferencia del árbol KD, son planas , a pesar de que podemos considerarlo como un árbol más jerárquico.
Por supuesto, hay un poco más que eso, pero te animo a que revises las reseñas de las fuentes vinculadas anteriormente para obtener más detalles.
