MINHASH_LSH

효율적인 중복 제거와 유사도 검색은 대규모 머신 러닝 데이터 세트, 특히 대규모 언어 모델(LLM)을 위한 학습 코퍼라 정리와 같은 작업에서 매우 중요합니다. 수백만 또는 수십억 개의 문서를 다룰 때, 기존의 정확한 일치 검색은 너무 느리고 비용이 많이 듭니다.

Milvus의 MINHASH_LSH 인덱스는 두 가지 강력한 기술을 결합하여 빠르고 확장 가능하며 정확한 대략적인 중복 제거를 가능하게 합니다:

• MinHash: 문서 유사성을 추정하기 위해 압축 서명(또는 "지문")을 빠르게 생성합니다.

• LSH(지역 민감 해싱): MinHash 서명을 기반으로 유사한 문서 그룹을 빠르게 찾습니다.

이 가이드에서는 Milvus에서 MINHASH_LSH를 사용하기 위한 개념, 전제 조건, 설정 및 모범 사례를 안내합니다.

개요

Jaccard 유사성

Jaccard 유사성은 공식적으로 다음과 같이 정의되는 두 세트 A와 B 사이의 중첩을 측정합니다:

$$J(A, B) = \frac{|A \cap B|}{|A \cup B|}$$

여기서 그 값은 0(완전히 일치하지 않음)에서 1(동일함)까지의 범위입니다.

그러나 대규모 데이터 세트의 모든 문서 쌍 간에 Jaccard 유사도를 정확히 계산하려면 n이 클 경우 시간과 메모리에 O(n² )의 계산 비용이 듭니다. 따라서 LLM 학습 코퍼스 정리나 웹 규모의 문서 분석과 같은 사용 사례에는 적용이 불가능합니다.

최소 해시 서명: 대략적인 Jaccard 유사성

MinHash는 Jaccard 유사성을 추정하는 효율적인 방법을 제공하는 확률적 기법입니다. 각 집합을 간결한 서명 벡터로 변환하여 집합 유사도를 효율적으로 추정할 수 있는 충분한 정보를 보존하는 방식으로 작동합니다.

핵심 아이디어:

두 세트가 더 유사할수록 MinHash 서명이 같은 위치에서 일치할 가능성이 높아집니다. 이 속성을 통해 MinHash는 세트 간의 Jaccard 유사성을 근사화할 수 있습니다.

이 속성을 사용하면 전체 집합을 직접 비교할 필요 없이 MinHash가 집합 간의 Jaccard 유사성을 근사화할 수 있습니다.

MinHash 프로세스에는 다음이 포함됩니다:

1. 슁글링: 문서를 겹치는 토큰 시퀀스 집합(대상포진)으로 변환합니다.

2. 해싱: 각 싱글에 여러 개의 독립적인 해시 함수를 적용합니다.

3. 최소 선택: 각 해시 함수에 대해 모든 싱글에 걸쳐 최소 해시 값을 기록합니다.

아래 그림에서 전체 프로세스를 확인할 수 있습니다:

민해시 워크플로

MinHash용 LSH

MinHash 서명은 문서 간의 정확한 Jaccard 유사성을 계산하는 데 드는 비용을 크게 줄여주지만, 모든 서명 벡터 쌍을 철저하게 비교하는 것은 여전히 규모에 따라 비효율적입니다.

이 문제를 해결하기 위해 LSH가 사용됩니다. LSH는 모든 쌍을 직접 비교할 필요 없이 유사한 항목이 높은 확률로 동일한 '버킷'에 해시되도록 함으로써 빠른 대략적인 유사성 검색을 가능하게 합니다.

프로세스에는 다음이 포함됩니다:

1. 서명 세분화:

   n차원 MinHash 서명은 b개의 밴드로 나뉩니다. 각 밴드에는 r 개의 연속 해시 값이 포함되므로 총 서명 길이는 n = b × r을 만족합니다.

   예를 들어 128차원 MinHash 서명(n = 128)을 32개의 밴드(b = 32)로 나눈다면 각 밴드에는 4개의 해시 값이 포함됩니다(r = 4).

2. 밴드 수준 해싱:

   세분화 후 각 밴드는 표준 해시 함수를 사용하여 독립적으로 처리되어 버킷에 할당됩니다. 두 서명이 한 밴드 내에서 동일한 해시 값을 생성하는 경우(즉, 동일한 버킷에 속하는 경우) 잠재적 일치로 간주됩니다.

3. 후보 선택:

   적어도 하나의 밴드에서 충돌하는 쌍이 유사성 후보로 선택됩니다.

128차원 MinHash 서명이 있는 세 개의 문서를 예로 들어 보겠습니다:

LSH 워크플로 1

먼저, LSH는 128차원 서명을 각각 4개의 연속된 값으로 구성된 32개의 밴드로 나눕니다:

Lsh 워크플로우 2

그런 다음 해시 함수를 사용해 각 밴드를 서로 다른 버킷으로 해시합니다. 버킷을 공유하는 문서 쌍이 유사성 후보로 선택됩니다. 아래 예에서 문서 A와 문서 B는 해시 결과가 밴드 0에서 충돌하므로 유사도 후보로 선택됩니다:

Lsh 워크플로 3

MHJACCARD: MinHash 서명 비교

MinHash 서명은 고정 길이 바이너리 벡터를 사용하여 세트 간의 Jaccard 유사성을 근사화합니다. 그러나 이러한 서명은 원본 집합을 보존하지 않기 때문에 JACCARD, L2, COSINE 와 같은 표준 메트릭을 직접 적용하여 비교할 수 없습니다.

이 문제를 해결하기 위해 Milvus는 MinHash 서명 비교를 위해 특별히 설계된 MHJACCARD 이라는 특수 메트릭 유형을 도입했습니다.

Milvus에서 MinHash를 사용할 때:

• 벡터 필드의 유형은 다음과 같아야 합니다. BINARY_VECTOR

• index_type 은 MINHASH_LSH (또는 BIN_FLAT)이어야 합니다.

• metric_type 은 다음과 같이 설정되어야 합니다. MHJACCARD

다른 메트릭을 사용하면 유효하지 않거나 잘못된 결과가 산출됩니다.

이 메트릭 유형에 대한 자세한 내용은 MHJACCARD를 참조하세요.

중복 제거 워크플로

MinHash LSH로 구동되는 중복 제거 프로세스를 통해 Milvus는 컬렉션에 삽입하기 전에 중복에 가까운 텍스트 또는 구조화된 레코드를 효율적으로 식별하고 필터링할 수 있습니다.

1. 청크 및 전처리: 들어오는 텍스트 데이터나 구조화된 데이터(예: 레코드, 필드)를 청크로 분할하고, 텍스트를 정규화하고(소문자, 구두점 제거), 필요에 따라 중지어를 제거합니다.

2. 기능 구성: MinHash에 사용되는 토큰 집합을 구축합니다(예: 텍스트의 대상포진, 구조화된 데이터의 연결된 필드 토큰).

3. MinHash 서명 생성: 각 청크 또는 레코드에 대한 MinHash 서명을 계산합니다.

4. 바이너리 벡터 변환: 서명을 Milvus와 호환되는 바이너리 벡터로 변환합니다.

5. 삽입하기 전에 검색: MinHash LSH 인덱스를 사용해 대상 컬렉션에서 들어오는 항목의 거의 중복된 항목을 검색합니다.

6. 삽입 및 저장: 컬렉션에 고유한 항목만 삽입합니다. 이렇게 하면 향후 중복 제거 검사를 위해 검색할 수 있게 됩니다.

전제 조건

Milvus에서 MinHash LSH를 사용하기 전에 먼저 MinHash 서명을 생성해야 합니다. 이 간결한 바이너리 서명은 세트 간의 Jaccard 유사성을 대략적으로 나타내며 Milvus의 MHJACCARD 기반 검색에 필요합니다.

MinHash 서명을 생성하는 방법 선택하기

워크로드에 따라 선택할 수 있습니다:

• Python의 datasketch 사용(프로토타이핑에 권장)

• 대규모 데이터 세트에 분산 도구(예: Spark, Ray) 사용

• 성능 튜닝이 중요한 경우 사용자 정의 로직(NumPy, C++ 등)을 구현합니다.

이 가이드에서는 단순성과 Milvus 입력 형식과의 호환성을 위해 datasketch 을 사용합니다.

필요한 라이브러리 설치

이 예제에 필요한 패키지를 설치합니다:

pip install pymilvus datasketch numpy

MinHash 서명 생성

각 해시 값이 64비트 정수로 표시되는 256차원 MinHash 서명을 생성하겠습니다. 이는 MINHASH_LSH 에 대해 예상되는 벡터 형식과 일치합니다.

from datasketch import MinHash
import numpy as np

MINHASH_DIM = 256
HASH_BIT_WIDTH = 64

def generate_minhash_signature(text, num_perm=MINHASH_DIM) -> bytes:
    m = MinHash(num_perm=num_perm)
    for token in text.lower().split():
        m.update(token.encode("utf8"))
    return m.hashvalues.astype('>u8').tobytes()  # Returns 2048 bytes

각 서명은 256 × 64비트 = 2048바이트입니다. 이 바이트 문자열은 BINARY_VECTOR 필드에 직접 삽입할 수 있습니다. Milvus에서 사용되는 바이너리 벡터에 대한 자세한 내용은 바이너리 벡터를 참조하세요.

(선택 사항) 원시 토큰 세트 준비(정제된 검색을 위해)

기본적으로 Milvus는 MinHash 서명과 LSH 인덱스만 사용하여 대략적인 이웃을 찾습니다. 이 방법은 빠르지만 오탐을 반환하거나 가까운 일치 항목을 놓칠 수 있습니다.

정확한 Jaccard 유사성을 원하는 경우, Milvus는 원본 토큰 세트를 사용하는 정교한 검색을 지원합니다. 사용하려면 다음과 같이 하세요:

• 토큰 세트를 별도의 VARCHAR 필드로 저장합니다.

• 인덱스 파라미터를 구축할 때 "with_raw_data": True 설정

• 그리고 유사도 검색을 수행할 때 "mh_search_with_jaccard": True 을 활성화합니다.

토큰 세트 추출 예시:

def extract_token_set(text: str) -> str:
    tokens = set(text.lower().split())
    return " ".join(tokens)

MinHash LSH 사용

MinHash 벡터와 원본 토큰 세트가 준비되면, MINHASH_LSH 을 사용하여 Milvus를 사용하여 저장, 색인 및 검색할 수 있습니다.

클러스터에 연결

from pymilvus import MilvusClient

client = MilvusClient(uri="http://localhost:19530")  # Update if your URI is different

// java

// nodejs

// go

# restful

수집 스키마 정의

스키마를 정의합니다:

• 기본 키

• MinHash 서명을 위한 BINARY_VECTOR 필드

• 원본 토큰 세트에 대한 VARCHAR 필드(정밀 검색이 활성화된 경우)

• 선택 사항, 원본 텍스트를 위한 document 필드

from pymilvus import DataType

VECTOR_DIM = MINHASH_DIM * HASH_BIT_WIDTH  # 256 × 64 = 8192 bits

schema = client.create_schema(auto_id=False, enable_dynamic_field=False)
schema.add_field("doc_id", DataType.INT64, is_primary=True)
schema.add_field("minhash_signature", DataType.BINARY_VECTOR, dim=VECTOR_DIM)
schema.add_field("token_set", DataType.VARCHAR, max_length=1000)  # required for refinement
schema.add_field("document", DataType.VARCHAR, max_length=1000)

// java

// nodejs

// go

# restful

인덱스 매개변수 빌드 및 컬렉션 생성

Jaccard 세분화가 활성화된 MINHASH_LSH 인덱스를 빌드합니다:

index_params = client.prepare_index_params()
index_params.add_index(
    field_name="minhash_signature",
    index_type="MINHASH_LSH",
    metric_type="MHJACCARD",
    params={
        "mh_element_bit_width": HASH_BIT_WIDTH,  # Must match signature bit width
        "mh_lsh_band": 16,                       # Band count (128/16 = 8 hashes per band)
        "with_raw_data": True                    # Required for Jaccard refinement
    }
)

client.create_collection("minhash_demo", schema=schema, index_params=index_params)

// java

// nodejs

// go

# restful

인덱스 작성 매개변수에 대한 자세한 내용은 인덱스 작성 매개변수를 참조하세요.

데이터 삽입

각 문서에 대해 준비합니다:

• 이진 MinHash 서명

• 직렬화된 토큰 세트 문자열

• (선택 사항) 원본 텍스트

documents = [
    "machine learning algorithms process data automatically",
    "deep learning uses neural networks to model patterns"
]

insert_data = []
for i, doc in enumerate(documents):
    sig = generate_minhash_signature(doc)
    token_str = extract_token_set(doc)
    insert_data.append({
        "doc_id": i,
        "minhash_signature": sig,
        "token_set": token_str,
        "document": doc
    })

client.insert("minhash_demo", insert_data)
client.flush("minhash_demo")

// java

// nodejs

// go

# restful

유사도 검색 수행

Milvus는 MinHash LSH를 사용하여 두 가지 유사성 검색 모드를 지원합니다:

• 근사 검색 - MinHash 서명과 LSH만을 사용하여 빠르고 확률적인 결과를 제공합니다.

• 정밀 검색 - 정확도 향상을 위해 원본 토큰 세트를 사용하여 Jaccard 유사성을 다시 계산합니다.

5.1 쿼리 준비

유사도 검색을 수행하려면 쿼리 문서에 대한 MinHash 서명을 생성합니다. 이 서명은 데이터 삽입 시 사용된 것과 동일한 차원 및 인코딩 형식과 일치해야 합니다.

query_text = "neural networks model patterns in data"
query_sig = generate_minhash_signature(query_text)

// java

// nodejs

// go

# restful

5.2 대략적인 검색(LSH 전용)

이 방법은 빠르고 확장 가능하지만 일치하는 항목을 놓치거나 오탐을 포함할 수 있습니다:

search_params={
    "metric_type": "MHJACCARD", 
    "params": {}
}

approx_results = client.search(
    collection_name="minhash_demo",
    data=[query_sig],
    anns_field="minhash_signature",
    search_params=search_params,
    limit=3,
    output_fields=["doc_id", "document"],
    consistency_level="Strong"
)

for i, hit in enumerate(approx_results[0]):
    sim = 1 - hit['distance']
    print(f"{i+1}. Similarity: {sim:.3f} | {hit['entity']['document']}")

// java

// nodejs

// go

# restful

5.3 정밀 검색(정확도를 위해 권장):

Milvus에 저장된 원본 토큰 세트를 사용하여 정확한 Jaccard 비교를 가능하게 합니다. 약간 느리지만 품질에 민감한 작업에 권장됩니다:

search_params = {
    "metric_type": "MHJACCARD",
    "params": {
        "mh_search_with_jaccard": True,  # Enable real Jaccard computation
        "refine_k": 5                    # Refine top 5 candidates
    }
}

refined_results = client.search(
    collection_name="minhash_demo",
    data=[query_sig],
    anns_field="minhash_signature",
    search_params=search_params,
    limit=3,
    output_fields=["doc_id", "document"],
    consistency_level="Strong"
)

for i, hit in enumerate(refined_results[0]):
    sim = 1 - hit['distance']
    print(f"{i+1}. Similarity: {sim:.3f} | {hit['entity']['document']}")

// java

// nodejs

// go

# restful

인덱스 매개변수

이 섹션에서는 인덱스를 구축하고 인덱스에서 검색을 수행하는 데 사용되는 매개변수에 대한 개요를 제공합니다.

인덱스 구축 매개변수

다음 표에는 인덱스 작성 시 params 에서 구성할 수 있는 매개변수가 나열되어 있습니다.

파라미터	설명	값 범위	조정 제안
mh_element_bit_width	MinHash 서명에서 각 해시 값의 비트 폭입니다. 8로 나눌 수 있어야 합니다.	8, 16, 32, 64	균형 잡힌 성능과 정확도를 위해 32 을 사용합니다. 더 큰 데이터 세트에서 더 높은 정밀도를 원하시면 64 을 사용하세요. 허용 가능한 정확도 손실로 메모리를 절약하려면 16 을 사용합니다.
mh_lsh_band	LSH에 대한 최소 해시 서명을 나눌 밴드 수입니다. 리콜-성능 트레이드오프를 제어합니다.	[1, 서명_길이]	128딤 서명의 경우: 32개 밴드(4개 값/밴드)로 시작합니다. 리콜률을 높이려면 64로 늘리고, 성능을 높이려면 16으로 줄입니다. 서명 길이를 균등하게 나누어야 합니다.
mh_lsh_code_in_mem	LSH 해시 코드를 익명 메모리에 저장할지 (true) 또는 메모리 매핑을 사용할지 (false).	참, 거짓	메모리 사용량을 줄이려면 대규모 데이터 세트(100만 세트 이상)의 경우 false 을 사용합니다. 최대 검색 속도가 필요한 소규모 데이터 세트의 경우 true 을 사용합니다.
with_raw_data	세분화를 위해 LSH 코드와 함께 원본 MinHash 서명을 저장할지 여부.	true, false	높은 정밀도가 필요하고 저장 비용이 허용되는 경우 true 을 사용합니다. 약간의 정확도 감소와 함께 스토리지 오버헤드를 최소화하려면 false 을 사용합니다.
mh_lsh_bloom_false_positive_prob	LSH 버킷 최적화에 사용되는 블룸 필터의 오탐 확률입니다.	[0.001, 0.1]	균형 잡힌 메모리 사용량과 정확도를 위해 0.01 을 사용하세요. 값이 낮을수록 (0.001) 오탐 확률은 감소하지만 메모리가 증가합니다. 값이 높을수록(0.05) 메모리는 절약되지만 정확도가 떨어질 수 있습니다.

인덱스별 검색 매개변수

다음 표에는 색인에서 검색할 때 search_params.params 에서 구성할 수 있는 매개변수가 나와 있습니다.

파라미터	설명	값 범위	조정 제안
mh_search_with_jaccard	세분화를 위해 후보 결과에 대해 정확한 Jaccard 유사도 계산을 수행할지 여부입니다.	참, 거짓	높은 정밀도(예: 중복 제거)가 필요한 애플리케이션에는 true 을 사용합니다. 약간의 정확도 손실이 허용되는 경우 false 을 사용하여 더 빠른 근사치 검색을 수행하세요.
refine_k	Jaccard 정제 전에 검색할 후보자 수입니다. mh_search_with_jaccard 이 true 일 때만 유효합니다.	[top_k, *top_k * 10*]	리콜과 성능의 균형을 맞추기 위해 원하는 top_k의 2~5배로 설정합니다. 값이 클수록 리콜 성능이 향상되지만 계산 비용이 증가합니다.
mh_lsh_batch_search	여러 개의 동시 쿼리에 대해 일괄 최적화를 활성화할지 여부입니다.	true, false	처리량 향상을 위해 여러 쿼리를 동시에 검색할 때는 true 을 사용합니다. 단일 쿼리 시나리오에서는 false 을 사용하여 메모리 오버헤드를 줄입니다.