¿Indexado espacial?

La base está en los datos

• Medición espacial
• Funciones espaciales
• Predicados espaciales
• Constructores de geometría
• Funciones observadoras

Tipos de indexado 😰

La herramienta correcta

• Representación eficiente de ubicación
• Búsqueda eficiente por proximidad
• Adaptable, fiable y agnóstico
• Dominio público

Photo by Ashim D’Silva on Unsplash

¿Qué es GeoHash?

Primero lo primero...

¿Qué es un hash?

GeoHash

• Es un algoritmo de codificación geográfica de dominio público creado por Gustavo Niemeyer (2008).
• Es una estructura de datos de jerarquía espacial que subdivide el espacio en regiones en forma de cuadrícula.
• Es una de las muchas aplicaciones de las curvas de órden Z y en general de las curvas de llenado de espacio.

Al César lo que és del César...

CTO @ Canonical

Parte del equipo de Canonical desde septiembre del 2005. Colaborador de proyectos como Landscape, Juju y Snap.

@gniemeyer

niemeyer.net

Otra vez... ¿qué era?

Es el algoritmo de una función hash que consume coordenadas geográficas (latitud, longitud), y produce hashes (cadenas de caracteres) de precisión variable que corresponden a esa ubicación.

¿Cómo por qué requiero precisión?

El algoritmo funciona subdividiendo el "mapa" y codificando la región resultante en una versión modificada de base32 (dígitos del 0 al 9 y el alfabeto en minúsculas, excluyendo [a,i,l,o]). Los geohashes representan regiones de un mapa, y la precisión juega un papel importante en la búsqueda por proximidad.

Ejemplo

Coordenadas: (20.644275, -103.415962)

1. 9  (23, -113)
2. 9e  (19.7, -107)
3. 9ew  (20.4, -103.4)
4. 9ewm  (20.65, -103.54)
5. 9ewmq  (20.632, -103.425)
6. 9ewmqw  (20.6461, -103.42)
7. 9ewmqwn  (20.644, -103.4164)

Algoritmo

Comenzamos con las coordenadas que queremos codificar. (20.644275, -103.415962)

Partimos el mapa en 2 por su longitud y tomamos la región que corresponde. 0 si es menor y 1 si es mayor.

Ahora partimos la sección por su latitud y tomamos región la que corresponde. 0 si es menor y 1 si es mayor.

Repetimos el algoritmo con la siguiente sección por longitud. (bits pares [0, 2, 4, 6, 8, ... ])

Y una vez más por latitud. (bits impares [1, 3, 5, 7, 9, ... ])

Con una última vez por su longitud juntamos 5 bits.

Y codificamos esos 5 bits en base32.

Continuamos con el proceso cuantas veces queramos hasta la precisión deseada.

Aproximadamente: ( 20.644 , -103.4164 )

¿Por qué usar GeoHash?

¡Véndemelo!

• Elegante y fácil de implementar
• Tamaño y eficiencia
• Búsqueda e indexado espacial
• Fácil de adaptar y compartir

Lugares cercanos

Regiones

¿y la famosa curva de órden-Z?

Problemas y soluciones

¿No que éramos vecinos?

La piedra en el zapato

• Búsqueda por región no siempre confiable


• Dimensiones variables de la cuadrícula

Photo by Matthew Hamilton on Unsplash

Y luego, ¿qué hago?

Photo by Nina Strehl on Unsplash

Búsqueda de vecinos (regiones adyacentes) por precisión variable.

9ewmt	9ewmw	9ewmx
9ewmm	9ewmq	9ewmr
9ewmj	9ewmn	9ewmp

Eficiente búsqueda espacial por proximidad con bases de datos.

¿Quién lo vistió mejor?

• Redis
• MongoDB
• Elasticsearch
• HBase
• Accumulo
• Etc...

Photo by Samuel Zeller Unsplash

Demo

Implementación del algoritmo

y servidor en Golang

Requisitos

• Ubicación
• Región
  • Centro
• Codificar
• Decodificar
• Vecinos
• Servidor
  • Guardar
  • Leer
  • Buscar región
  • Buscar vecinos

Photo by Chris Ried on Unsplash

Estructuras

type Location struct {
lat, lon float64
}

type Region struct {
min, max Location
}

func (r Region) Center() Location {
return NewLocation(
(r.min.lat+r.max.lat)/2,
(r.min.lon+r.max.lon)/2
)
}
			

Funciones

func Encode(latitude, longitude float64, precision int) string {
...
}

func Decode(geohash string) Region {
...
}

func Neighbours(geohash string) map[string]string {
...
}

func Validate(geohash string) bool {
...
}
			

Servidor

Construiremos una REST JSON API para una key/value store basada en geohash.

GET        /:geohash
POST       /:geohash
GET        /:geohash/region
GET        /:geohash/neighbours
OPTIONS    /:geohash*
-------------------------------
PUT        /:geohash
DELETE     /:geohash
			

¡La última y nos vamos!

¿Dónde la seguimos?

Photo by Jade Masri on Unsplash

• Distintas codificaciones y formatos
• Sistemas de coordenadas acotados o virtuales
• Otros sistemas (Open Location Code - Google Maps)

¿Para qué reinventamos la rueda?

https://github.com/mmcloughlin/geohash

• Soporte para geohashes base32 y enteros uint64
• Optimización en ensamblador para la plataforma más común (amd64)
• Pruebas, pruebas y más pruebas...

Geohash in Golang Assembly - Lessons in absurd optimization

¡Tan claro como un charco de lodo!

Photo by Camylla Battani on Unsplash

o... ¿a poco hay preguntas?

Gracias totales