Ricerca di prossimità

Question

In che modo un'applicazione esegue una ricerca di prossimità? Ad esempio, un utente digita un codice postale, quindi l'applicazione elenca tutte le aziende entro 20 miglia ordinate per prossimità.

Voglio creare qualcosa del genere in PHP e MySQL. Questo approccio è corretto?

1. Ottieni gli indirizzi delle località a cui sono interessato e memorizza nel mio database
2. Geocodifica di tutti gli indirizzi con il servizio di geocodifica di Google
3. Scrivi una query di database che includa la formula di Haversine per eseguire la ricerca e l'ordinamento di prossimità

Va ??bene? Nel passaggio 3, ho intenzione di calcolare la prossimità per ogni query. È meglio avere una tabella PROXIMITY che elenca la distanza tra ogni azienda e alcune posizioni di riferimento?

Answer 1

Se ci sono abbastanza record per la velocità che conta, ecco un modo per indicizzarli in anticipo.

Definisci una griglia di bidoni di circa 20 miglia su un lato. Memorizza il numero del cestino con ogni record del negozio. Al momento della ricerca, calcola il numero di tutti i contenitori che si intersecano in un raggio di 20 miglia dal punto di ricerca. Quindi recuperare tutti i negozi in uno di quei contenitori e procedere come prima.

Answer 2

Usiamo questo per fare molte migliaia di punti. È importante se lo stai eseguendo in SQL avere un indice sulla colonna Latitudine e Longitudine. Abbiamo provato a farlo in SQL 2008 con indici spaziali ma non abbiamo visto l'incremento prestazionale previsto. Tuttavia, se si desidera calcolare a una certa distanza da un ZIP, è necessario pensare se si intende utilizzare il centroide ZIP o una rappresentazione poligonale del codice postale.

Haversine forumla è un buon punto di partenza.

Non abbiamo avuto problemi di prestazioni nel calcolo della distanza al volo, la calcoliamo in anticipo per alcune applicazioni in cui conosciamo i punti in anticipo e ci saranno milioni di record.

SELECT
        [DistanceRadius]=
        69.09 *
        DEGREES(
          ACOS(
            SIN( RADIANS(latitude) )*SIN( RADIANS(@ziplat) ) 
           +
            COS( RADIANS(latitude) )*COS( RADIANS(@ziplat) ) 
           *
            COS( RADIANS(longitude - (@ziplon)) )
          )
        )
        ,*
        FROM
            table

    ) sub
WHERE
    sub.DistanceRadius < @radius

Answer 3

Lo facciamo per circa 1200 località. Vorrei solo usare la formula di Haversine al volo anche se a seconda dell'applicazione, potrebbe essere meglio memorizzarla in PHP anziché SQL. (La nostra implementazione è in .net quindi il tuo chilometraggio può variare).

Davvero il nostro più grande svantaggio con il modo in cui l'abbiamo implementato, è che ogni calcolo (fino a poco tempo fa) doveva essere calcolato sul livello dei dati che era dolorosamente lento (quando dico lento, intendo davvero non istantaneo ci è voluto un secondo o giù di lì), ma ciò era dovuto al fatto che doveva calcolare la distanza per tutte le 1200 località in base al codice postale fornito.

A seconda del percorso scelto, ci sono modi per velocizzare i calcoli della distanza numerica, osservando la longitudine e la latitudine e rimuovendo quelli al di fuori di un intervallo predefinito (ad esempio se si sta cercando tutto l'indirizzo entro 20 miglia c'è un intervallo di longitudine che puoi calcolare in cui tutti gli indirizzi devono rientrare a 20 miglia di distanza.) Ciò può accelerare la tua query se necessario.

Abbiamo effettivamente esaminato la memorizzazione di tutte le possibili combinazioni nel nostro database. In realtà sembra che potrebbe essere un grande archivio di dati, ma in realtà non è nel grande ambito delle cose. Con gli indici può essere abbastanza veloce e non devi preoccuparti dell'ottimizzazione dell'algoritmo ecc. Abbiamo deciso di non farlo, perché avevamo l'equazione in C # e ci ha permesso di memorizzare nella cache le informazioni necessarie per eseguire tutti i calcoli nel livello aziendale. Entrambi funzioneranno bene, è solo una questione di quale sia la tua preferenza.