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)?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.