Metode utilitare Java pentru geohashing.

Stare: productie , disponibil pe Maven Central

Rapoartele site-ului Maven sunt aici, inclusiv javadoc.

Adaugati acest lucru la pom:

<dependency> <groupId> com.github.davidmoten </groupId> <artifactId> geo </artifactId> <version> 0.7.1 </version> </dependency>

Note de lansare

  • 0.7 – imbunatatiri de performanta la GeoHash.encodeHash si altele (# 13), (# 14), multumesc @niqueco
  • 0.6.10 – compilat in java 1.6 pentru compatibilitate cu Android
  • 0.6.8 – obtineti clasa Pozitie din artefactul cu nucleul morocanos care include corectia Position.longitudeDiff.
  • 0.6.7 – Base32.encodeBase32 acum tamponeaza la lungimea maxima hash, ceea ce reprezinta o schimbare de rupere (# 9), multumesc @gnellzynga, utilizarea fixa ​​a DEFAULT_MAX_HASHES in doco (# 10).
  • 0.6.6 – remediaza # 8 calculele hashului la granita ar trebui sa se potriveasca cu implementarea de referinta geohash.org (multumesc DJ Hagberg)
  • 0.6.5 – remediaza problema # 6 GeoHash.coverBoundingBox nu reuseste atunci cand extinderea este mai mare decat cea acoperita de o singura litera hash
  • 0,6 – gestioneaza calculele vecinilor de la margini, elimina dependenta de guava, adaugari minore API
  • 0,5 – prima lansare pe Maven Central

Caracteristici

Cautari in casete de delimitare folosind geohashing

Care este problema?

Bazele de date ale evenimentelor la anumite momente care apar in anumite locuri de pe suprafata pamantului sunt susceptibile de a fi interogate in ceea ce priveste intervalele de timp si pozitie. O astfel de interogare este o interogare a casetei de delimitare care implica un interval de timp si o constrangere de pozitie definita de o caseta de delimitare lat-lunga.

Provocarea este de a face baza de date sa ruleze rapid aceste interogari.

Este posibil ca unele baze de date sa nu accepte sau sa sufere o degradare semnificativa a performantei atunci cand sunt interogate seturi de date mari cu conditii de inegalitate pe mai multe variabile.

De exemplu, o cautare a tuturor rapoartelor navei intr-un interval de timp si intr-o caseta de delimitare ar putea fi realizata cu o conditie de interval de timp combinata cu o conditie de interval pe latitudine combinata cu o conditie de interval pe longitudine ( combinata cu = AND logic). Acest tip de interogare poate functiona prost pe multe tipuri de baze de date, SQL si NoSQL. Pe Google App Engine Datastore, de exemplu, este permisa o singura variabila cu conditii de inegalitate pentru fiecare interogare. Acesta este un pas sensibil de facut pentru a indeplini garantiile de scalabilitate.

Ce este o solutie?

Interogarea casetei de delimitare cu un interval de timp poate fi rescrisa folosind geohashes, astfel incat o singura variabila sa fie supusa unei conditii de interval: ora. Metoda este:

  • stocati geohashes de toate lungimile (depinde de strategiile de indexare disponibile, un singur hash de lungime completa poate fi suficient) in campuri indexate in functie de fiecare pozitie lat lat din baza de date. Retineti ca stocarea hashurilor ca o singura valoare intreaga lunga poate fi avantajoasa (consultati Base32.decodeBase32 pentru a converti un hash intr-un long).
  • calculati un set de geohashes care acopera in intregime caseta de delimitare
  • efectuati interogarea folosind intervalul de timp si egalitatea fata de geohashes. De exemplu:
(startTime <= t <finishTime) si (hash3 = ‘drt’ sau hash3 = ‘dr2’)
  • filtrati rezultatele interogarii pentru a include numai acele rezultate in caseta de delimitare

Ultimul pas este necesar deoarece setul de geohashes contine caseta de delimitare, dar poate fi mai mare decat aceasta.

Ce lungime hash trebuie folosita?

Deci, cat timp ar trebui sa fie hashurile cu care incercam sa acoperim caseta de delimitare? Acest lucru va depinde de obiectivele dvs., care ar putea fi unul sau mai multe dintre minimizarea: procesorului, timpul de preluare a adresei URL, costul financiar, datele totale transferate de la depozitul de date, incarcarea bazei de date, incarcarea nivelului 2 sau o gramada de alte valori posibile.

Apelarea GeoHash.coverBoundingBox cu doar punctele de limitare si fara parametri suplimentari va returna hashuri de o lungime astfel incat numarul de hash-uri este cat mai mare posibil, dar mai mic sau egal cu GeoHash.DEFAULT_MAX_HASHES (12).

Puteti controla in mod explicit maxHashes apeland GeoHash.coverBoundingBoxMaxHashes.

Ca un exemplu rapid, pentru o caseta de delimitare proportionata mai putin ca un ecran cu Schenectady NY si Hartford CT in SUA la colturi:

Iata numarul de hash pentru diferite lungimi de hash:

m este dimensiunea in grade patrate a ariei totale hash si a este aria casetei de delimitare.

lungime num Hashes m / a 1 1 1694 2 1 53 3 4 6,6 4 30 1,6 5 667 1,08 6 20227 1,02

Doar testarea in baza de date si datele preferabil din viata reala vor determina care este valoarea maxima maxHashes. In sectiunea de referinta de mai jos, un test cu baza de date H2 a constatat ca timpul optim de interogare a fost cand maxHashes este de aproximativ 700. Ma indoiesc ca acest lucru ar fi cazul multor alte baze de date.

O explorare riguroasa a acestui subiect ar fi distractiv de facut sau de vazut. Spuneti-mi daca ati facut-o sau aveti un link si voi actualiza aceasta pagina!

Formule de inaltime si latime hash

Aceasta este relatia dintre un hash de lungime n si inaltimea si latimea acestuia in grade:

Mai intai definiti aceasta functie:

    paritate (n) = 0 daca n este chiar altfel 1

Atunci

    latime = 180/2 (5n + paritate (n) -2) / 2 grade

    inaltime = 180/2 (5n-paritate (n)) / 2 grade

Inaltimea si latimea in kilometri vor depinde de ce parte a pamantului este pe hash si pot fi calculate folosind Position.getDistanceToKm. De exemplu la (lat, lon):

double distancePerDegreeWidth = new Position (lat, lon) .getDistanceToKm (new Position (lat, lon + 1));

Repere

S-au inserat 10.000.000 de inregistrari intr-o baza de date de sistem de fisiere H2 incorporata care foloseste indexuri arborescente B. Inregistrarile au fost distribuite aleatoriu geografic intr-o regiune, apoi a fost aleasa o caseta de delimitare de 1/50 din zona regiunii. Interogare efectuata dupa cum urmeaza (timpul este timpul pentru a rula interogarea si a itera rezultatele):

hashLength num Hashes gasite din timp (uri) 2 2 200K 10m 56,0 3 6 200k 1,2m 10,5 4 49 200k 303k 4,5 5 1128 200k 217K 3,6 niciuna niciuna 200k 200k 31,1 (interogare cu mai multe domenii)

Am fost placut surprins ca H2 mi-a permis sa pun peste 1000 de conditii in clauza unde. Am incercat si cu urmatoarea lungime de hash mai mare, cu peste 22.000 de hash-uri, dar H2 a aruncat in mod inteles o StackOverFlowError.

Pentru a rula etalonul:

mvn clean test -Dn = 10000000

Rularea cu n = 1.000.000 este mult mai rapida si ruleaza acelasi rezultat primar:

interogarea cu mai multe raze este de 10 ori mai lenta decat cautarea prin geohash daca lungimea hash-ului este aleasa in mod judicios

Link-uri

  • Codul de codificare Geohash de baza a fost o traducere in java a https://github.com/davetroy/geohash-js/blob/master/geohash.js.
  • Implementarea imuabila a arborelui R in java de catre acelasi autor

ARTICOLE SIMILAREDE LA ACELAȘI AUTOR