I'm looking to calculate the approximate intersection (proximity under a certain distance) of two sets of points in a discrete metric space. In other words, given a metric space $(M, d)$, subsets $A, B \subseteq M$, and maximum distance $k$, find $A' \subseteq A, B' \subseteq B$ where $A' = \{ x \in A | (\exists y \in B)[ d(x,y) \le k ] \} $, and same for $B'$.
One obvious way to do this is to put one set in a BK-tree, then simply iterate through each point in the second set and look up its neighbors in the first set's BK-tree. However, this becomes slow (and, I suspect, wasteful) when both sets are large.
Is there a faster way (such as calculating the intersection of two BK-trees directly)?
