Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions Authors: Alexandr Andoni and Piotr Indyk
OK, I lied about the title.
You would think there would be short courses on title writing. Maybe I should start offering a one-day seminar in effective title writing.
Anyway, whatever the title issues, this is a deeply fascinating work on detection of nearest neighbors.
The short version is that really close neighbors bump into each other when hashing. So collisions become a way to detect neighbors. Rather clever.
I think of collisions as a basis for identify the same subjects.
Works in metric spaces but topic maps apply to metric spaces as well. After all, subjects are what define and occupy metric spaces.
For the longer explanation, read the paper.
[…] and Indyk aren’t any better with titles than they were in Whose Your Nearest Neighbor but here you will find additional information on their high dimension nearest neighbor algorithm as […]
Pingback by LSH Algorithm and Implementation (E2LSH) « Another Word For It — January 25, 2011 @ 10:57 am