1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

I think what you are trying to do is a kind of SPATIAL JOIN. A similar question has been answered here, albeit with a fixed size radius for returned points instead of asking for $k$ closest points.

I would suggest using a spatial index $L$. Then you can perform $k$-nearest neighbor queries on the index for each point. The complexity would be about or $O(|Q| * k * log |L|)$. I did some performance test of different spatial indexes here (Figure 28) with 2D and 3D datasets, you should be able to get around 100,000 $k$-nearest neighbor searches per second (on an index with 10,000,000 points). Some of these spatial indexes have updates rates of up to 1,000,000 updates per second, see Figure 40 in the same document. Especially quadtrees and the PH-Tree have high updates rates.

Not sure that it matters, but the PH-Tree uses internally z-curves (Morten order), which means that the ordering of elements uses z-order and is independent of insertion/deletion order. However, also note that the PH-Tree does not support duplicates, there can be only one point at any given coordinate.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.