미니해시

컴퓨터 과학 및 데이터 마이닝에서 MinHash(또는 min-wise 독립 순열 지역 민감 해시 방식)는 두 집합이 얼마나 유사한지 빠르게 추정하기 위한 기술입니다.이 스킴은 Andrei Broder(1997년)^[1]에 의해 발명되었으며, AltaVista 검색 엔진에서 처음에는 중복된 웹 페이지를 탐지하여 검색 ^[2]결과에서 삭제하기 위해 사용되었습니다.또한 ^[1]문서 집합의 유사성에 의한 클러스터링과 같은 대규모 클러스터링 문제에도 적용되어 왔습니다.

Jaccard 유사성과 최소 해시 값

Jaccard 유사도 계수는 일반적으로 사용되는 두 세트의 유사도 지표입니다.U를 한 $세트$ 로 $하고$ A와 $B$ 를 U의 서브셋으로 $하면$ , Jaccard 지수는 교집합 요소의 수와 결합 요소의 수의 비율로 정의된다.

({displaystyle J(A,B)=A\cap B}\over {A\cup B}).}

이 값은 두 세트가 분리된 경우 0, 동일한 경우 1 및 0과 1 사이의 엄밀한 값입니다.두 세트는 자카드 지수가 1에 가까울 때 더 유사하다(즉, 상대적으로 더 많은 구성원을 가진다).MinHash의 목표는 J $(A,$ $B)$ 를 교집합과 결합을 명시적으로 계산하지 않고 신속하게 $추정$ 하는 것이다.

있는 나라의 정수에 U의 회원들을 수립하는지 h가 된 해시 함수,이라는 정해진 U의 요소 중 perm 무작위 순열으며, 어떤 하위 집합 SUSh∘ perm—that에 존경을 이용해 최소한의 멤버 hmin(S)을 정의하게 해 주는 것은, Sh(파마())의 최소 값을 사용하여 멤버 x).(경우에는 해시 함수를 사용하기 위해서는 가정합니다오호ave 의사 변환 특성, 무작위 순열은 사용되지 않습니다.)

A와 $B$ 모두에 $h$ 를 $적용$ 하고_min 해시 충돌이 없다고 가정하면 $A\cup B$ 의 $A\cup B$ 요소 중 해시 값이 최소인 요소가 $A\cap B$ 와 $A\cap B$ B의 $A\cap B$ B에 존재하는 경우 $(\$ $displaystyle$ A $\cup$ B $\$ 에만_min 값이 $같다는 min$ 것을 알 수 있습니다.이것이 참일 확률은 정확히 Jaccard 지수입니다.따라서 다음과 같습니다.

Pr[h min (A) = h min (B) ]= J (A, B),

즉, h $(A)$ = $h min (B)$ 가_min 참일 확률은 균일한 분포에서 펌을 $추출$ 한다고 가정할 때 $유사$ 도 J $(A, B)$ 와 같다.즉, r이 h $(A)$ = $h min (B)$ 이고 $그렇지 min$ 않으면 0일 때 r은 J $(A, B)$ 의 비편향 추정치입니다 $.$ $r$ 은 분산이 너무 높아 Jaccard $유사성$ 에 대한 유용한 추정치가 될 수 없습니다.r은 $항상$ 0 또는 1이기 $r$ 입니다.MinHash 스키마의 개념은 동일한 방식으로 구성된 여러 변수의 평균을 구함으로써 이 분산을 줄이는 것입니다.

알고리즘.

해시 함수가 많은 변종

가장 간단한 버전의 Minhash 스킴은 k개의 다른 해시 함수를 $사용$ 합니다. $여기$ 서 k는 고정 정수 파라미터이며, $이러한$ k개의 함수에 대한 h $(S)$ 의_min $k개$ 의 값으로 각 $집합$ S를 나타냅니다.

이 버전의 체계를 사용하여 J $(A,$ $B)$ 를 $추정$ 하려면 y를 h $(A)$ = $h min (B)$ 인 $해시 min$ 함수의 수로 $하고$ y $/ k$ 를 추정으로 $사용$ 합니다.이 추정치는 각각 h(A) $=$ $h min (B)$ 일 $때 min$ 1이고 그렇지 않을 경우 0인 k개의 다른 0-1 랜덤 변수의 $평균$ 이며, 각각은 J $(A, B)$ 의 편향되지 않은 추정치이다.따라서 평균도 치우치지 않은 추정치이며 0-1 랜덤 변수의 합계에 대한 표준 편차에 의해 예상되는 오차는 O( $1/ µk) [3]$ 입니다.

따라서 상수 $θ$ > $0$ 에 대해 추정치의 예상 오차가 최대 $θ$ 가 되도록 $상수$ k $= O$ (1 $/diples 2)$ 가 존재한다.예를 들어, 예상 오차가 0.05 이하인 J $(A, B)$ 를 $추정$ 하려면 400개의 해시가 필요합니다.

단일 해시 함수를 사용하는 변종

여러 해시함수를 계산하는 것은 계산상 비용이 많이 들 수 있지만, 관련된 버전의 MinHash 스킴은 하나의 해시함수만을 사용하여 이 패널티를 회피하고 해시함수당 하나의 최소값만을 선택하는 것이 아니라 각 집합에서 여러 값을 선택하는 데 사용합니다. $h$ 를 해시 함수, k를 $고정$ 정수라고 합니다.S가 h $영역$ 의 k개 이상의 $값$ 집합인 $경우$ $,$ h( $S)$ 를 h의 $가장$ 작은 값을 갖는 $S$ 의 k 멤버의 서브셋으로 $정의$ 한다_(k).이 $서브셋h (k) (S)$ 는 $세트S$ 의 시그니처로서 사용되며, 임의의 2 세트의 유사성은 시그니처를 비교하여 추정됩니다.

구체적으로는 A와 B를 임의의 2세트로 합니다. $X$ = $h (k) (h (k) (A) h (k)$ $h (B (k)) =$ h $(A$ is B $)$ 는 A $a$ B의 k개 원소 집합이며, h가 랜덤 함수일 경우 k개 요소의 서브셋이 선택될 가능성이 동등하다. 즉, $X$ 는 A $b$ B의 $단순$ 랜덤 샘플이다. $부분집합$ Y = $X$ ∩ $h (k) (A) h (k)$ h $(B)$ 는 $교차점$ A $b$ B에 속하는 X의 $부재$ 집합이다.따라서 Y / $k$ 는 J $(A,$ $B)$ 의 편향되지 않은 추정치입니다.이 추정기와 여러 해시 함수에 의해 생성된 추정기의 차이점은 X가 항상 $정확히$ k개의 멤버를 가지고 있는 $반면$ , 여러 해시 함수는 두 개의 다른 해시 함수가 같은 최소값을 가질 수 있기 때문에 샘플링된 요소의 수가 적을 수 있다는 것입니다.그러나 k가 세트의 크기에 비해 작을 $경우$ 이 차이는 무시할 수 있습니다.

대체하지 않고 샘플링하기 위한 표준 체르노프 경계에 따라 이 추정기는 다중 해시 함수 방식의 성능과 일치하는 $오차$ O(1 $/ µk)$ 를 예측했습니다.

시간 분석

$추정기$ Y / $k$ 는 주어진 세트의 두 시그니처로부터 시간 $O(k)$ 단위로 계산될 수 있다.따라서 $θ$ 와 k가 상수인 경우 시그니처로부터 추정된 유사도를 계산하는 시간도 일정합니다.각 세트의 시그니처는 세트의 크기에 대해 선형 시간으로 계산할 수 있으므로, 많은 쌍의 유사성을 추정해야 할 경우 이 방법을 사용하면 각 세트의 멤버를 완전히 비교하는 것에 비해 실행 시간을 크게 절약할 수 있습니다.구체적으로는 set $size$ n의 경우 많은 해시 $배리언트에$ O( $nk)$ 시간이 걸립니다.일반적으로 단일 해시 배리언트는 속도가 더 빠릅니다.즉, $n$ >> ^[1]k를 $전제$ 로 한 최소 해시 값의 큐를 유지하기 위해서는 O $(n)$ 시간이 $필요$ 합니다.

무게 포함

Min Hashes의 계산에 가중치를 도입하는 다양한 기술이 개발되었다.가장 단순한 것은 정수 ^[4]가중치까지 확장합니다. $해시함수$ h를 확장하여 세트 멤버와 정수를 모두 받아들인 후 무게에 따라 각 항목에 대해 여러 개의 해시를 생성합니다. $항목$ i가 n회 $발생$ 하는 경우 $h(i,1),h(i,2),\ldots ,h(i,n)$ h $h(i,1),h(i,2),\ldots ,h(i,n)$ ), $h(i,1),h(i,2),\ldots ,h(i,n)$ $h(i,1),h(i,2),\ldots ,h(i,n)$ $h(i,1),h(i,2),\ldots ,h(i,n)$ h $h(i,1),h(i,2),\ldots ,h(i,n)$ $)$ { $displaystyle$ h $(i,$ 1 $), h(i, 2),$ \ $ldots, h(i, n$ 를 생성합니다.이 확장된 해시 세트에 대해 원래 알고리즘을 실행합니다.이렇게 하면 충돌 확률로 가중치 Jaccard Index가 산출됩니다.

J_{\mathcal {W}}(x,y)=sum frac {i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}}

실행 시간이 더 나은 실제 가중치에서 충돌 확률을 달성하는 추가 확장이 개발되었으며, 하나는 조밀한 ^[5]데이터를 위한 확장이고 다른 하나는 희박한 ^[6]데이터를 위한 확장이다.

다른 확장 패밀리에서는 지수 분산 해시를 사용합니다.0과 1 사이의 균일 랜덤 해시는 CDF 반전에 의한 지수 분포를 따르도록 변환할 수 있습니다.이 방법은 지수 변수 집합의 최소값의 많은 아름다운 특성을 활용합니다.

{\displaystyle H(x)= 언더셋 {i}{\operatorname {display,min}}}}{\frac {-\log(h(i)}}{x_{i}}}}}:

이것은 충돌 확률로서 확률 Jaccard^[7] 지수를 산출한다.

J_{\mathcal {P}(x,y})=\sum _{x_{i}\neq 0}{\frac {1}{\sum _{j}\max \frac {x_{i}},{\frac {x_{j}}_y}{neq}}{i}}}}{i}}}}}{\frac}}}}{i}}}}{\fracy}}}}}}}}}}{\fracy}}}}}}}{i}}}}}

최소 독립 순열

위와 같이 MinHash 스킴을 구현하기 위해서는 $해시함수$ h를 사용하여 n개의 $요소$ 에 랜덤 치환을 정의할 필요가 있습니다. $여기$ 서 n은 비교하는 모든 집합의 조합에서 구별되는 요소의 총수입니다.그러나 n $!$ 의 다른 순열이 $존재$ 하기 때문에 진정한 $랜덤$ 순열을 지정하기 위해서는 $δ(n$ $log$ n $)$ 비트가 필요합니다.이것은 n의 중간값이라도 실현 불가능한 큰 숫자입니다.이러한 사실 때문에, 보편적 해시의 이론에 유추함으로써, 도메인의 모든 부분 집합에서 모든 요소가 동등하게 최소가 될 가능성이 있다는 것을 의미하는 "min-wise-independent"인 순열 패밀리를 찾는 중요한 연구가 있었다.최소 독립 순열 패밀리는 적어도 다음을 포함해야 합니다.

\displaystyle \operatorname {lcm}(1,2,\cdots,n)\geq e^{n-o(n)}}

단일 치환을 지정하려면 $δ(n)$ 비트가 필요하지만 여전히 실행 불가능한 ^[2]크기입니다.

실용적인 최소 독립 해시 함수

위의 비실용성으로 인해 제한된 최소 독립 순열 패밀리와 근사 최소 독립 패밀리의 두 가지 변형 개념이 도입되었습니다.제한된 최소 독립성은 최대 ^[8] $k개$ 의 카디널리티 집합으로 제한된 최소 독립성 속성입니다.대략적인 최소 독립성은 완전 ^[9]독립성으로부터 변화할 확률이 $기껏해야$ 고정적이다.

1999년 Piotr Indyk는^[10] k $\displaystyle$ k에 $k$ $대해$ k-wise 독립군도 거의 min-wise 독립적이라는 것을 증명했다.특히 $c,c'>0$ c $c,c'>0$ $c,c'>0$ $c,c'>0$ $c,c'>0$ { $displaystyle$ c, $c'$ > $0$ }이 $c,c'>0$ 있습니다. $k\geq c\log {\tfrac {1}{\epsilon }}$ $k\geq c\log {\tfrac {1}{\epsilon }}$ log $k\geq c\log {\tfrac {1}{\epsilon }}$ 1 ${\$ { \ $displaystyle$ k \ $geq$ c \ log { \ $tfrac$ { 1 } { \ $epsilon$ } $k\geq c\log {\tfrac {1}{\epsilon }}$ 。

{\displaystyle \Pr _{h\in {H}}[h(x)<\min h(X)]=pm frac {1}{ X +1}}(1\pm \silon )

모든 $|X|\leq \epsilon nc'$ X $|X|\leq \epsilon nc'$ ${\$ 、 { $displaystyle$ X \ $leq \epsilon$ nc $|X|\leq \epsilon nc'$ } $x\in X$ $(1\pm \epsilon )$ X $(1\pm \epsilon )$ [ $\$ $(1\pm \epsilon )$ x \ $in$ X $x\in X$ ]( $주의$ ( $(1\pm \epsilon )$ 1 ± $)$ ){ $displaystyle ( 1$ \ $pm$ \epsilon $(1\pm \epsilon )$ }) $1-\epsilon$ 이 $1+\epsilon$ 최대 $1+\epsilon$ + $1+\epsilon$ {\ $1$ + {\ \ $epsilon$ 인수가 너무 크다는 것을 의미합니다 $1-\epsilon$

이 보증은 무엇보다도 MinHash 알고리즘에 필요한 Jaccard 바인드를 제공하기에 충분합니다.즉, A $($ $B$ A)와 B(displaystyle B $)$ 가 $B$ 세트일 $경우$

\Pr _{h\in {Mathcal {H}}[\min h(A)=\min h(B)]=cap frac { A\cap B }{ A\cup B }}}\pm \capilon

k-wise 독립 해시 함수는 $k\log n$ log $k\log n$ n \ $displaystyle$ k $\log$ n 비트만을 $k\log n$ $k\log n$ 하여 지정할 수 있으므로 이 방법은 완전히 min-wise 독립 순열을 사용하는 것보다 훨씬 실용적입니다.

대략적인 최소 독립성을 제공하는 또 다른 실용적인 해시 함수군은 표 해시입니다.

적용들

MinHash의 원래 어플리케이션에서는 웹 문서 간의 클러스터화와 거의 중복 제거가 포함되었으며, 이러한 문서에서 발생하는 단어 ^[1]^[2]^[11]세트로 표현됩니다.이미지 등 다른 유형의 데이터 클러스터링 및 거의 중복 제거에도 유사한 기술이 사용되었습니다. 이미지 데이터의 경우 이미지를 이미지에서 잘라낸 작은 하위 이미지 세트 또는 보다 복잡한 이미지 특징 설명 ^[12]세트로 나타낼 수 있습니다.

데이터 마이닝에서는 Cohen 등 (2001) MinHash를 연관지을 수 있는 규칙 학습 도구로 사용합니다.각 엔트리에 복수의 어트리뷰트(데이터베이스 엔트리당 행과 속성당 컬럼을 가진 0-1 매트릭스로 표시됨)가 있는 경우, 이들은 Jaccard 인덱스에 대한 MinHash 기반의 근사치를 사용하여 빈번히 공존하는 어트리뷰트의 후보 페어를 특정하고 이들 페어에 대해서만 인덱스의 정확한 값을 계산합니다.동시 발생 빈도가 특정 엄밀한 ^[13]임계값 미만인 경우.

MinHash 알고리즘은 게놈 서열을 비교하는 문제가 웹 상의 문서를 비교하는 것과 유사한 이론적 토대를 가지고 있는 생물 정보학을 위해 적용되었다.MinHash 기반^[14]^[15] 도구는 전체 게놈 시퀀싱 데이터를 참조 게놈과 신속하게 비교할 수 있도록 하며(RefSeq의 9만 개의 참조 게놈과 1개의 게놈을 비교하는 데 약 3분 소요), 특정화 및 미생물 서브타이핑에 적합합니다.또한 메타제노믹스와 게놈 정렬 및 게놈 ^[16]조립을 위한 MinHash 파생 알고리즘의 사용도 있다.MinHash 기반 ^[17]알고리즘을 사용하면 정확한 평균 뉴클레오티드 아이덴티티(ANI) 값을 매우 효율적으로 생성할 수 있습니다.

기타 용도

MinHash 스킴은 해시 함수를 사용하여 큰 개체 집합을 더 작은 해시 값으로 매핑하는 기술의 집합인 로컬리티에 민감한 해시의 인스턴스로 볼 수 있습니다.이것에 의해, 2개의 개체가 서로 거리가 좁을 경우, 그 해시 값은 같게 됩니다.이 경우 세트의 시그니처는 해시 값으로 간주될 수 있습니다.세트 간 해밍 거리와 벡터 간 코사인 거리에는 다른 지역 의존형 해시 기법이 있습니다.지역 의존형 해시에는 가장 가까운 네이버 검색 ^[18]알고리즘에서 중요한 응용 프로그램이 있습니다.대규모 분산 시스템, 특히 MapReduce의 경우 포인트 ^[19]치수에 의존하지 않고 유사성을 계산할 수 있도록 수정된 MinHash 버전이 있습니다.

평가 및 벤치마크

2006년 구글은 Minhash^[21] 알고리즘과 SimHash 알고리즘의 성능을 비교하기 위해 대규모 평가를 실시했다.2007년 Google은 웹^[22] 크롤링을 위한 중복 탐지에 Simhash를 사용하고 Google News ^[23]개인화에 Minhash와 LSH를 사용한다고 보고했습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b ^c ^d 브로 더는 안드레이 Z(1997년),"그 유사점과 문서들의 봉쇄에", 압축과 Sequences 간의 복잡:.집, 포시 타노, Amalfitan 연안, 살레르노, 이탈리아, 6월 11-13, 1997년(PDF), IEEE,를 대신하여 서명함. 21–29, CiteSeerX 10.1.1.24.779, doi:10.1109/SEQUEN.1997.666900, 아이 에스비엔 978-0-8186-8132-5, S2CID 11748509, 원본(PDF)에서 2015-01-31에 보관 시 2014-01-18 돌려받지 못 했다.
^ ^a ^b ^c 를 클릭합니다Broder, Andrei Z.; Charikar, Moses; Frieze, Alan M.; Mitzenmacher, Michael (1998), "Min-wise independent permutations", Proc. 30th ACM Symposium on Theory of Computing (STOC '98), New York, NY, USA: Association for Computing Machinery, pp. 327–336, CiteSeerX 10.1.1.409.9220, doi:10.1145/276698.276781, ISBN 978-0897919623, S2CID 465847.
^ 를 클릭합니다Vassilvitskii, Sergey (2011), COMS 6998-12: Dealing with Massive Data (lecture notes, Columbia university) (PDF), archived from the original (PDF) on 2018-10-24.
^ Chum, Ondrej; Philbin, James; Zisserman, Andrew (2008), "Near Duplicate Image Detection: min-Hash and tf-idf Weighting." (PDF), BMVC, 810: 812–815
^ Shrivastava, Anshumali (2016), "Exact weighted minwise hashing in constant time", arXiv:1602.08393 [cs.DS]
^ Ioffe, Sergey (2010), "Improved consistent sampling, weighted minhash and L1 sketching" (PDF), Data Mining (ICDM), 2010 IEEE 10th International Conference on: 246–255, CiteSeerX 10.1.1.227.9749, doi:10.1109/ICDM.2010.80, ISBN 978-1-4244-9131-5, S2CID 9970906
^ Moulton, Ryan; Jiang, Yunjiang (2018), "Maximally Consistent Sampling and the Jaccard Index of Probability Distributions", 2018 IEEE International Conference on Data Mining (ICDM), pp. 347–356, arXiv:1809.04052, doi:10.1109/ICDM.2018.00050, ISBN 978-1-5386-9159-5, S2CID 49746072
^ 를 클릭합니다Matoušek, Jiří; Stojaković, Miloš (2003), "On restricted min-wise independence of permutations", Random Structures and Algorithms, 23 (4): 397–408, CiteSeerX 10.1.1.400.6757, doi:10.1002/rsa.10101.
^ 를 클릭합니다Saks, M.; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000), "Low discrepancy sets yield approximate min-wise independent permutation families", Information Processing Letters, 73 (1–2): 29–32, CiteSeerX 10.1.1.20.8264, doi:10.1016/S0020-0190(99)00163-5.
^ 인디크, 표트르"약간의 최소 독립 해시 함수 패밀리입니다."알고리즘 저널 38.1(2001): 84-90.
^ Manasse, Mark (2012). On the Efficient Determination of Most Near Neighbors: Horseshoes, Hand Grenades, Web Search, and Other Situations when Close is Close Enough. Morgan & Claypool. p. 72. ISBN 9781608450886.
^ Chum, Ondřej, 필빈, 제임스 아이사드, 마이클 Zisserman, 앤드류(2007년),"동일한 이미지와 샷 탐지 스케일러블", 6ACM국제 회의 이미지 및 Cideo 검색(CIVR'07), 회보를 대신하여 서명함. 549–556, doi:10.1145/1282280.1282359, 아이 에스비엔 9781595937339, S2CID 3330908, Chum, Ondřej, 필빈, 제임스 Zisserman, 앤드류(2008년),".가까운 이미지 감지:min-hash과tf-idf weighting", 영국의 머신 비전 회의(PDF)회보 vol. 3페이지의 주 4중복.
^ 를 클릭합니다Cohen, E.; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P.; Motwani, R.; Ullman, J. D.; Yang, C. (2001), "Finding interesting associations without support pruning", IEEE Transactions on Knowledge and Data Engineering, 13 (1): 64–78, CiteSeerX 10.1.1.192.7385, doi:10.1109/69.908981.
^ ^a ^b Ondov, Brian D.; Treangen, Todd J.; Melsted, Páll; Mallonee, Adam B.; Bergman, Nicholas H.; Koren, Sergey; Phillippy, Adam M. (2016-06-20). "Mash: fast genome and metagenome distance estimation using MinHash". Genome Biology. 17 (1): 132. doi:10.1186/s13059-016-0997-x. ISSN 1474-760X. PMC 4915045. PMID 27323842.
^ "Welcome to sourmash! — sourmash 1.0 documentation". sourmash.readthedocs.io. Retrieved 2017-11-13.
^ Berlin, Konstantin; Koren, Sergey; Chin, Chen-Shan; Drake, James P; Landolin, Jane M; Phillippy, Adam M (2015-05-25). "Assembling large genomes with single-molecule sequencing and locality-sensitive hashing". Nature Biotechnology. 33 (6): 623–630. doi:10.1038/nbt.3238. ISSN 1546-1696. PMID 26006009. S2CID 17246729.
^ Jain, Chirag; Rodriguez-R, Luis M.; Phillippy, Adam M.; Konstantinidis, Konstantinos T.; Aluru, Srinivas (December 2018). "High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries". Nature Communications. 9 (1): 5114. doi:10.1038/s41467-018-07641-9. PMC 6269478. PMID 30504855.
^ 를 클릭합니다Andoni, Alexandr; Indyk, Piotr (2008), "Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions", Communications of the ACM, 51 (1): 117–122, CiteSeerX 10.1.1.226.6905, doi:10.1145/1327452.1327494, S2CID 6468963.
^ 를 클릭합니다Zadeh, Reza; Goel, Ashish (2012), "Dimension Independent Similarity Computation", arXiv:1206.2082 [cs.DS].
^ 를 클릭합니다Henzinger, Monika (2006), "Finding near-duplicate web pages: a large-scale evaluation of algorithms", Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 284, doi:10.1145/1148170.1148222, ISBN 978-1595933690, S2CID 207160068.
^ 를 클릭합니다Charikar, Moses S. (2002), "Similarity estimation techniques from rounding algorithms", Proceedings of the 34th Annual ACM Symposium on Theory of Computing, p. 380, doi:10.1145/509907.509965, ISBN 978-1581134957, S2CID 4229473.
^ 를 클릭합니다Gurmeet Singh, Manku; Jain, Arvind; Das Sarma, Anish (2007), "Detecting near-duplicates for web crawling", Proceedings of the 16th International Conference on World Wide Web (PDF), p. 141, doi:10.1145/1242572.1242592, ISBN 9781595936547, S2CID 1414324.
^ 를 클릭합니다Das, Abhinandan S.; Datar, Mayur; Garg, Ashutosh; Rajaram, Shyam; et al. (2007), "Google news personalization: scalable online collaborative filtering", Proceedings of the 16th International Conference on World Wide Web, p. 271, doi:10.1145/1242572.1242610, ISBN 9781595936547, S2CID 207163129.

[b97-1] 브로 더는 안드레이 Z(1997년),"그 유사점과 문서들의 봉쇄에", 압축과 Sequences 간의 복잡:.집, 포시 타노, Amalfitan 연안, 살레르노, 이탈리아, 6월 11-13, 1997년(PDF), IEEE,를 대신하여 서명함. 21–29, CiteSeerX 10.1.1.24.779, doi:10.1109/SEQUEN.1997.666900, 아이 에스비엔 978-0-8186-8132-5, S2CID 11748509, 원본(PDF)에서 2015-01-31에 보관 시 2014-01-18 돌려받지 못 했다.

[bcfm-2] 를 클릭합니다Broder, Andrei Z.; Charikar, Moses; Frieze, Alan M.; Mitzenmacher, Michael (1998), "Min-wise independent permutations", Proc. 30th ACM Symposium on Theory of Computing (STOC '98), New York, NY, USA: Association for Computing Machinery, pp. 327–336, CiteSeerX 10.1.1.409.9220, doi:10.1145/276698.276781, ISBN 978-0897919623, S2CID 465847.

[3] 를 클릭합니다Vassilvitskii, Sergey (2011), COMS 6998-12: Dealing with Massive Data (lecture notes, Columbia university) (PDF), archived from the original (PDF) on 2018-10-24.

[4] Chum, Ondrej; Philbin, James; Zisserman, Andrew (2008), "Near Duplicate Image Detection: min-Hash and tf-idf Weighting." (PDF), BMVC, 810: 812–815

[5] Shrivastava, Anshumali (2016), "Exact weighted minwise hashing in constant time", arXiv:1602.08393 [cs.DS]

[6] Ioffe, Sergey (2010), "Improved consistent sampling, weighted minhash and L1 sketching" (PDF), Data Mining (ICDM), 2010 IEEE 10th International Conference on: 246–255, CiteSeerX 10.1.1.227.9749, doi:10.1109/ICDM.2010.80, ISBN 978-1-4244-9131-5, S2CID 9970906

[7] Moulton, Ryan; Jiang, Yunjiang (2018), "Maximally Consistent Sampling and the Jaccard Index of Probability Distributions", 2018 IEEE International Conference on Data Mining (ICDM), pp. 347–356, arXiv:1809.04052, doi:10.1109/ICDM.2018.00050, ISBN 978-1-5386-9159-5, S2CID 49746072

[8] 를 클릭합니다Matoušek, Jiří; Stojaković, Miloš (2003), "On restricted min-wise independence of permutations", Random Structures and Algorithms, 23 (4): 397–408, CiteSeerX 10.1.1.400.6757, doi:10.1002/rsa.10101.

[9] 를 클릭합니다Saks, M.; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000), "Low discrepancy sets yield approximate min-wise independent permutation families", Information Processing Letters, 73 (1–2): 29–32, CiteSeerX 10.1.1.20.8264, doi:10.1016/S0020-0190(99)00163-5.

[10] 인디크, 표트르"약간의 최소 독립 해시 함수 패밀리입니다."알고리즘 저널 38.1(2001): 84-90.

[11] Manasse, Mark (2012). On the Efficient Determination of Most Near Neighbors: Horseshoes, Hand Grenades, Web Search, and Other Situations when Close is Close Enough. Morgan & Claypool. p. 72. ISBN 9781608450886.

[12] Chum, Ondřej, 필빈, 제임스 아이사드, 마이클 Zisserman, 앤드류(2007년),"동일한 이미지와 샷 탐지 스케일러블", 6ACM국제 회의 이미지 및 Cideo 검색(CIVR'07), 회보를 대신하여 서명함. 549–556, doi:10.1145/1282280.1282359, 아이 에스비엔 9781595937339, S2CID 3330908, Chum, Ondřej, 필빈, 제임스 Zisserman, 앤드류(2008년),".가까운 이미지 감지:min-hash과tf-idf weighting", 영국의 머신 비전 회의(PDF)회보 vol. 3페이지의 주 4중복.

[13] 를 클릭합니다Cohen, E.; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P.; Motwani, R.; Ullman, J. D.; Yang, C. (2001), "Finding interesting associations without support pruning", IEEE Transactions on Knowledge and Data Engineering, 13 (1): 64–78, CiteSeerX 10.1.1.192.7385, doi:10.1109/69.908981.

[:0-14] Ondov, Brian D.; Treangen, Todd J.; Melsted, Páll; Mallonee, Adam B.; Bergman, Nicholas H.; Koren, Sergey; Phillippy, Adam M. (2016-06-20). "Mash: fast genome and metagenome distance estimation using MinHash". Genome Biology. 17 (1): 132. doi:10.1186/s13059-016-0997-x. ISSN 1474-760X. PMC 4915045. PMID 27323842.

[15] "Welcome to sourmash! — sourmash 1.0 documentation". sourmash.readthedocs.io. Retrieved 2017-11-13.

[16] Berlin, Konstantin; Koren, Sergey; Chin, Chen-Shan; Drake, James P; Landolin, Jane M; Phillippy, Adam M (2015-05-25). "Assembling large genomes with single-molecule sequencing and locality-sensitive hashing". Nature Biotechnology. 33 (6): 623–630. doi:10.1038/nbt.3238. ISSN 1546-1696. PMID 26006009. S2CID 17246729.

[17] Jain, Chirag; Rodriguez-R, Luis M.; Phillippy, Adam M.; Konstantinidis, Konstantinos T.; Aluru, Srinivas (December 2018). "High throughput ANI analysis of 90K prokaryotic genomes reveals clear species boundaries". Nature Communications. 9 (1): 5114. doi:10.1038/s41467-018-07641-9. PMC 6269478. PMID 30504855.

[18] 를 클릭합니다Andoni, Alexandr; Indyk, Piotr (2008), "Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions", Communications of the ACM, 51 (1): 117–122, CiteSeerX 10.1.1.226.6905, doi:10.1145/1327452.1327494, S2CID 6468963.

[19] 를 클릭합니다Zadeh, Reza; Goel, Ashish (2012), "Dimension Independent Similarity Computation", arXiv:1206.2082 [cs.DS].

[20] 를 클릭합니다Henzinger, Monika (2006), "Finding near-duplicate web pages: a large-scale evaluation of algorithms", Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 284, doi:10.1145/1148170.1148222, ISBN 978-1595933690, S2CID 207160068.

[21] 를 클릭합니다Charikar, Moses S. (2002), "Similarity estimation techniques from rounding algorithms", Proceedings of the 34th Annual ACM Symposium on Theory of Computing, p. 380, doi:10.1145/509907.509965, ISBN 978-1581134957, S2CID 4229473.

[22] 를 클릭합니다Gurmeet Singh, Manku; Jain, Arvind; Das Sarma, Anish (2007), "Detecting near-duplicates for web crawling", Proceedings of the 16th International Conference on World Wide Web (PDF), p. 141, doi:10.1145/1242572.1242592, ISBN 9781595936547, S2CID 1414324.

[23] 를 클릭합니다Das, Abhinandan S.; Datar, Mayur; Garg, Ashutosh; Rajaram, Shyam; et al. (2007), "Google news personalization: scalable online collaborative filtering", Proceedings of the 16th International Conference on World Wide Web, p. 271, doi:10.1145/1242572.1242610, ISBN 9781595936547, S2CID 207163129.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[21]

[22]

[23]

Search

미니해시

네임스페이스

더

목차

Jaccard 유사성과 최소 해시 값