Conceitos
Indexação geoespacial hierárquica (S2/H3)
Intuição
Imagine dividir o mapa do mundo em grandes quadros numerados, depois cobrir cada quadro com quadros menores também numerados (que se encaixam exatamente ou quase), e assim por diante até chegar a pedaços menores que um metro quadrado. Em vez de anotar a posição exata de cada ocorrência, você anota só o número do pedaço onde ela caiu, e basta escolher o tamanho do pedaço para contar quantas ocorrências há em áreas do tamanho de um bairro, de uma cidade ou de um país. Como os pedaços têm tamanho e forma comparáveis e não mudam de lugar, as contagens de regiões diferentes podem ser comparadas entre si.
Como funciona
Em vez de guardar latitude e longitude, o sistema divide a Terra numa hierarquia de células e representa cada ponto pela célula em que ele cai, identificada por um inteiro de 64 bits. No S2, as seis faces de um cubo são projetadas sobre a esfera e cada célula é subdividida recursivamente em quatro filhas, do nível 0 ao 30; o identificador de uma célula de nível k tem 3 bits de face, k pares de bits que escolhem a filha, um bit 1 e zeros até completar 64 bits, e é numerado ao longo de uma curva que liga seis curvas de Hilbert, de modo que identificadores próximos correspondem a células próximas. Como no S2 cada quadrado se subdivide exatamente em quatro quadrados filhos (abertura 4), truncar um ponto indexado para a célula-mãe sempre o mantém dentro dela. O H3 monta a grade sobre as faces de um icosaedro, com hexágonos em resoluções de 0 a 15, e cada resolução usa abertura 7, ou seja, 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); como não se ladrilha o icosaedro só com hexágonos, cada resolução contém exatamente 12 pentágonos, e a resolução 0 tem 122 células-base. Hexágonos têm uma só classe de vizinhos, os que compartilham aresta, o que simplifica suavizações e convoluções porque basta contar a distância em células; mas não se subdividem exatamente em sete hexágonos, então no H3 a contenção lógica no índice é exata e a geométrica é aproximada. Uma região vira um conjunto de células de níveis diferentes: no H3, compactCells faz isso e, no exemplo do post da Uber, a Califórnia passa de 10.633 células na resolução 6 para 901 células de resoluções até 6, e uncompactCells recupera o conjunto original. No S2, permitir mais células aproxima melhor a região, ao custo de um conjunto maior. Quando a aplicação precisa de bordas exatas, a documentação do H3 sugere tratar a hierarquia como lógica e usar a grade como otimização antes de um teste preciso de ponto em polígono.
Na prática
O post de engenharia da Uber usa o H3 para agrupar em hexágonos os eventos do marketplace e medir oferta e demanda por célula, por exemplo para calcular preço dinâmico. A escolha entre os dois depende do que importa mais: o S2 oferece contenção exata entre níveis, enquanto o H3 oferece vizinhança uniforme, que simplifica suavizações e convoluções sobre células adjacentes. Em ambos, a resolução ou o nível define a granularidade da análise, e a cobertura de uma região por poucas células é barata, mas aproximada.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.