Closest k points - performance on large lists

Question

Very similar to this

Problem formulation: Given a list $L$ of n points with GPS coordinates and a second list $Q$ of $m$ points, find the $k$ (let's say 3) closest points on $L$ for each element on $Q$.

Aditional constrains: Assuming that both $L$ and $Q$ are very large, and performance is an issue. We can also assume that $Q$ is much larger thant $L$. Preprocessing can be performed, but has to be robust to updates on lists $L$ and $Q$ (ergo, it can't be be very performance heavy).

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

If you can also point me out to implemented solutions on R or Python it would be great!