Qual è l'approccio migliore per trovare tutti gli indirizzi che si trovano a una distanza specifica dal punto selezionato

Question

Sto sviluppando un'applicazione che dovrebbe mostrare gli indirizzi che si trovano in una specifica distanza di una posizione. So come trovare la distanza tra due punti, ma il problema è che non sono sicuro quale sarebbe l'approccio migliore in termini di prestazioni.

Un modo è quello di recuperare tutti gli indirizzi e controllarli uno a uno verso l'indirizzo selezionato nel back-end ma esiste un modo per ridurre al minimo il numero di elementi che richiamo dal database, piuttosto che utilizzare la memoria? qual è l'approccio migliore per farlo e come?

Immagina di avere 300.000 record devo recuperarli tutti e calcolare la loro distanza dal punto selezionato? Come James ha suggerito che posso avere i record in diverse regioni e calcolare la distanza, quindi quale metodo sarebbe opportuno seguire, calcolo della distanza tramite query o Java?

public class Address{ 
    long Id; 
    Double latitude; 
    Double longitude; 
    .. 
    } 

Calculation

public static double distFrom(double lat1, double lng1, double lat2, double lng2) { 
    double earthRadius = 3958.75; 
    double dLat = Math.toRadians(lat2-lat1); 
    double dLng = Math.toRadians(lng2-lng1); 
    double sindLat = Math.sin(dLat/2); 
    double sindLng = Math.sin(dLng/2); 
    double a = Math.pow(sindLat, 2) + Math.pow(sindLng, 2) 
     * Math.cos(Math.toRadians(lat1)) *  Math.cos(Math.toRadians(lat2)); 
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
    double dist = earthRadius * c; 

    return dist; 
} 

This question e this one metodi offrono per calcolare la distanza attraverso il mysql, ma da che parte è meglio Java o mysql Sono abbastanza confuso.

Answer 1

Si potrebbe eseguire il calcolo lato server nella query stessa anziché lato client, recuperando quindi solo i risultati del calcolo. Here (archive link per i posteri) è un esempio di implementazione basata su Haversine in SQL (mi spiace, l'articolo è semplicemente troppo lungo per me copiare e incollare o riepilogare qui, sebbene sia un ottimo articolo e una lettura facile).

In alternativa, è possibile dividere il database in regioni (ad esempio un quadruplo di ordinamenti con coordinate polari) e recuperare solo le regioni vicino al punto, offrendo un sottoinsieme più piccolo da testare sul lato client. Allo stesso modo, è possibile calcolare un rettangolo di latitudine e longitudine in base alla distanza, con un indice di database su latitudine e longitudine e selezionare solo gli indirizzi in tale intervallo da considerare nei calcoli.

L'approccio di query è tuttavia un approccio più semplice e pulito, con buone prestazioni a causa del filtraggio iniziale della distanza. Farei l'approccio regionale solo se il primo non è possibile da implementare per qualche motivo.

Answer 2

Direi che l'approccio al database è il migliore in quanto non è necessario disporre di un'enorme memoria. È possibile utilizzare il seguente codice per recuperarli tramite ibernazione.

@Transactional 
public List<Double> getAllPoisAroundUser(double longitude, double latitude, int page) { 

Query query = getSessionFactory().getCurrentSession().createSQLQ uery("SELECT (6371 * 2 * ASIN(SQRT(POWER(SIN((:ulatitude - abs(latitude)) * pi()/180/2),2) +" + 
"COS(:ulatitude * pi()/180) * COS(abs(latitude) * pi()/180) *" + 
"POWER(SIN((:ulongitude - longitude) * pi()/180/2), 2))))*1000 as distance " + 
"FROM poi HAVING distance < 5000 ORDER BY distance"); 

query.setParameter("ulongitude", longitude); 
query.setParameter("ulatitude", latitude); 
query.setFirstResult((page-1)*10); 
query.setMaxResults(10); 

return (List<Double>) query.list(); 
} 

Answer 3

Quando ho implementato questo in MySQL (per la memorizzazione di luoghi su una sfera oblato, che è fondamentalmente ciò che la terra è (suppongo tu stia parlando di terra!)), Ho conservato il più pre-calcolato informazioni possibili nel database.Così, per una riga che memorizza latitude e longitude, ho anche calcolare al momento di inserimento i seguenti campi:

• radiansLongitude (Math.toRadians(longitude))
• sinRadiansLatitude (Math.sin(Math.toRadians(latitude))
• cosRadiansLatitude (Math.cos(Math.toRadians(latitude))

Quindi quando cerco i posti che si trovano entro X unità di latitude/longitude in questio n, la mia dichiarazione preparata è la seguente:

from Location l where 
    acos(
     sin(:latitude) * sinRadiansLatitude + 
     cos(:latitude) * cosRadiansLatitude * 
     cos(radiansLongitude - :longitude) 
     ) * YYYY < :distance 
    and l.latitude>:minimumSearchLatitude 
    and l.latitude<:maximumSearchLatitude 
    and l.longitude>:minimumSearchLongitude 
    and l.longitude<:maximumSearchLongitude 
    order by acos(
       sin(:latitude) * sinRadiansLatitude + 
       cos(:latitude) * cosRadiansLatitude * 
       cos(radiansLongitude - :longitude) 
     ) * YYYY asc 

Dove YYYY = 3965 ti dà distanze in miglia o YYYY = 6367 può essere utilizzato per le distanze in km.

Infine, ho usato le maximumSearchLatitude/maximumSearchLongitude/minimumSearchLongitude/maximumSearchLongitude parametri di escludere la maggior parte dei punti dal gruppo del risultato prima che il database deve eseguire calcoli. Potresti o non potresti aver bisogno di questo. Se lo usi, dipenderà da te quali valori sceglierai per questi parametri, poiché dipenderà da ciò che stai cercando.

Ovviamente sono necessarie applicazioni giudiziose degli indici nel database.

Il vantaggio di utilizzare questo approccio è che le informazioni che non cambia mai, ma è necessaria ogni volta che viene calcolato solo una volta, mentre il calcolo dei valori di radiansLongitude, sinRadiansLatitude, cosRadiansLatitude per ogni riga ogni volta che si esegue una ricerca sta per arrivare molto costoso molto veloce.

L'altra opzione è quella di utilizzare uno geospatial index, il che significa che tutto questo viene preso in carico dal database. Non so quanto bene Hibernate si integri con quello però.

Disclaimer: è da tanto che non guardo questo e non sono un esperto GIS!

Answer 4

Sto usando Hibernate e faccio in questo modo:

public List<Tour> searchTours(double lat, double lon, double distance) { 

    Session session = getSession(); 

    Criteria criteria = session.createCriteria(Tour.class, "tour"); 

    // 
    // 1 Grad lat = 111 km 
    // 1 grad lon = cos(lat) * 111 
    // 
    final double KM_IN_ONE_LAT = 111.0; 

    double t1 = distance/Math.abs(Math.cos(Math.toRadians(lat)) * KM_IN_ONE_LAT); 
    double t2 = distance/KM_IN_ONE_LAT; 

    double lonA = lon - t1; 
    double lonB = lon + t1; 

    double latA = lat - t2; 
    double latB = lat + t2; 

    Criterion c1 = Restrictions.between("longitude", lonA, lonB); 
    Criterion c2 = Restrictions.between("latitude", latA, latB); 

    criteria.add(c1); 
    criteria.add(c2); 

    criteria.setResultTransformer(Criteria.DISTINCT_ROOT_ENTITY); 

    return criteria.list(); 
} 

Scegli questa carta per ulteriori informazioni: Geo (proximity) Search with MySQL

Answer 5

Come precisa avete bisogno. L'utilizzo dell'indice GIS postgres o di un indice r-tree può essere utile come punto di partenza. Quindi eseguire una query del riquadro di delimitazione .. Quindi eseguire una distanza radiale sul client. In questo modo la matematica FP non viene eseguita dal server centrale (capacità di soffocamento). Il mio problema è che GIS e rtrees sono i tipi più lenti di indici (worsted solo da indici FTS). Quindi in genere ho optato per gli indici 1D come i geohash ... Se si dispone di dati punto, è sufficiente memorizzare tutto in un comune GSD (Ground Sample Distance), come 10 metri o 1 metro o what-have-you .. Si costruisce un ' stringa '(in genere codificata in base 64) che è la lat-long (ogni bit alterna lat e long). I punti sono memorizzati come un semplice indice di stringa nel DB (molto efficiente per l'indicizzazione e l'archiviazione). Quindi per le query, devi creare un riquadro di delimitazione da un punto di ricerca attraverso l'intervallo di geo-hash a cui sei interessato ... A meno che tu non abbia raggi molto grandi, questo dovrebbe restringere i risultati della ricerca ... Fai il filtrazione finale nel client (o utilizzando una delle tecniche elencate da altri per i valori trigonometrici precalcolati).

Il problema, tuttavia, è che passare da 1 M a punti è veloce.Fare 1.000 accessi al disco casuali è inutilizzabile. Quindi, anche se hai un bel geo-hash, se ha molti punti casuali; questo non funzionerà.

Quello che ho fatto in genere è di bin su disco tutti i blocchi dati rilevanti. Quindi una ricerca geografica ti dà un insieme finito di posizioni del disco ... Quindi carichi TUTTI i dati (più dozzine di MB) in un massimo di 4 carichi del disco. Quindi setacciare tutta la geometria. Questo può essere 1000 volte più veloce nel migliore dei casi (v. 1000 accessi al disco rand). Ma ovviamente ha dei seri limiti su come hai archiviato i dati in griglie in primo luogo (riscrittura totale o ridimensionamento fisso dei raccoglitori).

Ovviamente se si dispone di RAM sufficiente per memorizzare l'intero DB nella cache, quindi iniziare da lì. L'algoritmo non avrà più importanza. Innanzitutto pensa attraverso i modelli di accesso al disco. Quindi i modelli di accesso della CPU (è possibile ridimensionare le CPU, ma è difficile mantenere duplicati dei dati del disco).

Answer 6

Piano A: Poiché si dispone di 300K righe, INDICE (lat) è un non-starter, in termini di prestazioni, anche con limitazione a una striscia: AND lat BETWEEN 65 AND 69. INDEX(lat, lng) non è migliore poiché l'ottimizzatore avrebbe non utilizzare entrambe le colonne, anche con AND lng BETWEEN...

Plan B: Scelta successiva coinvolgerà lat e lng, più un subquery. E la versione 5.6 sarebbe utile. E 'qualcosa di simile (dopo aver incluso INDEX(lat, lng, id)):

SELECT ... FROM (
    SELECT id FROM tbl 
     WHERE lat BETWEEN... 
      AND lng BETWEEN...) x 
    JOIN tbl USING (id) 
    WHERE ...; 

Per varie ragioni, il Piano B è solo leggermente meglio di Piano A.

Piano C: Se avete intenzione di bisogno di milioni di righe, si vuole bisogno di my pizza parlor algorithm. Ciò comporta una stored procedure per sondare ripetutamente, cercando abbastanza righe. Coinvolge anche PARTITION per ottenere un indice 2D grezzo.

I piani A e B sono O(sqrt(N)); Il piano C è O(1). Cioè, per i piani A e B, se quadruplicate il numero di righe, raddoppierete il tempo impiegato. Il piano C non si rallenta man mano che aumenti N.

Answer 7

È possibile utilizzare la query non elaborata per selezionare l'elenco di moduli di identificazione tabella indirizzi in modalità di sospensione.

public List<Long> getNearByLocations(float latitude, float longitude, 
      float distance) { 
     Session sess = getSession(); 
     String queryString = "SELECT id, (6371 * acos (cos(radians(" 
       + latitude 
       + ")) * cos(radians(latitude)) * cos(radians(longitude) - radians(" 
       + longitude 
       + ")) + sin(radians(" 
       + latitude 
       + ")) * sin(radians(latitude)))) AS distance FROM Address HAVING distance < " 
       + distance + " ORDER BY distance"; 
     Query qry = sess.createSQLQuery(queryString); 

     List<Object[]> list = null; 
     list = qry.list(); 
     List<Long> idList = new ArrayList<>(); 
     for (Object[] obj : list) { 
      Long id = (Long) obj[0]; 
      idList.add(id); 
     } 
     return idList; 
    } 

Answer 8

Non è efficiente o scalabile interrogare l'intera tabella del database. Considerare l'utilizzo di R-tree per prestazioni migliori.