Given thousands of points, such as city locations, how do we retrieve the closest points to a given query point? An intuitive way to do this is:
This is fine if we have a few hundred points. But if we have millions, these queries will be too slow to use in practice.
- Calculate the distances from the query point to every other point.
- Sort those points by distance.
- Return the first K items.
I had never had any need to dive into spatial search; this post is an excellent introduction. Deep yet approachable.Read more...