distance géodésique entre les visiteurs et le magasin le plus proche

Question

J'ai un grand jeu de données .csv contenant 10e7 points avec les coordonnées (latitude, longitude) représentant les emplacements des visiteurs. J'ai un autre ensemble de données contenant 10e3 points avec des coordonnées représentant les emplacements des magasins.

Je veux associer à chaque visiteur le magasin le plus proche, en utilisant une sorte de formule géodésique.

Je veux quelque chose de vraiment rapide et efficace, que je peux utiliser sur python (pandas par exemple) ou Google BigQuery.

Quelqu'un peut-il me donner un indice?

Answer 1

Pour ajouter à Felipe réponse:

Vous pouvez utiliser SQL UDF vs JS UDF
JS UDF ont une Limits que SQL UDF ne pas

donc équivalent UDF SQL vous peut utiliser avec le reste du code de Felipe est

CREATE TEMPORARY FUNCTION distance(lat1 FLOAT64, lon1 FLOAT64, lat2 FLOAT64, lon2 FLOAT64) 
RETURNS FLOAT64 AS ((
WITH constants AS (
    SELECT 0.017453292519943295 AS p 
) 
SELECT 12742 * ASIN(SQRT(
    0.5 - COS((lat2 - lat1) * p)/2 + 
    COS(lat1 * p) * COS(lat2 * p) * 
    (1 - COS((lon2 - lon1) * p))/2)) 
FROM constants 
)); 

J'ai essayé de conserver autant que possible la disposition de chaque UDF JS afin que vous puissiez voir comment elle est créée

Answer 2

Il s'agit d'une solution rapide qui trouve la station météorologique NOAA la plus proche pour 21 221 villes dans DBpedia (v2014).

#standardSQL 

CREATE TEMPORARY FUNCTION distance(lat1 FLOAT64, lon1 FLOAT64, lat2 FLOAT64, lon2 FLOAT64) 
RETURNS FLOAT64 
LANGUAGE js AS """ 

    var p = 0.017453292519943295; // Math.PI/180 
    var c = Math.cos; 
    var a = 0.5 - c((lat2 - lat1) * p)/2 + 
      c(lat1 * p) * c(lat2 * p) * 
      (1 - c((lon2 - lon1) * p))/2; 

    return 12742 * Math.asin(Math.sqrt(a)); // 2 * R; R = 6371 km 

"""; 

SELECT * 
FROM (
    SELECT city, country_label, distance, name weather_station, country, 
    RANK() OVER(PARTITION BY city ORDER BY distance DESC) rank 
    FROM (
    SELECT city, a.country_label, distance(a.lat,a.lon,b.lat,b.lon) distance, b.name, b.country 
    FROM (
     SELECT rdf_schema_label city, country_label, country, 
     CAST(REGEXP_EXTRACT(point, r'(-?\d*\.\d*)') as FLOAT64) lat, 
     CAST(REGEXP_EXTRACT(point, r' (-?\d*\.\d*)') as FLOAT64) lon 
     FROM `fh-bigquery.dbpedia2014temp.City` 
     WHERE point!='NULL' 
    ) a 
    JOIN (
     SELECT name, country, usaf, wban, lat, lon 
     FROM `bigquery-public-data.noaa_gsod.stations` 
     WHERE lat != 0.0 AND lon !=0.0 
    ) b 
    ON CAST(a.lat as INT64)=CAST(b.lat as INT64) 
    AND CAST(a.lon as INT64)=CAST(b.lon as INT64) 
) 
) 
WHERE rank=1 

Avertissements:

• Il utilise la formule de distance de https://stackoverflow.com/a/22476600/132438
• Optimise en limitant JOIN que par la recherche de stations dans la même INT (LAT), INT (LON) que la ville. Il est possible d'améliorer cela, mais je vais laisser cela pour une autre question.