Hashing-Funktionen für GIS-Daten

8

Ich möchte Geometrien aus einem Vektordatensatz nehmen und sie auf einen Hash reduzieren. Dieser Hash würde dann verwendet, um die Integrität dieser Daten zu überprüfen und auch identische Geometrien zu identifizieren.

Gibt es geeignete Algorithmen, die verwendet werden könnten? Auf welche Fallstricke könnte ich stoßen?

vector algorithm Matthew Snape
quelle
4
Vielleicht interessiert Sie mein Artikel über Vektor-Steganographie (im Directions Magazine), in dem Sie einen Überblick über einige der Probleme einer eng verwandten Anwendung erhalten, nämlich das Ausblenden von Nachrichten in Vektordaten.
whuber
Was müssen Geometrien alles erfüllen, um als gleich zu gelten? Wenn keine Rotation erforderlich ist, können Sie zunächst WKB betrachten und erweitern, um übersetzte Geometrien zu vergleichen.
Lynxlynxlynx
"Das Einfachste, was möglicherweise funktionieren könnte" wäre die Verwendung eines Standard-Hash (z. B. CRC32 oder MD4, wenn Sie keine Sicherheitseigenschaften benötigen, oder eines SHA256, wenn Sie eine oder mehrere Sicherheitseigenschaften benötigen). Wie lynxlynxlynx jedoch betonte, sind Geometrien Gleitkommadaten, daher müssen Sie beim Vergleich auf "Gleichheit" vorsichtig sein.
BradHards

Antworten:

4

und identifizieren auch identische Geometrien.

Sie können sich bei der Identifizierung nicht auf Hashcodes verlassen. Im Falle einer Hash-Kollision können Sie denselben Hashcode für verschiedene Objekte erhalten, sodass Sie für die Nachbearbeitung immer eine teurere Vergleichsmethode benötigen. Aber natürlich können Sie Ihre Hashing-Methode optimieren, um Hash-Kollisionen zu reduzieren.

Wenn Sie es einfach machen möchten, verwenden Sie einfach MD5 oder einen anderen Hash, aber Sie können die Wahrscheinlichkeit einer Hash-Kollision weiter verringern. Wenn Sie keine übersetzten oder gedrehten Geometrien haben und einen ganzzahligen Hashcode möchten, könnte Ihre Methode folgendermaßen aussehen:

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

Schauen Sie sich für die Geohash- Methode auch einen räumlichen Schlüssel ('binärer Geohash') an, der speichereffizienter und präziser ist, wenn die Bereichsgrenzen kleiner als die Weltgrenzen sind. Sie können auch einen Blick in meine Java-Implementierung werfen .

Sie können die Wahrscheinlichkeit einer Hash-Kollision noch weiter verringern, wenn Sie die Unterschiede der Punkte verwenden und einen Mittelpunkt berechnen :

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);
}

Um z. B. den Breitengrad in eine Ganzzahl umzuwandeln, können Sie Folgendes tun:

latAsInt = latitudeFloatValue * (Integer.MAX / 90)

Oder für den Längengrad:

lonAsInt = longitudeFloatValue * (Integer.MAX / 180)
Karussell
quelle
Ich gebe zu, dass ich kein Experte für Hashes bin, aber in der Praxis verlassen sich die Leute häufig auf Hashes zur Identifizierung - auch weil die Wahrscheinlichkeit, eine Kollision zu erhalten, so gering ist. Eine teurere Methode zur Identifizierung würde bessere Ergebnisse liefern, aber ich denke, Sie könnten auch einen Hashing-Algorithmus mit einem größeren Ergebnisraum (SHA1, SHA256) verwenden, um dies ebenfalls zu unterstützen. Ob der komplexere Vergleich zu diesem Zeitpunkt schnell genug mit dem Hashing wird oder nicht, weiß ich nicht.
Nicksan
Ich bin selbst kein Hash-Experte :)! und Sie haben in der Tat Recht, dass Kollisionen für SHA-1 (und sogar MD5) seltener sind. Ein Vorteil meiner spezifischen Hash-Berechnungen könnte jedoch sein (allerdings nicht getestet!), Dass sie schneller zu berechnen sind. Übrigens: Der Int-Hash-Wert kann auf ein langes oder sogar Byte-Array erhöht werden
Karussell