Near Duplicate Documents Detection - aragorn/home GitHub Wiki

수억건 이상의 문서 집합에서 유사 문서를 찾아 고유한 중복ID를 할당하는 시스템을 어떻게 구현할 것인지 살펴본다.

배경

뉴스, 블로그, 웹문서, 이미지, 쇼핑상품 등을 대상으로 하는 검색서비스를 구현할 때, 수억건 이상의 다수 문서를 검색엔진에 색인하여 서비스를 제공하게 된다. 다수의 데이터를 색인하는 경우, 실질적으로 동일한 문서 또는 유사한 문서가 다수 존재하게 되며, 이러한 중복 문서들은 검색결과의 품질을 떨어뜨리는 원인이 된다. 동시에 문서의 중복을 빠르고 정확하게 판별하는 전처리 시스템을 갖추게 되면, 중복된 문서의 정보를 이용해 주요 랭킹 요소로 사용할 수 있다.

개요

수억건 이상의 문서데이터에 대해 유사문서 쌍을 찾아내고 고유ID 또는 원본 문서를 찾아내는 알고리즘과 시스템의 구현 방법을 제시한다. 알고리즘 측면에서 다차원 공간에서 다수의 벡터가 주어진 경우, 모든 벡터들에 대해 Nearest neighbour search 결과를 도출해 내는 시스템을 구현하는 것이다. Locality sensitive hashing, Permutation and prefix matching 을 적용하여 시간 복잡도를 낮추는 대량 데이터 처리 방법을 제시한다. 높은 정확도, 재현률을 보장할 수 있는 알고리즘을 적용하기 위해, Locality sensitive hashing 과 병행하여 계산 비용이 높은 비교 알고리즘을 조합하는 기술적 방법을 제시한다. 아울러, 알고리즘과 시스템의 품질을 측정하기 위해 샘플 데이터에 대한 수작업 정답데이터를 구성하고, 이를 기반으로 정확률, 재현률을 측정하는 방법을 소개한다.

목차

• 문서 단위로 유사 중복을 판별하는 방법 - 1차 완료
  • 유사도를 계산하는 주요 알고리즘
• 여러 문서의 유사 중복 계산의 복잡도 - 1차 완료
• SimHash 계산 방법 - 1차 완료
• Hamming distance of hash value - 1차 완료
• Large scale similarity calculation by permutation and prefix matching - 1차 완료
  • Permutation 생성 방식 변경
  • 재귀적인 Permutation and prefix matching 방식
• Hadoop 기반 Map-Reduce 처리를 위한 입출력 설계 - 작성 중
  • 절차 1) 중복쌍 찾기, 2) 유사 중복쌍 찾기, 3) 유사 중복쌍의 중복제거, 4) 원본문서 찾기, 5) 중복쌍과 유사 중복쌍의 병합
  • 중복 해시값의 전처리
  • LSH 와 Uncompressed text 의 병합
• Online Processing of Streaming Data - 준비 중
  • 데이터가 지속적으로 증가
  • Streaming Data 가 single node 의 용량을 넘어서는 경우
• 유사 중복쌍에서 대표 선정하기 - 준비 중
• 중복쌍의 품질 평가
  • 샘플 테스트 구성
  • 수작업 중복검사 도구
  • SimHash 평가
• 레퍼런스

문서 단위로 유사 중복을 판별하는 방법

텍스트로 구성된 문서에서 유사 중복을 판별하는 방법으로 여러가지가 알고리즘이 있다. 이 가운데, 먼저 한 쌍의 문서에 대해 유사 중복을 판별하는데 있어, 높은 정확률(Precision), 재현률(Recall) 을 보여주는 알고리즘을 구현한다.

일반적으로 문서를 단어 단위로 구분하여 Bag of Words 를 구성하는 방법이 있는데, 이는 문장 내의 단어 구성이 유사하면, 실질적으로 상당히 다른 문장이더라도 유사도가 높게 측정되는 제약이 있다.

표절, 스크랩, 일부 단어를 대체하는 어뷰징 포스팅, 미러링 페이지 등 실질적으로 문장 구성이 거의 유사한 텍스트의 중복을 판별하는 방법으로는 어절 단위의 Shingle 을 사용하는 것이 적당하다. 한국어 텍스트를 기준으로 실험한 결과, 문장부호를 제거한 어절 단위 Trigram Shingle 을 사용하는 경우, 정확율과 재현율이 모두 높게 나오는 결과를 얻을 수 있었다.

어절 단위 Trigram Shingle 을 적용하는 경우, 문서 내에서 개별 feature 는 Trigram Shingle 을 사용하고, 유사도는 이 feature들을 대상으로 Jaccard similarity coefficient를 계산하는 방법으로 좋은 결과를 얻을 수 있다.

Jaccard similarity coefficient 는 유사도 계산 과정을 직접 확인하고, 직관적으로 이해하기 용이하다.

유사도를 계산하는 주요 알고리즘

• Cosine similarity

  좁은 의미의 cosine similarity는 두 벡터의 내적을 두 벡터의 절대값으로 나눈 값이다. 두 벡터가 얼마나 방향이 일치하는지 정도를 알려주는 값이다. 텍스트 문서가 주어진 경우, cosine similarity 를 계산하는 일반적인 접근 방법은 문서 내의 단어를 벡터 공간의 기저(base)로 간주하고, 이 단어들의 출현 빈도를 벡터 성분(vector component)의 크기로 표현하는 것이다. 다른 말로 표현하면, term frequency vector 라 표현한다.

  Cosine similarity 의 특징은 벡터 성분의 크기가 비슷한 정도를 존중하는 것으로, 문서들에서 동일 단어가 나타났더라도, 그 출현 빈도가 유사한 경우, 더 높은 유사도 점수를 갖는 특징을 갖는다. 반면에 단어의 출현 순서는 유사도에 무관하다.

  Cosine similarity 는 0 ~ 1 사이의 값을 갖는다.

• Edit distance

  두 문자열이 주어졌을 때, 하나의 문자열에 몇 번의 수정 연산을 적용하여 다른 문자열로 변형시킬 수 있는지 알아내어, 그 최소 수정 연산의 횟수로 문자열의 다른 정도 또는 비슷한 정도를 계산하는 알고리즘을 편집 거리(Edit distance)라고 한다.

  Edit distance 를 계산할 때에는 문자열을 구성하는 문자 또는 기호의 최소단위가 정의되어야 한다. 한글의 경우는 자소, 음절, 어절 단위를 최소단위로 정의할 수 있으며, 영어의 경우에는 알파벳, 단어를 최소단위로 정의할 수 있다.

  편집 연산을 적절히 정의하는 것도 필요하다. 일반적으로는 Levenshtein distance의 연산을 사용하며, edit distance 라고 하면 보통은 Levenshtein distance 를 가리킨다. Levenshtein distance 에서는 기호에 대한 삽입, 삭제, 대체, 세 가지 연산을 사용한다. 각 연산의 비용을 동일하게 볼 수도 있고, 적당한 가중치를 부여할 수도 있다.

  Edit distance 를 이용해 두 입력의 유사도를 0 ~ 1 사이로 계산하는 방법은 수학적으로 의미가 없어 사용하지 않는다. Edit distance 는 0 이상의 값으로 표현된다.

• Longest common subsequence

  여러 아이템을 갖는 순서를 가진 나열(순서열, sequence)이 두 개 주어졌을 때, 아이템이 출현한 순서가 두 나열에서 공통적으로 존재하면서, 가장 길이가 긴 순서를 찾아내는 알고리즘이다. 직관적으로 간단히 이해하겠다면, 유닉스의 표준 도구인 diff(1)의 작동 방식을 살펴보면 된다. Edit distance 를 계산할 때, 삽입, 삭제, 두 가지 연산만을 적용하는 것과 동등한 문제이기도 하다.

  diff(1)의 경우, 아이템 단위를 텍스트 파일의 줄(line)로 보는 것이다. 두 텍스트파일에서 어떤 줄의 문자열이 일치하면 동일한 아이템으로 간주하고, 줄 단위로 삽입, 삭제 연산을 계산하게 된다. 텍스트의 유사도를 계산할 때, 영어는 단어나 알파벳, 한국어는 어절, 음절, 자소 등을 아이템 단위로 삼을 수 있으며, 각각의 경우 유사도 계산값이 달라질 것이므로, 의도하는 목적에 따라 적절한 아이템 기준을 잡아야 한다.

  diff(1) 를 실행할 때, 다음과 같이 옵션을 지정하는 경우, 두 파일의 Longest common subsequence 만을 출력해서 살펴볼 수 있다.

  diff --old-line-format='' --new-line-format='' --unchanged-line-format='%L' file1.txt file2.txt

  Longest common subsequence는 Longest common substring 과 비슷해 보이지만, 다른 문제이다. 전자는 아이템의 출현 순서가 일치하면 되고, 그 중간에 다른 아이템이 삽입되어 있어도 무방하다. 후자는 substring 이기에, 아이템의 출현 사이에 다른 아이템이 삽입되어 있으면 안 된다.

  Longest common subsequence 를 구한 경우, 순서열 x의 길이를 |x|라 표현할 때, Resemblance(A, B) = |LCS| / ( |A| + |B| - |LCS| ) 가 된다. 즉, LCS길이를 (A길이 + B길이 - LCS길이) 로 나눈 값이다.

  Longest common subsequence 기반의 Resemblance 는 0 ~ 1 사이의 값을 갖는다.

• Hamming distance

  길이가 동일한 문자열에 대해 각 위치의 문자가 동일하지 않은 것의 갯수를 Hamming distance라 한다. 이론적으로는 비교하는 대상이 문자 또는 기호이고, 문자나 기호(symbol)를 필요에 따라 정의하면 된다. 일반적인 응용사례에서는 이진 문자열을 사용하며, bit 단위로 동일한지 여부를 판단한다. 즉, 기호를 bit 로 보는 것이다.

  long d1  = 0b0100_1010_1000_1110_1001_0100_1001_0010
  long d2  = 0b1100_1110_1000_1010_1001_0100_1011_0010
  
  d1 ^ d2 == 0b1000_0100_0000_0100_0000_0000_0010_0000
  hamming_distance(d1, d2) == hamming_weight( d1 ^ d2 ) == 4
  

  위의 예시와 같이 길이가 동일한 두 값을 Binary String 간주하고, 두 문자열의 XOR 을 계산한 후, 비트값 1의 갯수를 센 값이 Hamming distance 이다.

• Jaccard index

  주어진 두 집합에서 합집합의 크기 대비 교집합의 크기를 계산한 값이다. Jaccard(A, B) = | 교집합(A,B) | / | 합집합(A,B) |로 표현할 수 있다. 문자열을 비교할 때에는 문자열을 적절한 기준으로 구분하여 원소로 간주하여, 이 원소들의 집합을 사용하며, 영문의 경우에는 단어를 원소로 간주하는 방식을 쓰는 경우가 많다. 문자열을 집합으로 치환하기 때문에, 문자열 내의 단어 출현 순서를 무시하게 되는 효과가 발생한다.

  Jaccard index 는 0 ~ 1 사이의 값을 가지며, 동일한 두 집합의 Jaccard index 는 1 이 된다.

• Euclidean distance

  2차원 공간 또는 3차원 공간에서 일상생활에서 인지하는 두 장소의 거리이다. 다차원 공간을 다룰 때에는 Euclidean distance 가 유용하지 않기 때문에, 보통 사용하지 않는다. 자세한 것은 Why is Euclidean distance not a good metric in high dimensions? 라는 질의 응답을 참고하면 도움이 된다.

• 요약

  여러가지 유사도 계산 알고리즘이 알려져 있으며, 이 가운데 어느 것이 우월하거나 더 좋다고 일반화할 수 없다. 필요한 응용 사례에 가장 적절한 방식을 선택하는 것이 좋으며, 이를 위해 각 알고리즘의 특징을 잘 파악할 필요가 있다.

  알고리즘	유사도값	순서	빈도	길이 제약
  Cosine similarity	0 ~ 1	Ignored	Respected	No
  Levenshtein distance	0 이상 거리	Respected	Respected	No
  Longest common subsequence	0 ~ 1	Respected	Respected	No
  Hamming distance	0 이상 거리	Respected	Respected	Yes
  Jaccard index	0 ~ 1	Ignored	Ignored	No

  위 테이블에서 각 항목의 의미는 다음과 같다.

  • 유사도값 : 0 ~ 1 사이의 유사도값을 얻는지, 또는 0 이상의 거리를 얻는지 여부.
  • 순서 : 유사도를 판별하는 개별 feature 들의 출현 순서가 유사도에 반영되면 Respected, 아니면 Ignored.
    • Jaccard index 는 집합으로 데이터를 다루기에 feature 의 출현 순서를 무시하게 되는데, Shingle 과 같은 기법으로 feature 의 출현 순서에 따라 묶음을 만들게 되면, feature 의 출현 순서를 유사도에 반영하게 되는 효과를 얻게 된다.
  • 빈도 : 유사도를 판별하는 개별 feature 들의 출현 빈도가 유사도에 반영되면 Respected, 아니면 Ignored.
    • 순서가 유사도에 반영되면, 빈도가 유사도에 반영되는 것은 당연하다.
  • 길이 제약 : 비교 대상 값의 길이가 가변 길이이거나 서로 달라도 되는지 여부로 Hamming distance 는 길이가 동일해야 한다.

여러 문서의 유사 중복 계산의 복잡도

Bag of Words 를 적용하든, Trigram Shingle 을 적용하든, 문서 단위의 유사 중복 계산 방식은 기본적으로 주어진 한 쌍의 문서에 대해 유사도를 측정한다. N개의 문서집합이 주어진 경우, 모든 문서에 대해 서로 유사도를 측정하는 것이 간단한 접근 방법이며, 이 경우 N x ( N - 1 )의 time complexity 를 갖는 계산을 수행해야 한다. 수만 건 이상의 문서 집합에 대해서는 실질적으로 적용할 수 없는 방법이다.

이 문제는 다차원 공간에서 Nearest neighbor search 문제로 볼 수 있다.

이 문제를 해결하는 방법 가운데, 실용적으로 접근 가능한 방법으로 Locality sensitive hashing이 잘 알려져 있다. Locality sensitive hashing 은 다차원 벡터의 차원을 축소시켜 계산량을 줄이는 기법이며, 차원을 축소시키는 hash function 을 적용시킬 때, 암호화 hash 와 달리, 유사한 항목들의 충돌 확률이 높이는 hash function 을 적용한다. hash value 을 도출한 후에는, 이 hash value 사이의 hamming distance 가 가까운 것을 유사한 항목으로 볼 수 있다.

Locality sensitive hashing 구현 방법으로 MinHash(min-wise independent permutations), SimHash 등 여러가지가 알려져 있는데, 구현이 간단하면서 충분히 좋은 성능을 보여주는 방식으로 SimHash 가 적당하다.

SimHash 계산 방법

SimHash 계산 방법을 간단히 정리하면 다음의 슬라이드로 요약된다.

• 문서에서 feature, weight 를 추출한다. 여러가지 방식으로 feature, weight 를 추출할 수 있는데, 한국어 문서의 경우, 문장부호를 제외한 Trigram Shingle 을 사용할 수 있다. 이때, weight 는 의미가 없어진다. 단어를 사용하는 경우에는 Inverse Document Frequency 와 같은 weight를 사용할 수 있는데, Trigram Shingle 의 경우에는 IDF 가 의미가 없어지기에 1 로 둘 수 있다. 그러나, weight 를 적절히 할당하여 성능일 높이겠다면, 실험을 통해 탐색할 수 있을 것이다.

  • "SimHash 계산 방법을 간단히 정리하면 다음의 슬라이드로 요약된다."라는 문장이 주어진 경우, Trigram Shingle을 아래와 같이 추출할 수 있다.

    ```Groovy
    [
      'SimHash 계산 방법을',
      '계산 방법을 간단히',
      '방법을 간단히 정리하면',
      '간단히 정리하면 다음의',
      '정리하면 다음의 슬라이드로',
      '다음의 슬라이드로 요약된다'
    ]
    ```
    

• feature 에 대해 적당한 hash function 을 적용한다. 최종적으로 64bit fingerprint 를 얻겠다면, 이 단계에서 64bit hash value를 얻어야 한다. MD5, SHA1 등 일반적으로 알려진 암호화 hash를 사용할 수 있다. Trigram Shingle에 MD5를 적용하겠다면, 'SimHash 계산 방법을'와 같은 문자열에 대해 MD5 digest를 얻은 후, 상위 64bit 또는 하위 64bit 을 선택하면 된다.

• 여러 feature 에 대해 얻은 64bit hash value 에 대해, 비트 단위로 0 또는 1 의 값을 갖는 리스트를 만든다. 64bit hash value를 계산하였으므로, 64개의 0 또는 1의 값을 갖는 리스트가 각 feature 별로 만들어질 것이다.

• 여러 feature 의 0 또는 1의 값을 갖는 리스트에 대해, 1은 +weight, 0은 -weight로 간주하여, 리스트의 같은 위치의 값들을 합산한다. 슬라이드의 예시를 설명한다면, 다음과 같다.

  • 13 = +w1 + w2 + ... - wn
  • 108 = -w1 + w2 + ... - wn
  • -22 = -w1 - w2 + ... + wn
  • -5 = +w1 - w2 + ... - wn
  • -32 = +w1 - w2 + ... - wn
  • 55 = -w1 - w2 + ... + wn

• 합산된 값들을 다시 1, 0 의 비트벡터로 전환한다. 0 이상의 값은 1, 0 미만의 값은 0 으로 치환하는 방식을 적용하면 된다. 경계값인 0에 대해 1 또는 0 어느 것을 할당하여도 무방하나, 보통은 0 이상의 값에 대해 1을 할당하는 방식으로 구현하고 있다.

• 이 비트벡터를 SimHash fingerprint 값으로 사용한다.

Hamming distance of hash value

SimHash fingerprint 를 계산하면, 이 fingerprint 를 이용해 유사한 정도 또는 다른 정도를 계산할 수 있다. 두 fingerprint의 Hamming distance를 다른 정도로 사용한다. 주어진 두 해시값의 hamming distance 는 두 값의 XOR 값에서 hamming weight 또는 population count 를 계산하면 된다.

long d1  = 0b0100_1010_1000_1110_1001_0100_1001_0010
long d2  = 0b1100_1110_1000_1010_1001_0100_1011_0010

d1 ^ d2 == 0b1000_0100_0000_0100_0000_0000_0010_0000
hamming_weight( d1 ^ d2 ) == 4

SimHash fingerprint 가 좋은 품질의 locality sensitive hashing 이라는 것의 의미는, 64bit fingerprint를 기준으로 hamming distance 3~4 이내인 쌍을 유사중복으로 간주할 때, Precision과 Recall이 높게 나온다는 것이다. 실제 구현한 SimHash fingerprint 가 그런 특성을 갖는지, 샘플 데이터를 이용해 검증평가하는 과정이 필요하다.

일반적으로는 64bit fingerprint 를 기준으로 hamming distance 3, 4 또는 5 이내인 것을 유사 중복으로 간주하는 방법을 많이 사용한다. 어떤 값을 threshold 로 사용할 것인지는 품질 측정을 통해 판단하는 것이 좋으나, Recall 을 높이겠다면 큰 값을 사용하고, Precision 을 높이겠다면 작은 값을 사용하면 된다.

가변길이인 본문 전체에 대해 Bag of Words 또는 Trigram Shingle 기반으로 Jaccard index 를 이용해 중복 정도를 판별하는 방법과 달리, Fingerprint 의 Hamming distance 로 유사 여부를 판단하는 것은 문서 단위로 8byte 정도의 짧은 고정길이 값을 이용해 유사도를 계산할 수 있다는 장점이 있다.

그러나, 여러 문서에 대해 유사도를 계산하기 위해서는, 단순하게 접근할 경우 N x ( N - 1 )의 time complexity를 갖는 것은 동일하다.

Hamming weight 계산을 빠르게 처리할 수 있는 알고리즘, POPCNT 등의 CPU hardware instruction이 알려져 있다. 그러나 Hadoop을 사용하는 경우, 성능 차이를 구분하기 어렵다.

Large scale similarity calculation by permutation and prefix matching

참고 : Gurmeet Singh, Manku; Das Sarma, Anish (2007), "Detecting near-duplicates for web crawling", Proceedings of the 16th international conference on World Wide Web. ACM,. (http://www.wwwconference.org/www2007/papers/paper215.pdf)

여러 문서의 64bit fingerprint 가 주어진 경우, hamming distance 4 이내를 유사 중복이라고 가정하자. 5 이상의 값을 갖는 경우는 유사 중복이 아니므로, 유사도를 계산하지 않아도 된다. 5 이상의 값을 갖는 쌍들에 대해 유사도를 검사하지 않고, 4 이내의 값을 갖는 쌍의 후보들에 대해서만 유사도를 계산해 보는 알고리즘을 적용하면, O ( N log(N) ) 의 시간복잡도에 모든 중복을 검출할 수 있으며, 이 알고리즘을 Permutation and prefix matching 이라고 하겠다.

Manku 의 논문에서 구체적인 구현 방법이 제시되어 있으나, 이 방법을 지칭하는 이름이 붙어 있지 않은 것 같다. Naidan(2015)의 논문에서는 Permutation Search Method 라고 지칭하기도 한다. 조금 긴 이름이기는 하나, Permutation and prefix matching 이라고 지칭하는 것이 적당할 것으로 생각된다.

구체적인 예시와 함께 이 알고리즘의 작동 방식을 설명하면 다음과 같다.

1. 64bit fingerprint 에서 4개 이내의 비트가 다른 경우를 찾고자 한다.

2. 64bit fingerprint 를 적당히 5개 영역으로 구분한다. 앞에서부터 13bit, 13bit, 13bit, 13bit, 12bit 로 가능하면 크기가 비슷하게 구분한다. 이 영역을 앞에서부터 a, b, c, d, e 라고 이름 붙인다.

   long d1  = 0b01001010_10001110_10010100_10010010_11001110_10001010_10010100_10110010
            ~~~~~~~~~~~~~~_______________~~~~~~~~~~~~~~_______________~~~~~~~~~~~~~
                  a              b              c             d             e
   

3. fingerprint d1, d2 가 주어진 경우, 이 둘이 유사 중복이라면, 서로 다른 4개 이내의 비트가 a, b, c, d, e 영역에 위치할 수 있다. 이때 영역의 수가 5개 이므로, 5개의 영역 가운데 적어도 하나는 d1, d2 가 서로 일치하게 된다. 다르게 표현하면, 비둘기 집의 원리에 따라, 4개 이내의 비트가 5개 영역에 위치한 경우, 적어도 1개 이상의 영역은 해당 비트가 존재하지 않는다. 따라서, d1, d2 는 a, b, c, d, e 중 적어도 하나의 영역은 값이 일치한다.

4. fingerprint 의 5개 영역의 순서를 바꾸는 조합, permutation 을 만든다. 이 경우는 abcde, bcdea, cdeab, deabc, eabcd 와 같은 다섯개 조합을 만든다.

• abcde 조합의 경우, a를 기준으로 fingerprint를 정렬하면, a가 일치하는 fingerprint값들이 정렬된 리스트 중 한 곳에 몰리게 된다. a의 값이 일치하는 fingerprint들에 대해서 bcde 영역을 대상으로 hamming weight를 계산하여 4 이하인 경우를 찾으면 된다.
• bcdea 조합의 경우, b를 기준으로 fingerprint를 정렬하면, b가 일치하는 fingerprint값이 들이 한 곳에 몰리게 된다. cdea 영역을 대상으로 hamming weight를 계산한다.
• 나머지 조합의 경우에도 마찬가지로 계산한다.

5. 각 permutation에 대해 첫번째 영역을 prefix라 하고, prefix가 일치하는 fingerprint값들에 대해서만 hamming weight를 N ( N - 1 ) 시간복잡도를 적용하여 계산한다. 각 조합에 대해 유사도 검사를 완료하면, 주어진 fingerprint 와 max hamming distance(=4)에 대해, 유사중복 쌍을 빠짐없이 찾을 수 있게 된다.

• prefix 가 일치하는 fingerprint 값들을 효과적으로 찾기 위해, prefix 를 기준으로 전체 데이터를 정렬하면 된다.

위와 같은 경우, prefix가 일치하는 문서가 평균적으로 몇 개 나타날 것인지 예측해 보자. 문서가 100억개 주어지고, 64bit fingerprint, max hamming distance = 4인 경우, 가장 작은 bit를 갖는 영역의 크기가 12bit 이다. 12bit 값의 cardinality는 4096 이다. 100억개의 문서에 대해 12bit prefix가 일치하는 문서들의 수는 평균 100억 / 4096 = 약 24,414 이 된다.

위의 방식으로 중복 검사를 하는 경우, 평균적으로 24,414 개의 문서들에 대해 N x ( N - 1 )의 hamming weight를 계산하여 중복 쌍을 찾아야 한다.

Permutation 생성 방식 변경

실제 구현에서는 다른 방식의 조합을 적용하여 더 효과적인 구현을 할 수 있다. max hamming distance 를 m 이라 하면, m+1 개의 영역을 나누지 않고, m+2 개의 영역을 나눌 수 있다. m=4인 경우, 6개의 영역으로 나누게 되며, 모든 중복 쌍은 적어도 2개 이상의 영역의 값이 일치하게 된다. 이 경우, prefix 와 나머지 영역을 다음과 같은 조합으로 만들 수 있다.

• ab + cdef, ac + bdef, ad + bcef, ae + bcdf, af + bcde : 5개
• bc + adef, bd + acef, be + acdf, bf + acde : 4개
• cd + abef, ce + abdf, cf + abde : 3개
• de + abcf, df + abce : 2개
• ef + abcd : 1개

도합 15개의 조합이 만들어지며, 각 영역의 크기는 10~11bit 가 된다. 일반화하면, m+2 개의 영역을 만드는 경우, ( m + 2 ) x ( m + 1 ) / 2 의 조합이 만들어지며, 영역의 크기는 floor( 64 / ( m + 2 ) )가 된다. 이때, prefix가 2개 영역의 조합이 되므로, m = 4인 경우, prefix의 크기가 최소 20bit 가 된다.

20bit 의 cardinality는 1,048,576 이며, 100억개의 문서가 주어졌을 때, 20bit prefix가 일치하는 문서의 수는 평균 100억 / 1,048,576 = 약 95가 된다. 즉, N x ( N - 1 )의 비교를 할 문서수가 95가 되기에, 시간 복잡도가 크게 줄어드는 결과를 얻을 수 있다.

대신, ( m + 2 ) x ( m + 1 ) / 2의 fingerprint 조합을 만들어내고, 각 조합에 대해 prefix matching 을 실행하는 부담이 생긴다.

Permutation 을 다양하게 생성하는 방식에 대해서는 Manku(2007)의 논문에서 상세히 다루고 있다.

재귀적인 Permutation and prefix matching 방식

Fingerprint를 m + 1 개 영역으로 나누는 경우, m = 4 이면, prefix 가 일치하는 조건의 문서수가 평균적으로 약 24,414 개 발생한다. 실제로는 이보다 훨씬 더 큰 수의 문서들이 몰리는 경우도 발생한다. 수만~수십만의 문서의 prefix가 일치하는 경우, N x ( N - 1 )의 시간복잡도로 비교하는 것은 상당한 부담이 된다.

64bit fingerprint에서 가장 작은 prefix는 12bit이며, 남은 fingerprint는 52bit 이다. 남은 fingerprint 에 대해 다시 permutation and prefix matching 방식을 적용할 수 있으며, 이 경우 fingerprint 조합 테이블을 만드는 공간 복잡도를 감수할 수 있으면, 시간 복잡도를 충분히 줄일 수 있다.

52bit 의 fingerprint 를 갖는 문서가 10만개 주어진 경우, 이 가운데 다시 4개 이하의 hamming distance를 갖는 중복 쌍을 찾으면 된다. 처음 64bit fingerprint 가 주어졌을 때와 마찬가지로, 52bit fingerprint 에 대해 영역을 5개로 나누고, permutation and prefix matching 알고리즘을 반복한다면, 다음과 같이 fingerprint 영역을 나눌 수 있다.

long fp  = 0b01001010_10001110_10010100_10010010_11001110_10001010_1001
             ~~~~~~~~~~~~_____________~~~~~~~~~~~____________~~~~~~~~~~
                   a           b           c           d          e

각 영역은 10~11bit 의 크기를 갖게 되며, 5개의 permutation 을 만드는 경우, 공간복잡도는 다음과 같이 된다.

• fingerprint, document id, datetime, 3개의 입력값을 다룬다고 가정하자. 각각 8byte 으로 데이터를 표현할 수 있으며, 하나의 문서는 24byte 로 표현 가능하다. 사람이 읽기 편한 alphanumeric 문자만을 사용한다면, base64url encoding 등을 적용하는 경우, 약 40바이트 이내로 하나의 문서 정보를 표현할 수 있다.
• 10만개의 문서에 대해 5개 조합을 만드는 경우, 10만 x 5개 x 40byte의 메모리를 사용하여 permutation 을 표현할 수 있으며, 이 값을 계산하면 약 19MB 가 된다.

이때, prefix 크기의 최소비트는 10bit 이며, cardinality는 1024이다. prefix 가 일치하는 문서의 수는 평균 10만 / 1,048 = 약 97 이 된다.

Fingerprint 조합 테이블을 생성하고 정렬하는 비용은 O( N x log(N) ) 이기에 비용이 작고, 10만건의 문서에 대해 약 19MB 정도의 메모리를 일시적으로 사용하는 것으로 구현이 가능하다.

이 경우, 조합을 ( m + 2 ) x ( m + 1 ) / 2 개 생성하는 방식에 비해, 처음 조합을 생성하는 수는 m+1 개를 만들면 되기에 부담이 적고, Hadoop 을 이용하는 경우 reduce job 에서 20MB 정도의 메모리를 사용하여 중복검사를 수행하는 기능을 구현하면 되기에, 전체 시스템 구현에 있어서 부담이 적다. Hadoop map-reduce 기반으로 구현하는 경우, 결국 reduce job 의 hamming distance 계산 작업이 병목이 되며, CPU Bound 되는 작업이기에 물리 서버 내에서 CPU core 수 x 2~3배 정도의 job을 동시에 실행하는 것이 성능 최적점이 된다. 동시에 reduce job 이 50개 가량 실행되는 경우, 하나의 job 이 20MB 정도의 메모리를 더 사용하는 것은 메모리 자원 측면에서 부담되지 않는다.

Hadoop 기반 Map-Reduce 처리를 위한 입출력 설계

Permutation and prefix matching 구현을 Hadoop 기반 Map-Reduce 프로세스로 구현하면 전수 데이터에 대해 수십분 이내의 짧은 시간에 중복 검사를 수행하고 중복 쌍을 찾아낼 수 있다. 실제 구현을 해 보면, 일부 문서에 대해서는 중복 쌍이 다수 존재하는 특성이 있다. 예를 들어, 블로그 개설 축하 메시지가 수십만건 이상 시스템에서 생성되어 중복될 수 있다. 이러한 예외적인 데이터가 존재하는 경우, 데이터 분포가 골고루 분포하지 않아, 일부 Reduce 작업이 다른 경우보다 수배~수십배 오래 걸리는 현상이 발생한다. 이러한 경우를 고려하여, 다음와 같은 복합적인 데이터 처리 프로세스를 적용하는 것이 효과적이다.

작성 중

• 입력 데이터 예시

문서ID \t Fingerprint \t 문서작성시각 ```

• 출력 데이터

작성 중

• https://en.wikipedia.org/wiki/Triangle_inequality

레퍼런스

• Efficient Similarity Query Processing (http://www.cse.unsw.edu.au/~weiw/project/simjoin.html)
• Bilegsaikhan Naidan; Leonid Boytsov; Eric Nyberg, 2015, "Permutation Search Methods are Efficient, Yet Faster Search is Possible" (http://www.vldb.org/pvldb/vol8/p1618-naidan.pdf)
• Longest Common Subsequence - Lian’en Huang et al, 2008, "Achieving both High Precision and High Recall in Near-duplicate Detection" (http://sewm.pku.edu.cn/TianwangLiterature/2008/2008-CIKM-Achieving%20both%20high%20precision%20and%20high%20recall%20in%20near-duplicate%20detection.pdf)
• Moses S. Charikar, "Similarity Estimation Techniques from Rounding Algorithms", In proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 380-388, 2002 (http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf)
• Gurmeet Singh, Manku; Das Sarma, Anish (2007), "Detecting near-duplicates for web crawling", Proceedings of the 16th international conference on World Wide Web. ACM,. (http://www.wwwconference.org/www2007/papers/paper215.pdf)
• Detecting Near-Duplicates for Web Crawling (http://infolab.stanford.edu/~manku/papers/07www-duplicates.ppt‎)
• Tanguy Urvoy, Emmanuel Chauveau, Pascal Filoche, Thomas Lavergne, "Tracking Web spam with HTML style similarities", ACM Transactions on the Web (TWEB), v.2 n.1, pp.1-28, February 2008 (http://oniros.org/papers/urvoy2008acmtweb.pdf)
• Bingfeng Pi, Shunkai Fu, Weilei Wang , and Song Han, "SimHash-based Effective and Efficient Detecting of Near-Duplicate Short Messages", Proceedings of the Second Symposium International Computer Science and Computational Technology(ISCSCT ’09) Huangshan, P. R. China, pp.020-025, 26-28,Dec. 2009 (http://www.academypublisher.com/proc/iscsct09/papers/iscsct09p20.pdf)
• Chuan Xiao , Wei Wang , Xuemin Lin , Jeffrey Xu Yu , Guoren Wang, "Efficient similarity joins for near-duplicate detection", ACM Transactions on Database Systems (TODS), v.36 n.3, pp.1-41, August 2011 (http://www.cse.unsw.edu.au/~lxue/WWW08.pdf)
• Bayardo, R. J., Ma, Y., & Srikant, R. (2007), "Scaling up all pairs similarity search", In Proceedings of the 16th international conference on World Wide Web (WWW ’07), pp. 131–140, New York, NY. ACM. (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.2601&rep=rep1&type=pdf)