When Hashes Met Wedges - A Distributed Algorithm for Finding High Similarity Vectors

Finding similar item pairs is a core task in recommendation systems. It can be expressed as finding large inner products in a collection of vectors, or large entries in a matrix product. This talk describes how randomized sampling ideas became a distributed algorithm used in Twitter’s production recommendation system. Existing approaches struggled with industrial-scale inputs containing hundreds of billions of nonzero entries. The algorithm combines low-dimensional projections, called hashes, with path-sampling techniques, called wedges. The presentation explains the mathematical ideas behind this combination and its application at production scale. Joint work with Aneesh Sharma of Twitter and Ashish Goel of Stanford.