Pith. sign in

REVIEW 3 major objections 4 minor 41 references

Analysis of SparseHash: an efficient embedding of set-similarity via sparse projections

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read SparseHash proves that binary, sparse random projections can estimate the Jaccard coefficient between sets with a uniform concentration bound.

desk verdict The Fast SparseHash algorithm and the empirical comparison are genuinely useful, but Theorem 1's concentration bound is false as stated because it ignores the event that sim∪ equals zero; the theorem needs a non-degeneracy condition or a much stronger m. read the letter →

arxiv 1909.01802 v1 pith:XJ633ZN2 submitted 2019-09-02 cs.DS cs.CV

Diego Valsesia , Sophie Marie Fosson , Chiara Ravazzi , Tiziano Bianchi , Enrico Magli This is my paper · ORCID
classification cs.DScs.CV MSC 68P2068W20
keywords SparseHashJaccardcoefficientrandomprojectionsmatricessetsimilaritylocality-sensitivehashingbinaryembeddingsconcentrationinequalities
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

SparseHash is an embedding that turns a sparse signal or set into a short binary code and lets you estimate how similar two sets are by comparing those codes. The paper proves that when the code is produced by multiplying a set's indicator vector by a random matrix whose entries are mostly zero, a ratio of logarithms of zero-counts in the code concentrates around the true Jaccard coefficient of the two sets. The guarantee is uniform: for a collection of N sets with support sizes between k_min and k_max, a code length growing like log N is enough to keep every pairwise estimate within epsilon with high probability. This matters because the codes are one bit per measurement, cheaper to store than integer-valued MinHash sketches, and the paper also gives a fast hashing implementation with the same asymptotic cost as the MinHash bottom sketch.

What carries the argument

The load-bearing object is the gamma-sparsified random matrix A: each entry is zero with probability 1-gamma and otherwise drawn from any zero-mean, finite-variance distribution. Because rows are independent, a single measurement (Au)_i is zero exactly when every support element of u avoids the row's nonzero entries, which has probability (1-gamma)^{|supp(u)|}. Consequently, the empirical fraction of zero coordinates in a sketch estimates (1-gamma)^{|S|}; for two sets, the fraction of coordinates where both sketch bits are zero estimates (1-gamma)^{|S_u union S_v|}, while a product of individual zero-fractions divided by the both-zero fraction estimates (1-gamma)^{|S_u intersection S_v|}. Taking logarithms cancels the factor log(1-gamma), so the ratio simsh(y,z)=log(sim_intersection)/log(sim_union) targets the Jaccard coefficient directly. The proof converts these probability estimates into a uniform bound using a concentration inequality for sums of bounded random variables and a lemma showing that logarithms preserve concentration for positive variables.

What would settle it

Take any fixed set of k elements, hash each element many times with different seeds, and count the fraction of measurements whose hash falls below the threshold; if that fraction is not approximately (1-gamma)^k with binomially sized fluctuations, the implemented method does not match the random-matrix model and Theorem 1 does not guarantee the deployed algorithm.

Watch

Extended reading notes

Core claim

The central mathematical claim is Theorem 1. Let X_N be N sparse vectors with support sizes in [k_min,k_max], and let A be an m by n matrix whose entries are zero with probability 1-gamma and otherwise drawn from any zero-mean, finite-variance distribution. Define the binary measurement y=|sign(Au)| and the estimator simsh(y,z)=log(sim_intersection(y,z))/log(sim_union(y,z)). For any epsilon>0 and $\beta$>2, if m > 32 log(4+$\beta$ log N)/($gamma^{2}$ $k_min^{2}$ $e^{{-gamma k_max}}$ $epsilon^{2}$), then the probability that any pair (u,v) satisfies |simsh(Au,Av) - J_{u,v}| > epsilon is at most $N^{{-beta+2}}$. In other words, the log-ratio estimator is a uniformly consistent estimator of the Jaccard coefficient over the whole collection, under the assumed random-matrix model.

Load-bearing premise

The whole guarantee rests on treating the hash function used in the implementation as a perfectly uniform and independent random map on the actual set elements, over a range large enough that the threshold quantization is negligible.

Editorial extensions

If this is right

  • With a suitable code length m=O(log N), one binary sketch per set keeps the worst-case pairwise Jaccard error below epsilon across an entire collection of N sparse sets.
  • At equal code length, SparseHash needs no more LSH tables than 1-bit MinHash to reach a given candidate-pair probability, so query time and storage do not grow relative to MinHash.
  • Fast SparseHash computes a sketch with O(k) hash evaluations and O(k log m) comparisons, matching the asymptotic cost of the MinHash bottom sketch while storing one bit per measurement.
  • On the text and metagenome experiments reported, the binary Jaccard estimator matches or improves precision and mean-squared-error relative to 1-bit MinHash and to a MinHash-based genome sketching method at the same runtime.
  • The characterization of Hamming distance between SparseHash codes gives an explicit, nonlinear map from the Jaccard coefficient to the per-bit agreement probability, which is what drives the LSH comparison in Proposition 1.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same ratio-of-logs identity would work for any measurement scheme in which the probability of a zero coordinate factors as a base raised to the set size; this suggests natural extensions to weighted sets or to other similarity coefficients whenever such factorizations can be engineered.
  • The bound's dependence on e^{-gamma k_max} indicates that the favorable operating point is gamma roughly equal to 1/k, so sketches stay short only when the sparsity range is not too wide; datasets with highly variable support sizes may need a data-dependent gamma or a multi-resolution scheme.
  • Because the fast implementation treats hash outputs as uniform, a practitioner can empirically validate that assumption on a specific dataset by comparing measured zero-rates to (1-gamma)^{|S|}; a systematic mismatch would signal the need for a different hash or a larger output range.
  • The paper leaves empty-set and zero-overlap cases implicit; for J=0 the estimator involves log of a quantity near zero or undefined, so a robust deployment would need a fallback for pairs with no shared support.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The manuscript studies SparseHash, a method for sketching sparse signals/sets into m-bit binary vectors. Each sketch bit is obtained from a γ-sparsified random projection, implemented either by hashing with a fixed threshold (Algorithm 1) or by a faster tree-based random-window method (Algorithm 2). The authors define sim∪ as the empirical fraction of coordinates where both sketches are zero, define sim∩ as the empirical ratio of squared zero counts to simultaneous zero counts, and propose the estimator simsh = log(sim∩)/log(sim∪) for the Jaccard coefficient. Theorem 1 claims an explicit union-bound concentration of simsh around J over a collection of N sparse vectors. Section 4.2 gives the Hamming-distance analogue and derives an LSH comparison showing that SparseHash needs fewer hash tables than 1-bit MinHash under equal m. Experiments on synthetic data, New York Times bag-of-words data, and a metagenome dataset (with code released) show competitive precision/recall and MSE-vs-runtime behavior.

Significance. The paper addresses a useful problem—binary, space-efficient embeddings for set similarity—and contains several strengths: Fast SparseHash is a nontrivial algorithmic contribution, the LSH comparison in Proposition 1 is clean, and the experimental section compares against MinHash on real large-scale data with publicly available code. The numerical validation of the Hamming-distance mean in Fig. 2 is a genuine check of the model. If Theorem 1 were correct, it would give a transparent dependence of m on N, ε, and the sparsity range, including the appealing regime m = O(log N). However, the central theoretical statement currently fails on a boundary event that is not negligible under the stated hypotheses, so the main contribution needs substantial revision before the result can be accepted.

major comments (3)
  1. [Theorem 1, Section 4.1] The concentration claim in (2) is false as stated because log(sim∪) is undefined with probability tending to 1 under the theorem's own hypotheses. Take u and v disjoint, both of sparsity K, and set k_min = k_max = K so that Theorem 1 applies. For each coordinate i, P(y_i = z_i = 0) = (1-γ)^{2K} = ζ. Under the bound m > 32 log(4 + β log N)/(γ² K² e^{-γK} ε²), the expected number of all-zero coordinates is mζ ≈ 32 log(4 + β log N)e^{-γK}/(γ²K²ε²), which tends to 0 as K → ∞. Hence P(sim∪ = 0) = (1-ζ)^m ≈ exp(-mζ) → 1, while the claimed failure probability N^{-β+2} tends to 0. Since simsh is undefined on {sim∪ = 0}, the theorem is at best ill-posed and, under any convention that assigns an arbitrary value on the bad event, contravenes (2). The statement needs an additional hypothesis—for example, a coupling of γ with k_max, or an explicit bound on P(sim∪ = 0 ∪ sim∩ = 0) under the m condition—before the proof can be valid.
  2. [Appendix A.2, proof of Theorem 1] The final concentration argument applies Lemma 4 to sim∩ and sim∪ and then Lemma 3 to the two logarithms, but none of these steps conditions on sim∪ > 0 or sim∩ > 0, even though Lemma 4 explicitly requires X > 0. This is not a cosmetic gap: the previous comment shows that {sim∪ = 0} has probability tending to 1 for admissible parameter choices, so the unconditional tail bounds for log(sim∪) give no control on the event where the logarithm is undefined. A rigorous proof must either prove that {sim∪ ≥ δ, sim∩ ≥ δ} has high probability under the stated m condition, or replace simsh by an estimator that is well-defined on the zero-count events.
  3. [Appendix A.2, Corollary 2] There is a notation error that propagates through the proof: after setting X = (Σ_i 1((Au)_i=0) Σ_i 1((Av)_i=0))/m² and Z = sim∪, the text states μ_Z = (1+γ)^{(k1+k2)/(1+J)}. The correct expectation of Z is (1-γ)^{(k1+k2)/(1+J)}. The displayed bound (12) and the later substitution μ_Z² = (1-γ)^{2(k1+k2)/(1+J)} use the (1-γ) form, so the (1+γ) expression appears to be a typo. Please correct it and make the algebra from μ_Z² to the (1-γ)^{12k_max} exponent explicit, since the current derivation skips a step that is essential for verifying the final exponent.
minor comments (4)
  1. [Appendix A.2, Lemma 1] In the proof of Lemma 1, the text reads 'Sv = supp(Sv)'; this should be 'Sv = supp(v)'.
  2. [Theorem 1 statement] The condition on m is written as '32 log 4+β logN / (...)' without parentheses; it should be '32 log(4 + β log N)/(γ² k_min² e^{-γk_max} ε²)' for the bound to be unambiguous.
  3. [Section 3.1] The claim that 32-bit or larger hash outputs make the quantization error 'negligible' is not quantified. Since Theorem 1 is proved for the matrix model rather than for the hash-based implementation, the paper should state explicitly which uniformity property of the hash family is required and, if no rigorous guarantee is available, mark this as an approximation assumption in the theorem's scope.
  4. [Appendix A.3, Proposition 1] The proof says 'We can then numerically verify that the last inequality is always true (see Figure 6)'. Since the inequality 2^{(J-1)/(1+J)} ≥ (J+1)/2 can be verified analytically, a plot is not a proof; please replace the numerical check with a short analytical argument.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the Jaccard-preservation theorem is derived from the random projection model, not assumed or fitted.

full rationale

The central derivation is self-contained. Theorem 1 defines simsh from the measurement vectors y,z only, and the proof derives its concentration from first principles: for the γ-sparsified random matrix model, E[sim∪] = (1−γ)^(|Su∪Sv|) and E[sim∩] ≈ (1−γ)^(|Su∩Sv|), so the ratio of logarithms concentrates on the Jaccard coefficient. No parameter is fitted to Jaccard values; γ is an input of the embedding and is chosen by entropy maximization in the experiments, and the target Jaccard coefficient is never used as a regressor. The paper extends the authors' prior work [37], but the proof in Appendix A.2 uses Hoeffding inequalities and elementary ratio-concentration lemmas; [37] is cited for the definition of SparseHash and prior numerical validation, not as the proof of Theorem 1. The only passages that might appear load-bearing are the acknowledgement in Section 4.1 that 'γ must be designed so that this formula has small probability to be undefined' and the approximation caveat about hash uniformity in Section 3.1; both are limitations of the implementation or model, not inputs folded into the conclusion. The skeptics' issue that the event {sim∪=0} is not controlled in Theorem 1's statement is a correctness or well-posedness concern, not a circularity: the claimed concentration would be ill-posed on that bad event, but it does not reduce to fitting or to a self-citation chain. Therefore the circularity score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central theorem rests on standard concentration inequalities, the assumed i.i.d. row and entry model of the gamma-sparsified matrix, and the uniformity approximation of real hash functions. No numerical constants are fitted to data in the proof; gamma is a user-chosen design parameter. The estimator simsh is constructed so its expectation ratio equals J, but no parameter is tuned to match observed J values, so the derivation is not circular. No new physical or mathematical entities are introduced.

free parameters (1)
  • gamma (sparsification probability) = 1 - 2^{-1/k} in the experiments; left as a free design parameter in the theorem
    gamma controls the threshold tau = gamma(2^b - 1) and the measurement probabilities (1-gamma)^k. It is chosen by hand to maximize binary entropy rather than fitted to Jaccard targets, so it is a design parameter rather than a fitted constant.
assumptions (4)
  • standard math Hoeffding's inequality for sums of independent bounded random variables.
    Used in Lemmas 1 and Corollary 1 to bound deviations of sim_union and zero-count averages from their means.
  • domain assumption Rows of the gamma-sparsified random matrix A are independent and each entry is zero with probability 1-gamma, nonzero entries drawn from a zero-mean finite-variance distribution.
    This is the generative model in Section 3 and the basis for the Bernoulli indicators used in the proof; if rows were dependent, the Hoeffding steps would not hold.
  • ad hoc to paper Hash functions used in Algorithms 1 and 2 produce independent, uniformly distributed outputs over [0, 2^b - 1] with negligible quantization.
    Section 3.1 states exact equivalence with y = |sign(Au)| requires truly uniform hash output; the concentration theorem applies to the exact matrix model, not directly to the hash-based implementation.
  • domain assumption Sets are represented as binary sparse vectors with support size k, and Jaccard similarity is defined on supports.
    Section 3 defines the duality between sets and binary signals; bag-of-words counts are discarded, so the method measures support overlap, not weighted similarity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Analysis of SparseHash: an efficient embedding of set-similarity via sparse projections." pith.science (2026). https://pith.science/paper/XJ633ZN2

@misc{pith2026190901802,
  author       = {Pith},
  title        = {Pith review of: Analysis of SparseHash: an efficient embedding of set-similarity via sparse projections},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XJ633ZN2}},
  note         = {Machine review of arXiv:1909.01802}
}
read the original abstract

Embeddings provide compact representations of signals in order to perform efficient inference in a wide variety of tasks. In particular, random projections are common tools to construct Euclidean distance-preserving embeddings, while hashing techniques are extensively used to embed set-similarity metrics, such as the Jaccard coefficient. In this letter, we theoretically prove that a class of random projections based on sparse matrices, called SparseHash, can preserve the Jaccard coefficient between the supports of sparse signals, which can be used to estimate set similarities. Moreover, besides the analysis, we provide an efficient implementation and we test the performance in several numerical experiments, both on synthetic and real datasets.

Figures

Figures reproduced from arXiv: 1909.01802 by the authors.

Figure 1
Figure 1. Example of Fast SparseHash: a binary tree is generated from [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Numerical validation: Hamming distance (mean and variance). [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Experiment on similar text documents: precision and recall, threshold [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Experiment on similar text documents: precision and recall, threshold [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Metagenome clustering: MSE on pairwise Jaccard matrix with com [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: Proof of Proposition 1 25 [PITH_FULL_IMAGE:figures/full_fig_p025_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    Achlioptas

    D. Achlioptas. Database-friendly random projections: Johnson- Lindenstrauss with binary coins. J. Comput. Syst. Sci. , 66(4):671–687, 2003

    work page 2003

  2. [2]

    Andoni and P

    A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM, 51(1):117–122, 2008. 15

    work page 2008

  3. [3]

    Bioglio, T

    V. Bioglio, T. Bianchi, and E. Magli. On the fly estimation of the sparsity degree in compressed sensing using sparse sensing matrices. In Proc. IEEE ICASSP, pages 3801–3805, 2015

    work page 2015

  4. [4]

    Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422–426, 1970

    work page 1970

  5. [5]

    Boufounos and S

    P. Boufounos and S. Rane. Secure binary embeddings for privacy preserving nearest neighbors. In IEEE WIFS, pages 1–6, 2011

    work page 2011

  6. [6]

    P. T. Boufounos and S. Rane. Efficient coding of signal distances using universal quantized embeddings. In Data Compression Conference (DCC), 2013, pages 251–260, 2013

    work page 2013

  7. [7]

    A. Broder. On the resemblance and containment of documents. In Proc. Compression and Complexity of Sequences , pages 21–29, 1997

    work page 1997

  8. [8]

    Broder, M

    A. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher. Min-wise independent permutations. Journal Comput. Syst. Sci. , 60(3):630 – 659, 2000

    work page 2000

Show all 41 references
  1. [9]

    A. Z. Broder, S. C. Glassman, M. S. Manasse, and G. Zweig. Syntactic clustering of the web. Comput. Netw. ISDN Syst. , 29(8-13):1157–1166, 1997

    1997

  2. [10]

    E. J. Cand` es and T. Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inf. Theory , 52(12):5406–5425, 2006

    2006

  3. [11]

    J.Lawrence Carter and Mark N. Wegman. Universal classes of hash func- tions. Journal of Computer and System Sciences , 18(2):143 – 154, 1979

    1979

  4. [12]

    M. S. Charikar. Similarity estimation techniques from rounding algorithms. In Proc. ACM STOC, pages 380–388, 2002

    2002

  5. [13]

    Set similarity search beyond MinHash

    Tobias Christiani and Rasmus Pagh. Set similarity search beyond MinHash. In Proc. ACM STOC, pages 1094–1107, 2017

    2017

  6. [14]

    Summarizing data using bottom-k sketches

    Edith Cohen and Haim Kaplan. Summarizing data using bottom-k sketches. In Proc. ACM PODC, pages 225–234, 2007

    2007

  7. [15]

    Fast similarity sketching

    Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. Fast similarity sketching. CoRR, abs/1704.04370, 2017

    2017 arXiv

  8. [16]

    D. L. Donoho. Compressed sensing. IEEE Trans. Inf. Theory, 52(4):1289– 1306, 2006

    2006

  9. [17]

    Henzinger

    M. Henzinger. Finding near-duplicate web pages: A large-scale evaluation of algorithms. In Proc. ACM SIGIR, pages 284–291, 2006. 16

    2006

  10. [18]

    Probability inequalities for sums of bounded random variables

    Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association , 58(301):13–30, March 1963

    1963

  11. [19]

    Similarity measures for text document clustering

    Anna Huang. Similarity measures for text document clustering. In Proc. New Zealand computer science research student conf. , pages 49–56, 2008

    2008

  12. [20]

    P. Indyk. A small approximately min-wise independent family of hash functions. In Proc. ACM-SIAM SODA, pages 454–456, 1999

    1999

  13. [21]

    Improved consistent sampling, weighted minhash and l1 sketching

    Sergey Ioffe. Improved consistent sampling, weighted minhash and l1 sketching. In Proc. IEEE Int. Conf. Data Mining , pages 246–255, 2010

    2010

  14. [22]

    Jacques, J

    L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Trans. Inf. Theory, 59(4):2082–2102, 2013

    2013

  15. [23]

    Bitshred: feature hashing malware for scalable triage and semantic analysis

    Jiyong Jang, David Brumley, and Shobha Venkataraman. Bitshred: feature hashing malware for scalable triage and semantic analysis. In Proc. ACM CCS, pages 309–320, 2011

    2011

  16. [24]

    W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26, 1984

    1984

  17. [25]

    P. Li, T. J. Hastie, and K. W. Church. Very sparse random projections. In Proc. ACM SIGKDD, pages 287–296, 2006

    2006

  18. [26]

    Li and C

    P. Li and C. K¨ onig. b-bit minwise hashing. In Proceedings of the 19th International Conference on World Wide Web , pages 671–680, 2010

    2010

  19. [27]

    M. Lichman. UCI machine learning repository. http://archive.ics.uci.edu/ml, 2013

    2013

  20. [28]

    Luo, Deke Guo, Richard TB Ma, Ori Rottenstreich, and Xueshan Luo

    L. Luo, Deke Guo, Richard TB Ma, Ori Rottenstreich, and Xueshan Luo. Optimizing bloom filter: Challenges, solutions, and comparisons. arXiv preprint arXiv:1804.04777, 2018

    2018 arXiv

  21. [29]

    MurmurHash3. Code. https://github.com/aappleby/smhasher/blob/ master/src/MurmurHash3.cpp, 2016

    2016

  22. [30]

    Ondov, Todd J

    Brian D. Ondov, Todd J. Treangen, P´ all Melsted, Adam B. Mallonee, Nicholas H. Bergman, Sergey Koren, and Adam M. Phillippy. Mash: fast genome and metagenome distance estimation using minhash. Genome Bi- ology, 17(1):132, 2016

    2016

  23. [31]

    Ravazzi, S

    C. Ravazzi, S. M. Fosson, T. Bianchi, and E. Magli. Signal sparsity estima- tion from compressive noisy projections via γ-sparsified random matrices. In Proc. IEEE ICASSP, pages 4029–4033, 2016. 17

    2016

  24. [32]

    Ravazzi, S

    C. Ravazzi, S. M. Fosson, T. Bianchi, and E. Magli. Sparsity estimation from compressive projections via sparse random matrices. EURASIP J. Adv. Signal Process., 2018(56):1–18, 2018

    2018

  25. [33]

    Exact weighted minwise hashing in constant time

    Anshumali Shrivastava. Exact weighted minwise hashing in constant time. CoRR, abs/1602.08393, 2016

    2016 arXiv

  26. [34]

    SparseHash. Code. https://github.com/diegovalsesia/sparsehash, 2017

    2017

  27. [35]

    Structure, function and di- versity of the healthy human microbiome.Nature, 486(7402):207–214, 2012

    The Human Microbiome Project Consortium. Structure, function and di- versity of the healthy human microbiome.Nature, 486(7402):207–214, 2012

    2012

  28. [36]

    Valsesia, G

    D. Valsesia, G. Coluccia, T. Bianchi, and E. Magli. Large-scale image retrieval based on compressed camera identification. IEEE Trans. Multim., 17(9):1439–1449, 2015

    2015

  29. [37]

    Valsesia, S

    D. Valsesia, S. M. Fosson, C. Ravazzi, T. Bianchi, and E. Magli. Sparse- hash: Embedding Jaccard coefficient between supports of signals. In IEEE ICMEW, pages 1–6, 2016

    2016

  30. [38]

    Valsesia and E

    D. Valsesia and E. Magli. Binary adaptive embeddings from order statistics of random projections. IEEE Signal Process. Lett., 24(1):111–115, 2017

    2017

  31. [39]

    J. Wang, T. Zhang, J. song, N. Sebe, and H. T. Shen. A survey on learning to hash. IEEE Trans. Pattern Anal. Mach. Intell. , 40(4):769–790, 2018

    2018

  32. [40]

    W.L. Zhao, H. J´ egou, and G. Gravier. Sim-Min-Hash: An efficient matching technique for linking large image collections. In Proc. ACM MM , pages 577–580, 2013. A Appendix In this Appendix, we provide the details of the proofs of Theorem 1 and Propo- sition 1. Here, we report al...

    2013

  33. [41]

    and, analogously denoting µZ = (1−γ)k2, P (|Z−µZ|>ϵ )≤ 2e−2ϵ2m

    we get P (|X−µX|>ϵ )≤ 2e−2ϵ2m. and, analogously denoting µZ = (1−γ)k2, P (|Z−µZ|>ϵ )≤ 2e−2ϵ2m. Applying Lemma 2 and computing P ( |X−µX|> ϵ 3µZ ) ≤ 2e − 2ϵ2m 9(1−γ)2k2 ≤ 2e− 2ϵ2m 9 (9) and, similarly, P ( |Z−µZ|> min { ϵ 2µX ,µZ 2 }) ≤ 2e −2m min { ϵ2 4(1−γ)k1, (1−γ)2k2 4 } ≤ ...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.