Funções de hash para dados GIS

8

Gostaria de pegar geometrias de um conjunto de dados vetoriais e reduzi-las a um hash. Esse hash seria usado para verificar a integridade desses dados e também para identificar geometrias idênticas.

Existe algum algoritmo apropriado que possa ser usado? Que armadilhas eu poderia encontrar?

vector algorithm Matthew Snape
fonte
4
Você pode estar interessado no meu artigo sobre esteganografia vetorial (na Directions Magazine) para obter uma visão geral de apenas alguns dos problemas envolvidos em um aplicativo intimamente relacionado, o de ocultar mensagens em dados vetoriais.
whuber
O que tudo que as geometrias precisam satisfazer para serem consideradas iguais? Se não houver rotação envolvida, você poderá começar examinando o WKB e estendendo-o para poder comparar as geometrias traduzidas.
Lynxlynxlynx
"a coisa mais simples que poderia funcionar" seria usar um hash padrão (por exemplo, CRC32 ou MD4 se você não precisar de propriedades de segurança ou um SHA256 se precisar de uma ou mais propriedades de segurança). Como lynxlynxlynx apontou, no entanto, as geometrias são dados de ponto flutuante, portanto, você deve ter cuidado com a comparação para "igualdade".
BradHards

Respostas:

4

e também identificar geometrias idênticas.

Você não pode confiar em códigos de hash para identificação. No caso de uma colisão de hash, você pode obter o mesmo código de hash para objetos diferentes; portanto, você sempre precisará de um método de comparação mais caro que o pós-processamento. Mas é claro, você pode ajustar seu método de hash para reduzir colisões de hash.

Se você quiser simplificar, use o MD5 ou qualquer hash, mas poderá reduzir ainda mais a probabilidade de uma colisão de hash. Se você não possui geometrias traduzidas ou rotacionadas e deseja um código de hash inteiro, seu método pode se parecer com:

int hash = numberOfPoints * 37;
hash += geometryType * 37;
...
for(point : points) {
     hash = hash XOR geohash(point.lat, point.lon)
}

Para o método geohash , observe também uma chave espacial ('binário geohash') que é mais eficiente em termos de memória e mais precisa se os limites da área forem menores que os limites do mundo. Você também pode dar uma olhada na minha implementação Java .

Você pode reduzir ainda mais a probabilidade de uma colisão de hash se estiver usando as diferenças dos pontos e calcular algum ponto central :

int hash = numberOfPoints;
hash += 37 * geometryType;
...
hash = hash XOR geohash(someCenterPoint.lat, someCenterPoint.lon);
for(point : points) {
   hash += 37 * latToInteger(previousPoint.lat - point.lat);
   hash += 37 * lonToInteger(previousPoint.lon - point.lon);
}

Para converter, por exemplo, a latitude em um número inteiro, você pode:

latAsInt = latitudeFloatValue * (Integer.MAX / 90)

Ou para a longitude:

lonAsInt = longitudeFloatValue * (Integer.MAX / 180)
Karussell
fonte
Admito que não sou especialista em hashes, mas, na prática, as pessoas geralmente confiam em hashes para identificação - em parte porque a probabilidade de obter uma colisão é muito baixa. Um método de identificação mais caro daria melhores resultados, mas acho que você também pode usar um algoritmo de hash com um espaço de resultados maior (SHA1, SHA256) para ajudar também. Se a comparação mais complexa se torna rápida o suficiente versus o hash nesse ponto, não sei.
Nicksan
Eu também não sou especialista em hash :)! e você está certo de que as colisões com o SHA-1 (e até o MD5) são raras. Mas uma vantagem de meus cálculos de hash específicos pode ser (ainda não testado!) Que eles são mais rápidos de calcular. Entre: o valor de hash int pode ser aumentada para uma matriz de bytes de comprimento ou mesmo
Karussell