R의 textreuse packge가 LSH 버킷을 원래 minhashe보다 크게 만드는 이유는 무엇입니까?
내가 이해하는 한 LSH 방법의 주요 기능 중 하나는 기본 해시 (종종 minhashes)를 넘어서는 데이터 감소입니다. 저는 textreuseR 에서 패키지를 사용하고 있으며 생성되는 데이터의 크기에 놀랐습니다. textreuse동료 검토를 거친 ROpenSci 패키지이므로 올바르게 작동한다고 가정하지만 내 질문은 지속됩니다.
내 minhash 및 LSH 함수에 대해 각각 256 순열과 64 밴드를 사용한다고 가정 해 보겠습니다. 상대적 확실성 (~ 98 %) 유사성을 50 % 까지 탐지하는 데 자주 사용되는 현실적인 값입니다 .
TextReuseTextDocument(256 perms)를 사용하여 임의의 텍스트 파일을 해시 하고에 할당하면 다음 trtd과 같이됩니다.
object.size(trtd$minhashes)
> 1072 bytes
이제이 객체 (64 개 밴드)에 대한 LSH 버킷을 만들고에 할당 해 보겠습니다 l.
object.size(l$buckets)
> 6704 bytes
따라서 LSH 버킷에 보유 된 해시는 원래 minhashe보다 6 배 더 큽니다. textreuse md5 다이제스트 를 사용하여 버킷 해시를 만들기 때문에 이런 일이 발생한다는 것을 이해 합니다.
그러나 이것은 너무 낭비 적이거나 과도하지 않으며 개선 할 수 없습니까? 우리의 데이터 감소 기술이이 정도까지 팽창하는 것이 정상입니까? 그리고 원래 해시 (perms = 256 및 bands = 256과 유사)를 기반으로 문서를 일치시킨 다음 임계 값을 사용하여 오 탐지를 제거하는 것이 더 효과적이지 않습니까?
Mining of Massive Datasets 와 같은 일반적인 텍스트를 검토 했지만이 특정 구현에 대해서는이 질문이 남아 있습니다. 또한 질문은 호기심 때문일뿐만 아니라 필요하지 않은 것입니다. 수백만 또는 수십억 개의 해시가있는 경우 이러한 차이가 중요해집니다.
답변
여기에 패키지 작성자. 예, 필요한 것보다 더 많은 해시 / 밴드를 사용하는 것은 낭비입니다. (여기서는 킬로바이트에 대해 이야기하고 있으며 원본 문서보다 훨씬 더 작을 수 있습니다.)
문제는 무엇이 필요합니까? 일치에 가까운 (즉, Jaccard 점수가 1.0에 가까운) 일치하는 항목 만 찾아야하는 경우 특별히 민감한 검색이 필요하지 않습니다. 그러나 부분 겹침 (예 : 0에 가까운 Jaccard 점수) 만 공유하는 잠재적 일치 항목을 안정적으로 감지해야하는 경우 더 많은 해시 / 밴드가 필요합니다.
MMD를 읽었으므로 여기에서 방정식을 찾을 수 있습니다. 그러나 패키지의 두 가지 기능이 있습니다 여기에 문서화 당신이 필요로 얼마나 많은 해시 / 밴드 계산 도움이 될 수 있습니다. lsh_threshold()감지 될 임계 값 Jaccard 점수를 계산합니다. 동안 lsh_probability()당신을 말할 것이다 그것은 주어진 인 Jaccard 점수가 문서의 한 쌍의 검출 될 것입니다 가능성을. 검색 문제에 가장 적합한 해시 / 밴드 수를 얻을 때까지이 두 가지 기능을 사용해보십시오.