MinHash-based Locality Sensitive Hashing (LSH)는 대용량 데이터 집합에서 유사한 항목을 효율적으로 찾기 위한 기술이다. 이는 데이터 마이닝, 정보 검색, 유전체학 등 다양한 분야에서 활용된다.
MinHash는 집합을 대표하는 짧은 signature를 생성하는 기법이다. 이 때, 집합의 특성을 최대한 유지하면서 작은 크기의 signature를 생성하기 위해 무작위 함수를 사용한다. MinHash signature는 원래 집합의 요소들 간의 관계를 추정하는 데 사용된다. 예를 들어, 두 개의 집합이 유사한지를 판별하려면 MinHash signature를 비교하여 일치하는 signature의 비율을 측정할 수 있다.
LSH는 MinHash signature를 사용하여 유사한 항목을 찾는 데 사용되는 인덱싱 메커니즘이다. LSH는 signature 공간을 여러 개의 버킷으로 분할하고, 동일한 버킷에 속한 항목들끼리 유사한 것으로 간주한다. 이를 통해 유사한 항목들을 효율적으로 검색할 수 있다. MinHash LSH는 대량의 데이터에 대해 빠른 유사도 검색을 가능하게 해주며, 이를 활용하여 유사한 문서, 이미지, 음악 등을 찾을 수 있다.
MinHash-based LSH는 데이터의 차원이 높아지면서 발생하는 차원의 저주(curse of dimensionality) 문제에도 상대적으로 강인한다. 저주의 차원 문제란, 고차원 공간에서 데이터 간의 거리나 유사도를 정확하게 계산하기 어려워지는 현상을 말한다. MinHash는 집합의 특성을 보존하는 signature를 생성하기 때문에 이러한 문제를 완화시킬 수 있다.
따라서 MinHash-based LSH는 대규모 데이터 집합에서 유사한 항목을 효율적으로 검색하는 데 사용되는 강력한 기술이다.
