erock2112/CircleSMR_GPU — Issue #1: LSH KNN disagrees with our notion of distance
Author: erock2112
Created: 2012-03-04 20:55:07+00:00
State: open

LSH finds approximate nearest neighbors in d-dimensional space, without collision tests. We think of distance as the length of the path between two states, where distance is infinity for infeasible paths. Because of this, we have to discard infeasible neighbors after the LSH KNN runs. This results in very few of our neighbors being feasible, and the graphs are therefore sparse and often disconnected. Is there a better workaround than just using a higher K?