A General Construction of Min-Wise Independent Permutations
Summary :
A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.646-655
- Publication Date
- 2000/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yoshinori TAKEI, Toshiya ITOH, "A General Construction of Min-Wise Independent Permutations" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 4, pp. 646-655, April 2000, doi: .
Abstract: A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_646/_p
Copy
@ARTICLE{e83-a_4_646,
author={Yoshinori TAKEI, Toshiya ITOH, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A General Construction of Min-Wise Independent Permutations},
year={2000},
volume={E83-A},
number={4},
pages={646-655},
abstract={A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - A General Construction of Min-Wise Independent Permutations
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 646
EP - 655
AU - Yoshinori TAKEI
AU - Toshiya ITOH
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2000
AB - A min-wise independent permutation family is known to be an efficient tool to estimate similarity of documents. Toward good understanding of min-wise independence, we present a characterization of exactly min-wise independent permutation families by size uniformity, which represents certain symmetry of the string representation of a family. Also, we present a general construction strategy which produce any exactly min-wise independent permutation family using this characterization.
ER -
English
