On the Complexity of Inner Product Similarity Join

Thomas D. Ahle, Rasmus Pagh, Ilya Razenshteyn +1

A number of tasks in classification, information retrieval, recommendation systems, and record linkage reduce to the core problem of inner product similarity join (IPS join): ident…