MINHASH_LSH

A deduplicação eficiente e a pesquisa por semelhança são fundamentais para conjuntos de dados de aprendizagem automática em grande escala, especialmente para tarefas como a limpeza de corpora de treino para Modelos de Linguagem de Grande Dimensão (LLMs). Quando se lida com milhões ou milhares de milhões de documentos, a correspondência exacta tradicional torna-se demasiado lenta e dispendiosa.

O índice MINHASH_LSH do Milvus permite uma deduplicação aproximada rápida, escalável e precisa, combinando duas técnicas poderosas:

• MinHash: Gera rapidamente assinaturas compactas (ou "impressões digitais") para estimar a similaridade de documentos.

• Locality-Sensitive Hashing (LSH): Encontra rapidamente grupos de documentos semelhantes com base nas suas assinaturas MinHash.

Este guia o orienta através dos conceitos, pré-requisitos, configuração e melhores práticas para usar MINHASH_LSH no Milvus.

Visão geral

Similaridade Jaccard

A similaridade de Jaccard mede a sobreposição entre dois conjuntos A e B, formalmente definida como:

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

Onde seu valor varia de 0 (completamente disjuntos) a 1 (idênticos).

No entanto, calcular a semelhança de Jaccard exatamente entre todos os pares de documentos em conjuntos de dados de grande escala é computacionalmente dispendioso - O(n²) em tempo e memória quando n é grande. Isto torna-o inviável para casos de utilização como a limpeza de corpus de treino LLM ou a análise de documentos à escala da Web.

Assinaturas MinHash: Similaridade Jaccard aproximada

O MinHash é uma técnica probabilística que oferece uma forma eficiente de estimar a semelhança de Jaccard. Funciona transformando cada conjunto num vetor de assinatura compacto, preservando informação suficiente para aproximar a semelhança de conjuntos de forma eficiente.

A ideia central:

Quanto mais semelhantes forem os dois conjuntos, maior será a probabilidade de as suas assinaturas MinHash coincidirem nas mesmas posições. Essa propriedade permite que o MinHash aproxime a similaridade Jaccard entre conjuntos.

Essa propriedade permite que o MinHash aproxime a similaridade Jac card entre conjuntos sem precisar comparar os conjuntos completos diretamente.

O processo do MinHash envolve:

1. Shingling: Converter documentos em conjuntos de sequências de tokens sobrepostos (shingles)

2. Hashing: Aplicar várias funções hash independentes a cada shingle

3. Seleção do mínimo: Para cada função de hash, registar o valor de hash mínimo em todos os shingles

Pode ver todo o processo ilustrado abaixo:

Fluxo de trabalho do Minhash

LSH para MinHash

Embora as assinaturas MinHash reduzam significativamente o custo do cálculo da semelhança Jaccard exacta entre documentos, a comparação exaustiva de cada par de vectores de assinatura continua a ser ineficiente à escala.

Para resolver este problema, é utilizado o LSH. O LSH permite uma pesquisa rápida e aproximada de semelhanças, assegurando que os itens semelhantes são colocados em hash no mesmo "balde" com elevada probabilidade - evitando a necessidade de comparar cada par diretamente.

O processo envolve:

1. Segmentação da assinatura:

   Uma assinatura MinHash n-dimensional é dividida em b bandas. Cada banda contém r valores de hash consecutivos, de modo que o comprimento total da assinatura satisfaz: n = b × r.

   Por exemplo, se você tiver uma assinatura MinHash de 128 dimensões(n = 128) e dividi-la em 32 bandas(b = 32), então cada banda contém 4 valores de hash(r = 4).

2. Hashing em nível de banda:

   Após a segmentação, cada banda é processada de forma independente utilizando uma função de hash padrão para a atribuir a um intervalo. Se duas assinaturas produzirem o mesmo valor de hash dentro de uma banda - ou seja, caírem no mesmo intervalo - elas são consideradas correspondências potenciais.

3. Seleção de candidatos:

   Os pares que colidem em pelo menos uma banda são selecionados como candidatos à semelhança.

Considere três documentos com assinaturas MinHash de 128 dimensões:

Fluxo de trabalho 1 do Lsh

Primeiro, o LSH divide a assinatura de 128 dimensões em 32 bandas de 4 valores consecutivos cada:

Fluxo de Trabalho 2 do Lsh

De seguida, cada banda é transformada em diferentes intervalos usando uma função de hash. Os pares de documentos que partilham os intervalos são selecionados como candidatos à semelhança. No exemplo abaixo, o Documento A e o Documento B são selecionados como candidatos à semelhança, uma vez que os seus resultados de hash colidem na Banda 0:

Fluxo de trabalho Lsh 3

MHJACCARD: Comparação de assinaturas MinHash

As assinaturas MinHash aproximam a similaridade Jaccard entre conjuntos usando vetores binários de comprimento fixo. No entanto, como essas assinaturas não preservam os conjuntos originais, métricas padrão como JACCARD, L2, ou COSINE não podem ser aplicadas diretamente para compará-las.

Para resolver isso, Milvus introduz um tipo de métrica especializada chamada MHJACCARD, projetada especificamente para comparar assinaturas MinHash.

Ao usar MinHash em Milvus:

• O campo vetorial tem de ser do tipo BINARY_VECTOR

• O index_type tem de ser MINHASH_LSH (ou BIN_FLAT)

• O metric_type deve ser definido como MHJACCARD

A utilização de outras métricas será inválida ou produzirá resultados incorrectos.

Para obter mais informações sobre este tipo de métrica, consulte MHJACCARD.

Fluxo de trabalho de desduplicação

O processo de deduplicação desenvolvido pelo MinHash LSH permite ao Milvus identificar e filtrar eficazmente texto quase duplicado ou registos estruturados antes de os inserir na coleção.

1. Separação e pré-processamento: Dividir os dados de texto de entrada ou os dados estruturados (por exemplo, registos, campos) em pedaços; normalizar o texto (minúsculas, remoção de pontuação) e remover palavras de paragem conforme necessário.

2. Construção de caraterísticas: Construir o conjunto de tokens usado para o MinHash (por exemplo, shingles de texto; tokens de campo concatenados para dados estruturados).

3. Geração da assinatura MinHash: Calcular assinaturas MinHash para cada pedaço ou registo.

4. Conversão de vetor binário: Converte a assinatura em um vetor binário compatível com o Milvus.

5. Pesquisa antes de inserir: Utilizar o índice LSH do MinHash para procurar na coleção de destino por quase-duplicados do item de entrada.

6. Inserir e armazenar: Insere apenas itens únicos na coleção. Eles se tornam pesquisáveis para futuras verificações de deduções.

Pré-requisitos

Antes de usar o MinHash LSH no Milvus, é preciso primeiro gerar assinaturas MinHash. Essas assinaturas binárias compactas aproximam a similaridade Jaccard entre conjuntos e são necessárias para a pesquisa baseada em MHJACCARD no Milvus.

Escolha um método para gerar assinaturas MinHash

Dependendo da sua carga de trabalho, pode escolher:

• Usar o Python's datasketch do Python para simplicidade (recomendado para prototipagem)

• Usar ferramentas distribuídas (por exemplo, Spark, Ray) para conjuntos de dados em grande escala

• Implementar lógica personalizada (NumPy, C++, etc.) se o ajuste de desempenho for crítico

Neste guia, usamos datasketch por simplicidade e compatibilidade com o formato de entrada Milvus.

Instalar as bibliotecas necessárias

Instale os pacotes necessários para este exemplo:

pip install pymilvus datasketch numpy

Gerar assinaturas MinHash

Vamos gerar assinaturas MinHash de 256 dimensões, com cada valor de hash representado como um inteiro de 64 bits. Isso se alinha com o formato de vetor esperado para 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

Cada assinatura tem 256 × 64 bits = 2048 bytes. Esta cadeia de bytes pode ser inserida diretamente num campo BINARY_VECTOR. Para mais informações sobre os vectores binários utilizados no Milvus, consulte Vetor binário.

(Opcional) Preparar conjuntos de tokens brutos (para pesquisa refinada)

Por padrão, o Milvus usa apenas as assinaturas MinHash e o índice LSH para encontrar vizinhos aproximados. Isso é rápido, mas pode retornar falsos positivos ou perder correspondências próximas.

Se você quiser uma similaridade Jaccard precisa, o Milvus suporta a pesquisa refinada que usa conjuntos de tokens originais. Para habilitá-la:

• Armazene os conjuntos de tokens como um campo VARCHAR separado

• Defina "with_raw_data": True ao criar parâmetros de índice

• E ativar "mh_search_with_jaccard": True ao efetuar a pesquisa de semelhanças

Exemplo de extração de conjuntos de símbolos:

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

Usar o MinHash LSH

Quando os vectores MinHash e os conjuntos de tokens originais estiverem prontos, pode armazená-los, indexá-los e pesquisá-los utilizando o Milvus com MINHASH_LSH.

Conecte-se ao seu cluster

from pymilvus import MilvusClient

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

// java

// nodejs

// go

# restful

Definir esquema de coleção

Defina um esquema com:

• A chave primária

• Um campo BINARY_VECTOR para as assinaturas MinHash

• Um campo VARCHAR para o conjunto de tokens original (se a pesquisa refinada estiver activada)

• Opcionalmente, um campo document para o texto original

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

Construir parâmetros de índice e criar coleção

Crie um índice MINHASH_LSH com o refinamento Jaccard ativado:

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

Para obter mais informações sobre os parâmetros de criação de índices, consulte Parâmetros de criação de índices.

Inserir dados

Para cada documento, prepare:

• Uma assinatura MinHash binária

• Uma cadeia de caracteres serializada do conjunto de tokens

• (Opcionalmente) o texto original

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

Realizar pesquisa de similaridade

Milvus suporta dois modos de pesquisa de similaridade usando MinHash LSH:

• Pesquisa aproximada - usa apenas assinaturas MinHash e LSH para resultados rápidos, mas probabilísticos.

• Pesquisa refinada - calcula novamente a similaridade Jaccard usando conjuntos de tokens originais para melhorar a precisão.

5.1 Preparar a consulta

Para executar uma pesquisa de similaridade, gere uma assinatura MinHash para o documento de consulta. Essa assinatura deve corresponder à mesma dimensão e formato de codificação usados durante a inserção de dados.

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

// java

// nodejs

// go

# restful

5.2 Pesquisa aproximada (somente LSH)

É rápida e escalável, mas pode falhar correspondências próximas ou incluir falsos positivos:

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 Pesquisa refinada (recomendada para precisão):

Permite uma comparação Jaccard precisa usando os conjuntos de tokens originais armazenados no Milvus. É um pouco mais lenta, mas recomendada para tarefas sensíveis à qualidade:

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

Parâmetros de índice

Esta seção fornece uma visão geral dos parâmetros usados para criar um índice e realizar pesquisas no índice.

Parâmetros de criação de índice

A tabela a seguir lista os parâmetros que podem ser configurados em params ao criar um índice.

Parâmetro	Descrição	Intervalo de valores	Sugestão de ajuste
mh_element_bit_width	Largura de bit de cada valor de hash na assinatura MinHash. Deve ser divisível por 8.	8, 16, 32, 64	Use 32 para obter desempenho e precisão equilibrados. Use 64 para obter maior precisão com conjuntos de dados maiores. Use 16 para economizar memória com perda aceitável de precisão.
mh_lsh_band	Número de bandas para dividir a assinatura MinHash para LSH. Controla a troca entre desempenho e recuperação.	[1, signature_length]	Para assinaturas de 128 dígitos: comece com 32 bandas (4 valores/banda). Aumentar para 64 para uma maior recuperação, diminuir para 16 para um melhor desempenho. Deve dividir o comprimento da assinatura uniformemente.
mh_lsh_code_in_mem	Se deve armazenar códigos hash LSH em memória anónima (true) ou usar mapeamento de memória (false).	verdadeiro, falso	Use false para grandes conjuntos de dados (>1M conjuntos) para reduzir o uso de memória. Use true para conjuntos de dados menores que exigem velocidade máxima de pesquisa.
with_raw_data	Se deve armazenar assinaturas MinHash originais juntamente com códigos LSH para refinamento.	verdadeiro, falso	Use true quando for necessária alta precisão e o custo de armazenamento for aceitável. Utilizar false para minimizar a sobrecarga de armazenamento com uma ligeira redução da precisão.
mh_lsh_bloom_false_positive_prob	Probabilidade de falsos positivos para o filtro Bloom usado na otimização do balde LSH.	[0.001, 0.1]	Use 0.01 para equilibrar o uso de memória e a precisão. Valores mais baixos (0.001) reduzem os falsos positivos mas aumentam a memória. Valores mais altos (0.05) poupam memória mas podem reduzir a precisão.

Parâmetros de pesquisa específicos do índice

A tabela a seguir lista os parâmetros que podem ser configurados em search_params.params ao pesquisar no índice.

Parâmetro	Descrição	Intervalo de valores	Sugestão de ajuste
mh_search_with_jaccard	Se deve ser efectuado o cálculo exato da similaridade Jaccard nos resultados candidatos para refinamento.	true, false	Utilize true para aplicações que exijam elevada precisão (por exemplo, desduplicação). Utilize false para uma pesquisa aproximada mais rápida quando é aceitável uma ligeira perda de precisão.
refine_k	Número de candidatos a recuperar antes do refinamento Jaccard. Só é efetivo quando mh_search_with_jaccard é true.	[top_k, *top_k * 10*]	Defina para 2-5x o top_k desejado para um bom equilíbrio entre a recuperação e o desempenho. Valores mais altos melhoram a recuperação, mas aumentam o custo de computação.
mh_lsh_batch_search	Se deve ser activada a otimização em lote para várias consultas simultâneas.	verdadeiro, falso	Use true ao pesquisar com várias consultas simultaneamente para obter melhor rendimento. Use false para cenários de consulta única para reduzir a sobrecarga de memória.