Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search

Thomas Dybdahl Ahle, Jakob Bæk Tejs Knudsen

We formulate and optimally solve a new generalized Set Similarity Search problem, which assumes the size of the database and query sets are known in advance. By creating polylog co…