Locality Sensitive Hashing

In the preceding chapter, we delved into algorithms that inferred the geometrical shape of a collection of vectors and condensed it into a navigable structure. In many cases, the algorithms were designed for exact top-k retrieval, but could be modified to provide guarantees on approximate search. This section, instead, explores an entirely different idea that is probabilistic in nature and, as such, is designed specifically for approximate top-k retrieval from the ground up.