A general construction of min-wise independent permutations

被引：0

作者：

Takei, Y ^{[1
]}

Itoh, T

机构：

[1] Tokyo Inst Technol, Dept Elect & Elect Engn, Tokyo 1528552, Japan

[2] Tokyo Inst Technol, Dept Informat Proc, Yokohama, Kanagawa 2268502, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2000年 / E83A卷 / 04期

关键词：

min-wise independence; permutations; general construction;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：646 / 655

页数：10

共 6 条

[1]

Broder A. Z., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P327, DOI 10.1145/276698.276781

[2] On the resemblance and containment of documents [J].

Broder, AZ .

COMPRESSION AND COMPLEXITY OF SEQUENCES 1997 - PROCEEDINGS, 1998, :21-29

[3]

Broder AZ, 1998, LECT NOTES COMPUT SC, V1518, P15

[4]

Indyk P, 1999, PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P454

[5]

SHINOZAKI T, 1999, MODELS COMPUTATION A, V1093, P74

[6]

TAKEI Y, 1998, COMP9862 IEICE

← 1 →