Hardness of bichromatic closest pair with Jaccard similarity

DOI10.4230/LIPICS.ESA.2019.74MaRDI QIDQ5075822zbMATH OpenFDO

Authors Rasmus Pagh, Nina Mesing Stausholm, Mikkel Thorup

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1907.02251

zbMATH Keywords

bichromatic closest pairfine-grained complexityJaccard similarityset similarity search

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Set similarity search beyond MinHash
• On Finding the Jaccard Center
• Hardness of approximate nearest neighbor search
• The complexity of LSH feasibility
• Fingerprints for highly similar streams

Cites work

• scientific article; zbMATH DE number 7250154 (Why is no real title available?)
• An equivalence class for orthogonal vectors

Cited in

(1)

• scientific article; zbMATH DE number 7250154 (Why is no real title available?)

This page was built for publication: Hardness of bichromatic closest pair with Jaccard similarity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075822)