On the Complexity of Inner Product Similarity Join

Keyphrases

• Similarity Join 100%
• New Upper Bound 50%
• Asymmetric Embeddings 33%
• Inner Product 33%
• New Lower Bound 33%
• Recommendation System 16%
• Information Retrieval 16%
• Locality Sensitive Hashing 16%
• Tight 16%
• Distinct Element 16%
• Hardness Results 16%
• Linear Sketch 16%
• Subquadratic 16%
• Indexing Methods 16%
• Collision Probability 16%
• Record Linkage 16%
• System Linkage 16%
• Classification Information 16%
• Hardness of Approximation 16%
• Strong Exponential Time Hypothesis 16%

Computer Science

• Approximation (Algorithm) 100%
• Locality Sensitive Hashing 50%
• Record Linkage 50%
• Collision Probability 50%
• Indexing Method 50%
• Information Retrieval 50%

Mathematics

• Inner Product 100%
• Asymmetric 37%
• Lower and upper bounds 25%
• Main Result 12%
• Upper Bound 12%
• Probability Theory 12%
• Exponential Time 12%
• Distinct Element 12%