사본 탐지 및 삭제 방법 document_id A220517005288

본 발명은 대량의 컬렉션(collection)에서 유사한 데이터 객체들의 식별에 관한 것으로, 보다 상세히는, WWW(World Wide Web)와 같은, 문서의 매우 방대한 코퍼스들(corpora)에서의 유사한-사본의 식별에 관한 것이다. 문서의 대량의 컬렉션들은 통상적으로 서로 동일하거나 거의 동일한 문서들을 다수 포함한다. (예를 들면, 해슁(hashing) 기법을 이용하여) 2개의 디지털 방식으로 인코딩된 문서가 비트 단위로 동일한지 여부를 판정하는 것을 쉬운일이다. 그러나, 문서가 대략 동일한지 아니면 실질적으로 동일한지를 빠르게 식별하는 것이 보다 흥미로운 일이고, 많은 경우에서, 보다 유용한 일이다. WWW는 극도로 큰 문서 집합이다. 웹은 출현 이후 기하 급수적으로 성장하고 있어, 웹 인덱스는 현재 대략 50억의 웹 페이지를 포함하는데(정적인 웹은 200억 페이지로 추정된다.), 이 중 상당 부분이 사본 및 유사한-사본이다. 웹 크롤러(crawler) 및 검색 엔진과 같은 애플리케이션은 유사한-사본을 탐지하는 기능으로부터 이득을 얻는다. 예를 들면, 이러한 애플리케이션으로 하여금 대부분의 사본 및 유사한-사본들을 무시하게 하거나 질의의 결과를 필터링(filter)하여 유사한 문서들은 모두 그루핑(group)하는 것이 바람직할 수 있다. 대량의 컬렉션에서 유사한 객체를 찾아내는 것에 대한 문제를 해결하기 위하여 "싱글링(shingling)" 또는 "싱글프린팅(shingleprinting)" 기법이 개발되어 왔다. 이러한 기법들의 다양한 양태는 종래기술의 문헌 정보의 문헌들에 기술된다. 이들 특허 및 비특허 문헌들 각각은 본 명세서에 참조로서 포함된다. 이 싱글링 접근법에서, 문서는 그 문서를 충분히 표현하는 특징들의 집합으로 축약되어, 2개의 매우 유사한 문서는 매우 많은 특징들을 공유할 것이다. 텍스트-컨텐츠 문서의 경우, 중복된 연속된 w-단어 서브구(subphrase)(자신의 "w-싱글링")의 집합을 특징으로 추출하는 것이 유용하다고 판명되었으며, 여기서 w는 고정수이다. D1 및 D2를 문서라 하고, F1 및 F2를 이들 문서 각각의 특징 집합이라 하면, D1과 D2의 유사도를 특징 집합들의 쟈카드(Jaccard) 계수, (즉, 2개의 문서의 공통 특징의 수를 2개의 문서의 모든 특징의 총 개수로 나눈 값)로 정의한다. 이는 0과 1사이의 수로서 산출되는데, 본질적으로 동일한 2개의 문서의 유사도는 1에 가까운 수일 것인 한편, 유사하지 않는 문서의 쌍 대부분에 대한 유사도는 0에 가까운 수일 것이다. 대량의 컬렉션에서 실질적으로-동일한 항목을 탐지하는 싱글링 기법은 텍스트 코퍼스들에만 제한되지 않음을 유의한다. 싱글링은, 전형 특징을 집합을 추출할 수 있는, 녹음된 소리나 시각적 이미지와 같은, 임의 유형의 데이터 객체의 컬렉션에 적용될 수 있다. 각 문서로부터 추출된 특징의 개수는 잠재적으로 (문서 내의 단어의 수만큼이나) 매우 많을 수 있다. 문서 컬렉션 자체가 매우 크다(웹의 경우에서와 같이 수십억일 수도 있다)고 가정하면, 정확하게 유사도 값을 계산하고 한 쌍 단위의 비교를 수행하는 것은 컬렉션의 사이즈의 제곱이 되며 이는 엄청난 비용이 든다. 그러므로 유사도는 관리할 수 있는 크기 중 하나로 문제를 축소시키기 위하여 근사화된다. 근사화는 문서 유사도를 보존하는 방식으로 각 문서에 대한 특징 집합을 샘플링(sample)하는 것에 관련된다. 원칙적으로, 사용자는 특징들의 공간으로부터 모든 특징의 집합보다 큰 잘-정렬된 집합으로의 무작위 1대1 함수를 이용할 수 있다. 잘-정렬됨에 의하여, 무작위 함수 하의 특징 집합의 이미지의 가장 작은 엘리먼트가 존재한다. 그 가장 작은 엘리먼트의 이전 이미지를 선택된 샘플 특징으로서 취한다. 이는 모든 함수가 동일하게 예상되기 때문에 작용된다. 집합의 임의의 엘리먼트가 가장 작은 엘리먼트에 매핑(map)될 가능성이 있으며, 2개의 집합으로부터 선택될 때, 이 가장 작은 엘리먼트는 합집합으로부터 균일하게 선택된다. 전술된 방식은 실질적으로 구현가능하도록 변형시켜야 한다. 첫째, 균일하게 선택되기 위하여, 이미지 집합을 정수들의 유한 집합으로 만드는 것이 편리하다. 특징 집합이 제한되지 않는다면, 유한 집합에 대한 1대1 함수를 획득하는 것이 어렵다. 라빈(Rabin) 핑거프린트가 바람직한, 적절히-선택된 해쉬 함수를 이용하여, 고정수 비트를 가지는 수로 각 특징을 해슁하기 위하여, 집합 간의 충돌 가능성이 아주 작아지기에 충분한 큰 집합이 선택될 수 있다. 둘째, 진짜 무작위 함수를 선택하는 대신, 더 작고 쉽게 파라미터화될 수 있는 함수의 집합으로부터 함수가 선택되는 것이며, 선택한 함수는 정확한 확률에 근접한 것을 임의적으로 얻을 수 있을 만큼 충분히 양호하다고 증명되었다. 통상적으로, 라빈 핑거프린트를 동반한 선형 합동 치환(linear congruential permutation)의 조합이 사용되지만 올바르지 않다고 증명되었다. 이 기법은 이 되도록, 각 특징 집합 Fi로부터의 하나의 특징 fi 를 선택하는 메카니즘을 제공한다. 이러한 선택 메카니즘은 유사성에 대한 편향되지 않은 포인트 추정기를 제공한다. 선택기의 임의 수 r이 선택된다. 각 문서 Di에 대하여, Di에 대해 각 선택기를 한번 이용하여, 가 계산된다. 일부 사건 처리의 댓가로서, 이 선택은 각 항에 대한 데이터 저장소를 일정하게 줄여주고 집합과 벡터 내의 일치하는 항과의 비교를 줄여준다. 복수의 독립적인 선택 메카니즘을 실행시킴으로써, 2개의 문서의 유사도의 백분율 추정치를 선택물들의 벡터에서의 일치들을 카운팅(count)함으로써 구한다. 라면, D와 E에 대한 벡터들의 각 항은 확률 p와 일치한다. 한 행에서 k항들이 일치할 확률은 이다. 벡터는 k개의 항의 중복되지 않는 실행을 해쉬 값 내의 충돌 확률을 무시해도 될 정도로 충분히 큰 공간으로부터 선택된 단일 정수들로 해슁함으로써 압축될 수 있는 한편, 저장소 요구량은 k분의 1로 줄어든다. 길이가 k인 s 그룹("수퍼샘플(supersample)")이 존재한다면, 하나 이상의 수퍼샘플이 일치할 확률은 이고 2개 이상의 수퍼샘플이 일치할 확률은 이다. 알타 비스타 검색 엔진에 관련된 종래 연구에서, 각 문서의 텍스트의 정규화된 버전의 6개의-싱글링이 특징 집합으로 추출되었다. 특징들은 64비트 정수형으로 표현되었다. 선형 합동 치환 기법이 각 64-비트 정수형에 적용되어, 새로운 집합의 64-비트 정수형을 생성하였고 이 새로운 집합의 가장 작은 값의 이전-이미지가 샘플로 선택되었다. 84개의 샘플들을 취하여, 6개의 수퍼샘플로 나누어 각각 14개의 샘플로 조합시켰다. 그러므로, 파라미터 k와 s에 대하여, k=14와 s=6 값이 이용되었다. 유사한-사본 문서에 대한 소정의 유사도 임계값이 .95였기 때문에 이들 파라미터가 선택되었다. 2개의 문서 간에 14개의 샘플이 일치할 확률은 문서의 유사도를 14제곱한 것과 같아서, 문서가 유사한-사본이라면, 이 확률은 .9514일 것이며, 이값은 대략 1/2이다. 그러므로, 14개의 샘플의 6개의 그룹에서, 6개 중 적어도 2개의 그룹이 일치할 가능성이 있으며, 2개 보다 작은 그룹이 일치할 가능성은 희박하다. 그러므로, 문서가 아마도 유사한-사본인 것을 판정하기 위해서는, 6개의 수퍼샘플 중 2개가 일치되어야 했었다. 종래 연구는 소정의 임계값에 따라 유사한-사본 아이템을 식별하는 데 실제로 효율적이었다. 종래 연구에서 일치 프로세스는 작은 수의 아이템 당 적은 수의 해쉬 테이블 룩업(lookup)으로 간소화될 수 있음을 발견하였다. 한 그룹 내의 k개의 샘플들은 64-비트 정수형으로 압축된다. 이하 설명될 바와 같이, 각 수퍼샘플은 유사하지 않은 문서를 유사하다고 판정할 사태를 방지하기 위해 64-비트 정밀도로 레코딩된다. 그 다음 s 개의 64비트 정수형의 가능한 쌍 모두는 해쉬 테이블에 삽입된다. 예를 들어, s=6이라면, 적어도 2개가 일치하는 아이템들을 찾아내는 것은 오직 룩업만이 필요하기 때문에, 15개의 해쉬 테이블이 이용된다. 종래 연구는 오프라인 프로세스의 이용에 중점을 두어서, 주 메모리를 경제성 있도록 하는 것은 주요 관심사가 아니었다. 예를 들면, 이전 문단에서 기술한 해슁 최적화는, 오프라인 프로세싱에 매우 적합하다. 그러나, 이 기법의 문서-당 저장소 요구량은 검색 엔진이 모든 문서에 대하여 "빠르게" 이 기법을 수행하기에는 적합하지 않다. 50억 문서 컬렉션에서, 이 기법은 6개의 값을 저장하기 위해 240 기가바이트의 메모리 풋프린트(footprint)가 필요하며, 및 해쉬-테이블을 저장하기 위해 520 기가바이트가 더 필요할 것이다. 이는 검색은 실행하기에 부피가 크고 인덱스 구축에서도 제약 조건이 따른다. 예를 들어, 검색 엔진은 전체 문서 컬렉션에 대해 전처리 과정을 수행하지 않을 수 있으며 자신이 인덱스를 증분적으로 작성할 수 있다. 온라인 프로세스에서는, 검색 엔진이 보고될 질의 결과가 유사한-사본이라고 판정하여 이 보고를 유사한-사본의 클러스터 마다 하나의 문서로 축약할 수 있는데 그 문서를 선택하기 위해, 대부분의 응답 문서가 동적으로 선택되도록 할 수 있는 랭킹(ranking) 함수를 이용하는 것이 바람직할 수 있다.