검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Constructing an Optimal Family of Min-Wise Independent Permutations Min-Wise 독립 순열의 최적 계열 구축

Yoshinori TAKEI, Toshiya ITOH, Takahiro SHINOZAKI

  • 조회수

    0

  • 이것을 인용

요약 :

가족 C 최소 단위의 독립 순열은 웹에서 복제된 문서를 색인화하는 유용한 도구로 알려져 있습니다. 임의의 정수에 대해 n>0, 가족 C [에 대한 순열의n]={1,2,. . . ,n} 이라고합니다 최소한의 독립 만약 있다면(비어있지 않음) X [n] 그리고 어떤 x X, Pr ( 분 {π(X)} = π(x))= ||X||-1 π가 다음에서 균일하게 무작위로 선택될 때 C, 여기서 ||A|| 유한 집합의 카디널리티입니다 A. 임의의 정수에 대해 n>0, (1) ||C|| XNUMXcm(n,n-1,. . . ,2,1) = e아니(n) 어느 가족에게나 C [에 대한 최소 단위 독립 순열의n]; (2) 샘플링 가능한 다항식 시간이 존재합니다. C [에 대한 최소 단위 독립 순열 계열n] 그런 식으로 ||C|| 4n. 그러나 최소한의 독립된 가족이 존재하는지 여부는 불분명하다. C 그렇게 ||C|| = 1cm(n,n-1,. . . ,2,1) 각 정수에 대해 n>0 그리고 그러한 가족을 구성하는 방법 C 각 정수에 대한 최소 단위 독립 순열 n>0(존재하는 경우) 본 논문에서는 가족을 구성할 것이다. Fn 각 정수에 대한 순열 n>0이고 다음을 보여줍니다. Fn 최소 단위로 독립적이고 ||Fn|| = 1cm(n,n-1,. . . ,2,1). 게다가, 우리는 다항식 시간 가족을 위한 샘플링 알고리즘. 그리하여 가족은 Fn 최소 단위의 독립 순열은 다음과 같습니다. 최적의 가족 규모 측면에서 볼 때 다항식 시간 샘플링 가능성으로 인해 구현하기 쉽습니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.747-755
발행일
2000/04/25
공개일
온라인 ISSN
DOI
원고의 종류
PAPER
범주
알고리즘 및 데이터 구조

작성자

키워드