Pinterest, Inc.
Balanced distribution of items in LSH mapping

Abstract:

Systems and methods are presented for efficient and effective computation of LSH hashing functions for use in various environments, including nearest-neighbor search. A corpus of items is maintained, with each item of the corpus being associated with information identifying one of a plurality of LSH partitions to which the item has been mapped or hashed. In response to an input item, the input item is projected one or more times into an orthoplex inscribed within a multi-dimensional space. For each mapping, a determination is made as to the nearest vertex of the orthoplex to the projected input item in view of determined offsets that provide for balanced distribution, and the LSH partitions associated with the nearest vertex are aggregated and associated with the input item as the input item's LSH partition.