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!