Fast road snapping for big data

Question

I hope this question is not too general. I'm dealing with a lot of data from vehicles (1.000.000 GPS points per day) and I want to snap the data to a big city's street network. The timely order is not so important, so I don't need corrective filtering using HMM like in other implementations. I just need to snap the point to the nearest road.

I want to use Spark (pySpark) for this Problem and have

• gps_df: lons and lats
• edges_df: road network as shapely LineStrings (each Road is a new line and loaded as WKT to the DataFrame)

My first try was using osmnx using the get_nearest_edge function, which is way too slow for the amount of GPS points.

Now I want to do this completely in Spark to make it fast and running parallel, but don't know where to start. Do I need kdtree? Which algorithm to chose (should I use shapely's nearest_point, which uses rtree according to another post, or kdtree which is faster, or completely build it myself)?

Answer 1

There are several projects, of various age and support status that make this faster:

• GeoSpark, https://datasystemslab.github.io/GeoSpark/

• SparkGIS, https://github.com/drubbo/SparkGIS

• Magellan, https://github.com/harsha2010/magellan

Each of them accelerates spatial join, making such queries much faster, and should run them reasonably fast. You did not say how big is your city network (number of edges), but 1M points is not that much for optimized join (I've more experience with Google BigQuery though, did not try this with Spark).