yes, this is true. In 2D/3D, sorting into regular space partitions of exponentially decreasing size (e.g. KD-trees) is far more effective - roughly log(N) vs N^

yes, this is true. In 2D/3D, sorting into regular space partitions of exponentially decreasing size (e.g. KD-trees) is far more effective - roughly log(N) vs N^rho (rho < 1). In high dimensions, the simple partitioning strategy runs up against the "curse of dimensionality" which is where LSH starts to work better.