Introduction to Locality-Sensitive Hashing

Re:Introduction to Locality-Sensitive Hashing by IshKebab on Thursday June 24, 2021 @06:11PM (#27624505)

I can't see how LSH would be any faster for 2D/3D data than just sorting into regular X, Y buckets (like the first example). Surely this is only useful for high dimensional data?

[ Parent | on HN ]

Re:Introduction to Locality-Sensitive Hashing by bencoleman on Friday June 25, 2021 @02:28AM (#27627731)

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.

[ Parent | on HN ]