Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 43 min ago
PreprintarXiv licencearXiv

Understanding Circulant Permutation to Extend the CMinHash Estimator

  • Keegan Kang
  • Avery Hood
  • Benedict H. W. Wong
Open at sourcePDFDOICite

Abstract

CMinHash promises a new direction for designing MinHash algorithms with reduced variance and storage space via circulant permutations. However, the original variance analysis is difficult to extend to other MinHash estimators. We present a new approach that gives explicit and easily comparable approximate variance expressions, and use it to analyze the Minner estimator. Numerical experiments show that our variance expression matches the empirical mean square error (MSE) of estimates. Our work thereby demonstrates how to apply circulant permutation to other MinHash estimators and compute their approximate variance.

Related

  1. High-Girth QLDPC Codes from Circulant and Affine Permutation Matrices
    Vahid Nourozi, Roxana Smarandache, David G. M. Mitchell†
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  2. A d-algebra whose product does not extend to its Dedekind completion
    Mohamed Amine Ben Amor
    arXivPreprintCC BY-NC-ND 4.0Full textAnalysis & PDEsarXiv
  3. A study on Type-2 isomorphic circulant graphs. Part 3: 384 pairs of Type-2 isomorphic circulant graphs C32(R)
    Vilfred Kamalappan
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Gauss--Manin connections extend to holonomic coadmissible D-cap-modules
    Andreas Bode, Finn Wiersig
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  5. A study on Type-2 isomorphic circulant graphs. Part 4: 960 triples of Type-2 isomorphic circulant graphs C54(R)
    Vilfred Kamalappan
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{kang2026understanding,
  title = {{Understanding Circulant Permutation to Extend the CMinHash Estimator}},
  author = {Keegan Kang and Avery Hood and Benedict H. W. Wong},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.18551},
  eprint = {2610.18551},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.18551},
}
RIS
TY  - UNPB
TI  - Understanding Circulant Permutation to Extend the CMinHash Estimator
AU  - Keegan Kang
AU  - Avery Hood
AU  - Benedict H. W. Wong
PY  - 2026
DA  - 2026/10/13
PB  - arXiv
DO  - 10.48550/arxiv.2610.18551
UR  - https://arxiv.org/abs/2610.18551
AB  - CMinHash promises a new direction for designing MinHash algorithms with reduced variance and storage space via circulant permutations. However, the original variance analysis is difficult to extend to other MinHash estimators. We present a new approach that gives explicit and easily comparable approximate variance expressions, and use it to analyze the Minner estimator. Numerical experiments show that our variance expression matches the empirical mean square error (MSE) of estimates. Our work thereby demonstrates how to apply circulant permutation to other MinHash estimators and compute their approximate variance.
ER  -