Papers
Indexação geoespacial hierárquica: Google S2 Geometry e H3 da Uber
Isaac Brodsky (post de engenharia da Uber sobre o H3), Equipe do projeto S2 Geometry (documentação oficial), Equipe do projeto H3 (documentação oficial) · Fontes públicas não acadêmicas: blog de engenharia da Uber (H3: Uber's Hexagonal Hierarchical Spatial Index, 27/06/2018) e documentação oficial em s2geometry.io e h3geo.org (versão 4.x), 2018
O problema: agrupar eventos por localização em células de uma grade global
O post de engenharia da Uber sobre o H3 parte de uma necessidade prática: todo dia ocorrem milhões de eventos no marketplace, cada um num ponto específico, e é preciso extrair informação analisando uma cidade inteira. Analisar na granularidade máxima, o local exato de cada evento, é difícil e caro; analisar áreas, como bairros, é bem mais prático. A solução é um sistema de grade que agrupa eventos em células, por exemplo para medir oferta e demanda por hexágono e calcular preço dinâmico. Segundo o post, alternativas como áreas de código postal têm formas e tamanhos pouco úteis para análise e mudam por razões alheias ao uso, enquanto zonas desenhadas pelas equipes de operação exigem atualização frequente e definem bordas de modo arbitrário. Uma grade tem formas e tamanhos comparáveis entre cidades e não muda arbitrariamente. O post também descreve uma abordagem simples, uma projeção de mapa (como Mercator) com uma grade quadrada por cima, e aponta dois defeitos: a Mercator distorce muito o tamanho, de modo que células ficam com áreas bem diferentes, e quadrados têm dois tipos de vizinho, os que compartilham aresta e os que compartilham só um vértice, o que obriga a usar mais de um conjunto de coeficientes na análise. A documentação do S2 contrasta os sistemas de informação geográfica tradicionais, que representam os dados em projeções planas, com a abordagem do S2: representar tudo numa esfera, o que permite um banco de dados mundial sem costuras nem singularidades, com um único sistema de coordenadas.
S2: cubo projetado na esfera e identificadores ao longo de uma curva de Hilbert
Segundo a documentação do S2, a biblioteca decompõe a esfera unitária numa hierarquia de células. O nível mais alto vem de projetar as seis faces de um cubo sobre a esfera, e cada célula é subdividida recursivamente em quatro filhas. Cada célula é um quadrilátero limitado por quatro geodésicas. O nível é o número de subdivisões a partir da face e vai de 0 a 30; as menores, de nível 30, são chamadas células-folha, existem 6 vezes 4 elevado a 30 delas e cada uma tem cerca de 1 cm de lado na superfície da Terra. Pontos costumam ser representados por células-folha, e regiões, por coleções de células de níveis variados. Cada célula tem um identificador de 64 bits, o S2CellId, numerado ao longo de uma curva que liga seis curvas de Hilbert num único laço contínuo sobre a esfera. Por isso, se dois identificadores são próximos, as células também são próximas, o que melhora a localidade de referência na indexação. A estrutura do identificador de uma célula de nível k é: 3 bits de face, k pares de bits que escolhem a filha, um bit 1 e zeros até completar 64 bits. Assim, o nível se deduz da posição do bit 1 de menor ordem. Para deixar as células de tamanho mais uniforme na esfera, a biblioteca aplica uma transformação não linear entre as coordenadas (s, t) e (u, v) antes de projetar no globo.
H3: icosaedro, hexágonos, doze pentágonos e abertura 7
O H3 é descrito pela documentação como um sistema discreto de grade global, com ladrilhamento hexagonal em várias precisões e índices hierárquicos. A grade é construída sobre as faces planas de um icosaedro circunscrito à esfera, e as células são depois projetadas na superfície por uma projeção gnomônica inversa. O post da Uber justifica o hexágono assim: um hexágono tem uma só distância entre o centro e os de seus vizinhos, contra duas para quadrados e três para triângulos, o que simplifica a análise e a suavização de gradientes. Como não é possível ladrilhar o icosaedro apenas com hexágonos, cada resolução contém exatamente 12 pentágonos, um em cada vértice do icosaedro. O icosaedro é orientado pela orientação de Fuller, que, segundo a documentação, coloca os 12 vértices no oceano; o post diz que isso ajuda a evitar que pentágonos apareçam no trabalho da Uber. A resolução 0 tem 122 células-base, 110 hexágonos e 12 pentágonos. Cada resolução seguinte usa abertura 7: cada hexágono tem um sétimo da área do hexágono da resolução anterior (medida no icosaedro, antes da projeção na esfera). Há 15 resoluções mais finas além da 0, e a resolução 15 tem células com área inferior a 1 m². O índice é um inteiro de 64 bits, cujo campo de modo, para células, vale 1, e a conversão de latitude e longitude para índice recebe uma resolução entre 0 e 15.
Trade-offs: contenção exata ou aproximada, vizinhança e compactação de regiões
A documentação do H3 compara os dois sistemas. Ambos usam inteiros de 64 bits como índices de célula. O S2 usa abertura 4: um quadrado se subdivide exatamente em quatro quadrados filhos, então um ponto indexado e truncado para a célula-mãe sempre fica dentro dela. No H3 essa operação é aproximada, porque hexágonos não se subdividem exatamente em sete hexágonos; a contenção lógica no índice é exata, mas a geométrica é aproximada, e os limites das células em uma dada resolução não são afetados. Quando se precisam de bordas exatas, a documentação sugere tratar a hierarquia como lógica e usar a grade como otimização antes de um teste preciso de ponto em polígono. Por outro lado, quadrados têm duas classes de vizinhos, enquanto hexágonos têm uma só, a que compartilha aresta, o que simplifica convoluções e suavizações. Nas duas bibliotecas, uma região vira um conjunto de células de níveis diferentes. No H3, a função compactCells faz isso; no exemplo do post da Uber, a Califórnia, que na resolução 6 usa 10.633 células, fica com 901 células de resoluções até 6, e uncompactCells recupera o conjunto original. No S2, os exemplos de cobertura mostram o compromisso: com poucas células a cobertura de um círculo desperdiça área, e permitir mais células a aproxima melhor da região, e a documentação da hierarquia de células mostra o Havaí aproximado por 22 células.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.