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

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

Min-Wise Independence vs. 3-Wise Independence 최소-현 독립 vs. 3-현 독립

Toshiya ITOH

  • 조회수

    0

  • 이것을 인용

요약 :

가족 F 최소 단위의 독립 순열은 웹에서 복제된 문서를 색인화하는 유용한 도구로 알려져 있습니다. 우리는 가족이라고 말해요 F {0,1,. . . ,n-1}은 최소한의 독립 혹시라도 X {0,1,. . . ,n-1} 및 기타 x X, Pr[분 {π(X)} = π(x)]= ||X||-1 π가 다음에서 균일하게 무작위로 선택될 때 F, 여기서 ||A|| 유한 집합의 카디널리티입니다 A. 우리는 또한 가족이라고 말합니다. F {0,1,. . . ,n-1}은 d-현명한 독립 특별한 경우 x1,x2,. . . ,xd {0,1,. . . , n-1} 및 기타 고유한 y1,y2,. . . ,yd {0,1,. . . , n-1}, Pr[i = 1d π(xi) = π(yi)]= 1/{n(n-1)··· (n-d+1)} π가 무작위로 균등하게 선택되는 경우 F (중요하지 않은 구성은 d- 현명한 독립 가족 F {0,1,. . . ,n-1}은 다음으로만 알려져 있습니다. d=2,3). 최근에는 Broder, et al. 어떤 가족이라도 보여줬어 F 쌍별(2별) 독립 순열은 최소별 독립 순열 계열에 가깝게 동작합니다. 즉, X {0,1,. . . ,n-1} 3 ||X||=k n-2 및 임의 x X, (하한) Pr[min {π(X)}=π(x)] 1/{2(k-1)}; (상한) Pr[min {π(X)}=π(x)] O(1 /k). 이 논문에서 우리는 이러한 범위를 3-방향 독립 순열 패밀리로 확장하고 3-방향 독립 순열 패밀리가 최소 단위 독립 순열 패밀리에 더 가깝게 동작한다는 것을 보여줍니다. X {0,1,. . . ,n-1} 4 ||X||=k n-3 및 임의 x X, (하한) Pr[min {π(X)}=π(x)] 1/{2(k-2)}- 1/{6(k- 2)2}; (상한) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).

발행
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.957-966
발행일
2002/05/01
공개일
온라인 ISSN
DOI
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주

작성자

키워드