algorithms – k nearest points – performance on large lists

Very similar to that

Formulation of the problem: From a list $$L$$
of n points with GPS coordinates and a second list $$Q$$ of $$m$$ points, find the $$k$$ (say 3) the nearest points on $$L$$ for each element on $$Q$$.

Additional constraints: Assuming both $$L$$ and $$Q$$ are very big, and performance is a problem. We can also assume that $$Q$$ is much bigger than $$L$$. Preprocessing can be done, but must be robust to list updates $$L$$ and $$Q$$ (ergo, it can not be very heavy in performance).

Problem extensions: If we can not have preprocessing, because the updates on $$L$$ and $$Q$$ are very common, what would be the solution?

If you could also report solutions implemented on R or Python, it would be great!