Talk to me about nearest neighbors

Hot Discussions Forum
1

Hey - this is for work.

20 years into my DS career … I am being asked to tackle a geospatial problem. In short - I need to organize data with lat long and then based on “nearby points” make recommendations (in v1 likely simple averages).

The kicker is that I have multiple data points per geo-point, and about 1M geo-points. So I am worried about calculating this efficiently. (v1 will be hourly data for each point, so 24M rows (and then I’ll be adding even more)

What advice do you have about best approaching this? And at this scale?

Where I am after a few days of looking around

  • calculate KDtree
  • Possibly segment this tree where possible (e.g. by region)
  • get nearest neighbors

I am not sure whether this is still the best, or just the easiest to find because it’s the classic (if outmoded) option. Can I get this done on data my size? Can KDTree scale into multidimensional “distance” tress (add features beyond geo distance itself)?

If doing KDTrees - where should I do the compute? I can delegate to Snowflake/SQL or take it to Python. In python I see scipy and SKLearn has packages for it (anyone else?) - any major differences? Is one way way faster?

Many thanks DS Sisters and Brothers…

4 Likes
2

Make sure you use haversine distance instead of Euclidean.

3 Likes
3

How come?, I don’t understand.:slightly_smiling_face:

3 Likes
4

How spatial distortions in your data, where points nearer the poles appear wider apart than those nearer the equator, can result from utilizing lat lon as x-y. The meaning of a feature that is defined as “local distance to point” will vary depending on the latitude.

Additionally, even if the distribution of your data is within a comparable latitude, the meaning of distance will differ. Your ‘distance’ feature may be biased N-S/E-W if you fail to account for great circle distance, since ∆lat 1 degree =/= ∆lon 1 degree.

2 Likes
5

Hey thanks for the great explanation! I’m taking a data science certificate right now and trying to break into the field. Learning about unstructured data and dimensionality reduction right now, and it’s very cool and helpful to engage with real world examples here

1 Like
6

The Earth is implied to be flat if Euclidean distance is used.

Haversine considers the radius of the Earth as a sphere.