Papers › Fast Similarity Sketching
Fast Similarity Sketching
Søren Dahlgaard, Mathias Bæk Tejs Langhede, Jakob Bæk Tejs Houen, Mikkel Thorup
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We consider the Similarity Sketching problem: Given a universe [u] = {0,…, u-1} we want a random function S mapping subsets A⊆[u] into vectors S(A) of size t, such that the Jaccard similarity J(A,B) = |A∩B|/|A∪B| between sets A and B is preserved. More precisely, define Xᵢ = [S(A)[i] = S(B)[i]] and X = ∑_(i∈[t]) Xᵢ. We want E[Xᵢ]=J(A,B), and we want X to be strongly concentrated around E[X] = t ·J(A,B) (i.e. Chernoff-style bounds). This is a fundamental problem which has found numerous applications in data mining, large-scale classification, computer vision, similarity search, etc. via the classic MinHash algorithm. The vectors S(A) are also called sketches. Strong concentration is critical, for often we want to sketch many sets B₁,…,Bₙ so that we later, for a query set A, can find (one of) the most similar Bᵢ. It is then critical that no Bᵢ looks much more similar to A due to errors in the sketch. The seminal t×MinHash algorithm uses t random hash functions h₁,…, hₜ, and stores ( min_(a∈A) h₁(A),…, min_(a∈A) hₜ(A) ) as the sketch of A. The main drawback of MinHash is, however, its O(t·|A|) running time, and finding a sketch with similar properties and faster running time has been the subject of several papers. (continued...)
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections