I have two sets of lat/long points, $A$ and $B$. For each point $a$ in $A$, I want to find the corresponding closest point (by Haversine distance) $b$ in $B$. I'd like to use a space-partitioning tree, but as far as I can tell, quadtrees and k-d trees are confined to working in Euclidean space. How can I efficiently do a nearest-neighbor lookup in spherical space?
One solution I've considered is projection into 3d space and then using an octree, but I'd prefer not to do that if a space-partitioning tree (or alternative algorithm) that works with spherical coordinates directly exists.