MINHASH_LSH

La deduplicación eficiente y la búsqueda de similitudes son fundamentales para los conjuntos de datos de aprendizaje automático a gran escala, especialmente para tareas como la limpieza de corpus de entrenamiento para grandes modelos lingüísticos (LLM). Cuando se trata de millones o miles de millones de documentos, la búsqueda exacta tradicional resulta demasiado lenta y costosa.

El índice MINHASH_LSH de Milvus permite una deduplicación aproximada rápida, escalable y precisa mediante la combinación de dos potentes técnicas:

• MinHash: Genera rápidamente firmas compactas (o "huellas dactilares") para estimar la similitud de los documentos.

• Hashing sensible a la localización (LSH): Encuentra rápidamente grupos de documentos similares basándose en sus firmas MinHash.

Esta guía le guía a través de los conceptos, prerrequisitos, configuración y mejores prácticas para utilizar MINHASH_LSH en Milvus.

Visión general

Similitud Jaccard

La similitud de Jaccard mide el solapamiento entre dos conjuntos A y B, formalmente definido como:

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

Donde su valor oscila entre 0 (completamente disjuntos) y 1 (idénticos).

Sin embargo, calcular exactamente la similitud de Jaccard entre todos los pares de documentos en conjuntos de datos a gran escala es costoso desde el punto de vista computacional (O(n²)) en tiempo y memoria cuando n es grande. Esto lo hace inviable para casos de uso como la limpieza de corpus de entrenamiento LLM o el análisis de documentos a escala web.

Firmas MinHash: Similitud de Jaccard aproximada

MinHash es una técnica probabilística que ofrece una forma eficaz de estimar la similitud de Jaccard. Funciona transformando cada conjunto en un vector de firmas compacto, preservando suficiente información para aproximar la similitud de conjuntos de forma eficiente.

La idea central:

Cuanto más parecidos sean los dos conjuntos, más probable será que sus firmas MinHash coincidan en las mismas posiciones. Esta propiedad permite a MinHash aproximar la similitud de Jaccard entre conjuntos.

Esta propiedad permite a MinHash aproximar la similitud de Jaccard entre conjuntos sin necesidad de comparar directamente los conjuntos completos.

El proceso MinHash implica:

1. Shingling: Convertir los documentos en conjuntos de secuencias de tokens superpuestos (shingles).

2. Hashing: aplicar múltiples funciones hash independientes a cada shingle

3. Selección de mínimos: Para cada función hash, registrar el valor hash mínimo de todas las fichas.

A continuación se ilustra todo el proceso:

Flujo de trabajo Minhash

LSH para MinHash

Aunque las firmas MinHash reducen significativamente el coste de calcular la similitud exacta de Jaccard entre documentos, comparar exhaustivamente cada par de vectores de firma sigue siendo ineficiente a escala.

Para solucionarlo, se utiliza LSH. LSH permite una búsqueda rápida y aproximada de similitudes, ya que garantiza que los elementos similares se agrupen en el mismo "cubo" con una alta probabilidad, evitando así la necesidad de comparar cada par directamente.

El proceso incluye

1. Segmentación de firmas:

   Una firma MinHash n-dimensional se divide en b bandas. Cada banda contiene r valores hash consecutivos, por lo que la longitud total de la firma satisface: n = b × r.

   Por ejemplo, si tienes una firma MinHash de 128 dimensiones(n = 128) y la divides en 32 bandas(b = 32), entonces cada banda contiene 4 valores hash(r = 4).

2. Hashing a nivel de banda:

   Tras la segmentación, cada banda se procesa de forma independiente utilizando una función hash estándar para asignarla a un bucket. Si dos firmas tienen el mismo valor hash dentro de una banda, es decir, están en el mismo cubo, se considera que pueden coincidir.

3. Selección de candidatos:

   Los pares que coinciden al menos en una banda se seleccionan como candidatos de similitud.

Considere tres documentos con firmas MinHash de 128 dimensiones:

Flujo de trabajo de Lsh 1

En primer lugar, LSH divide la firma de 128 dimensiones en 32 bandas de 4 valores consecutivos cada una:

Flujo de trabajo Lsh 2

A continuación, cada banda se divide en distintos buckets mediante una función hash. Los pares de documentos que comparten buckets se seleccionan como candidatos de similitud. En el ejemplo siguiente, el Documento A y el Documento B se seleccionan como candidatos de similitud porque sus resultados hash coinciden en la Banda 0:

Flujo de trabajo Lsh 3

MHJACCARD: Comparación de firmas MinHash

Las firmas MinHash aproximan la similitud de Jaccard entre conjuntos utilizando vectores binarios de longitud fija. Sin embargo, como estas firmas no conservan los conjuntos originales, no se pueden aplicar directamente métricas estándar como JACCARD, L2 o COSINE para compararlas.

Para solucionar esto, Milvus introduce un tipo de métrica especializada llamada MHJACCARD, diseñada específicamente para comparar firmas MinHash.

Cuando se utiliza MinHash en Milvus:

• El campo vectorial debe ser de tipo BINARY_VECTOR

• El index_type debe ser MINHASH_LSH (o BIN_FLAT)

• El valor metric_type debe ser MHJACCARD

El uso de otras métricas no será válido o producirá resultados incorrectos.

Para obtener más información sobre este tipo de métrica, consulte MHJACCARD.

Flujo de trabajo de deduplicación

El proceso de deduplicación impulsado por MinHash LSH permite a Milvus identificar y filtrar eficazmente los registros de texto o estructurados casi duplicados antes de insertarlos en la colección.

1. Trocear y preprocesar: Divide los datos de texto entrantes o los datos estructurados (por ejemplo, registros, campos) en trozos; normaliza el texto (minúsculas, eliminación de puntuación), y elimina las palabras clave según sea necesario.

2. Construcción de características: Construir el conjunto de tokens utilizado para MinHash (por ejemplo, shingles a partir de texto; tokens de campo concatenados para datos estructurados).

3. Generación de firmas MinHash: Calcular firmas MinHash para cada trozo o registro.

4. Conversión de vectores binarios: Convierte la firma en un vector binario compatible con Milvus.

5. Búsqueda antes de la inserción: Utiliza el índice LSH de MinHash para buscar en la colección de destino casi duplicados del elemento entrante.

6. Insertar y almacenar: Inserte sólo elementos únicos en la colección. Estos elementos se pueden buscar para futuras comprobaciones de dedup.

Requisitos previos

Antes de utilizar MinHash LSH en Milvus, primero debe generar firmas MinHash. Estas firmas binarias compactas aproximan la similitud de Jaccard entre conjuntos y son necesarias para la búsqueda basada en MHJACCARD en Milvus.

Elija un método para generar firmas MinHash

Dependiendo de su carga de trabajo, puede elegir:

• Usar Python datasketch por simplicidad (recomendado para la creación de prototipos)

• Utilizar herramientas distribuidas (por ejemplo, Spark, Ray) para conjuntos de datos a gran escala

• Implementar lógica personalizada (NumPy, C++, etc.) si el ajuste del rendimiento es crítico

En esta guía, utilizamos datasketch por simplicidad y compatibilidad con el formato de entrada Milvus.

Instalar las bibliotecas necesarias

Instale los paquetes necesarios para este ejemplo:

pip install pymilvus datasketch numpy

Generar firmas MinHash

Generaremos firmas MinHash de 256 dimensiones, con cada valor hash representado como un entero de 64 bits. Esto coincide con el formato vectorial 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 firma tiene 256 × 64 bits = 2048 bytes. Esta cadena de bytes puede insertarse directamente en un campo BINARY_VECTOR. Para obtener más información sobre los vectores binarios utilizados en Milvus, consulte Vector binario.

(Opcional) Preparar conjuntos de tokens sin procesar (para búsqueda refinada)

Por defecto, Milvus utiliza sólo las firmas MinHash y el índice LSH para encontrar vecinos aproximados. Esto es rápido pero puede devolver falsos positivos o pasar por alto coincidencias cercanas.

Si desea una similitud Jaccard precisa, Milvus admite la búsqueda refinada que utiliza conjuntos de símbolos originales. Para activarla

• Almacene los conjuntos de tokens como un campo VARCHAR separado.

• Establezca "with_raw_data": True al crear los parámetros del índice

• Y habilite "mh_search_with_jaccard": True al realizar la búsqueda de similitud

Ejemplo de extracción de conjuntos de tokens:

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

Utilizar MinHash LSH

Una vez que sus vectores MinHash y conjuntos de tokens originales estén listos, puede almacenarlos, indexarlos y buscarlos utilizando Milvus con MINHASH_LSH.

Conéctese a su clúster

from pymilvus import MilvusClient

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

// java

// nodejs

// go

# restful

Definir el esquema de la colección

Defina un esquema con:

• La clave primaria

• Un campo BINARY_VECTOR para las firmas MinHash

• Un campo VARCHAR para el conjunto de tokens original (si la búsqueda refinada está activada)

• Opcionalmente, un campo document para el 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 y crear colección

Construye un índice MINHASH_LSH con el refinamiento Jaccard habilitado:

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 obtener más información sobre los parámetros de creación de índices, consulte Parámetros de creación de índices.

Insertar datos

Para cada documento, prepare

• Una firma binaria MinHash

• Una cadena serializada del conjunto de tokens

• (opcionalmente) el 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 la búsqueda de similitud

Milvus soporta dos modos de búsqueda de similitud usando MinHash LSH:

• Búsqueda aproximada - utiliza sólo firmas MinHash y LSH para obtener resultados rápidos pero probabilísticos.

• Búsqueda refinada: vuelve a calcular la similitud de Jaccard utilizando los conjuntos de tokens originales para mejorar la precisión.

5.1 Preparar la consulta

Para realizar una búsqueda de similitud, genere una firma MinHash para el documento de la consulta. Esta firma debe coincidir con la misma dimensión y formato de codificación utilizados durante la inserción de datos.

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

// java

// nodejs

// go

# restful

5.2 Búsqueda aproximada (sólo LSH)

Es rápida y escalable, pero puede pasar por alto coincidencias cercanas o 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 Búsqueda refinada (recomendada por su precisión):

Esto permite una comparación Jaccard precisa utilizando los conjuntos de tokens originales almacenados en Milvus. Es ligeramente más lenta, pero se recomienda para tareas sensibles a la calidad:

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 del índice

Esta sección proporciona una visión general de los parámetros utilizados para construir un índice y realizar búsquedas en el índice.

Parámetros de creación de índices

La siguiente tabla enumera los parámetros que pueden configurarse en params cuando se construye un índice.

Parámetro	Descripción	Rango de valores	Sugerencia de ajuste
mh_element_bit_width	Ancho de bit de cada valor hash en la firma MinHash. Debe ser divisible por 8.	8, 16, 32, 64	Utilice 32 para un rendimiento y precisión equilibrados. Utilice 64 para una mayor precisión con conjuntos de datos más grandes. Utilice 16 para ahorrar memoria con una pérdida de precisión aceptable.
mh_lsh_band	Número de bandas para dividir la firma MinHash para LSH. Controla el equilibrio recall-rendimiento.	[1, longitud_firma]	Para firmas de 128 dígitos: comience con 32 bandas (4 valores/banda). Aumentar a 64 para una mayor recuperación, reducir a 16 para un mejor rendimiento. Debe dividir la longitud de la firma uniformemente.
mh_lsh_code_in_mem	Si almacenar códigos hash LSH en memoria anónima (true) o utilizar mapeo de memoria (false).	true, false	Utilice false para conjuntos de datos grandes (>1M conjuntos) para reducir el uso de memoria. Utilice true para conjuntos de datos más pequeños que requieran la máxima velocidad de búsqueda.
with_raw_data	Si se almacenan las firmas MinHash originales junto con los códigos LSH para su refinamiento.	true, false	Utilice true cuando se requiera una alta precisión y el coste de almacenamiento sea aceptable. Utilice false para minimizar la sobrecarga de almacenamiento con una ligera reducción de la precisión.
mh_lsh_bloom_false_positive_prob	Probabilidad de falsos positivos para el filtro Bloom utilizado en la optimización de cubos LSH.	[0.001, 0.1]	Utilice 0.01 para equilibrar el uso de memoria y la precisión. Los valores más bajos (0.001) reducen los falsos positivos pero aumentan la memoria. Los valores más altos (0.05) ahorran memoria pero pueden reducir la precisión.

Parámetros de búsqueda específicos del índice

La siguiente tabla enumera los parámetros que pueden configurarse en search_params.params al buscar en el índice.

Parámetro	Descripción	Rango de valores	Sugerencia de ajuste
mh_search_with_jaccard	Si se debe realizar el cálculo exacto de la similitud de Jaccard en los resultados candidatos para el refinamiento.	true, false	Utilice true para aplicaciones que requieran alta precisión (por ejemplo, deduplicación). Utilice false para una búsqueda aproximada más rápida cuando sea aceptable una ligera pérdida de precisión.
refine_k	Número de candidatos a recuperar antes del refinamiento de Jaccard. Sólo es efectivo cuando mh_search_with_jaccard es true.	[top_k, *top_k * 10*]	Establezca entre 2 y 5 veces el top_k deseado para obtener un buen equilibrio entre memoria y rendimiento. Los valores más altos mejoran la recuperación pero aumentan el coste de cálculo.
mh_lsh_batch_search	Activar o no la optimización por lotes para múltiples consultas simultáneas.	true, false	Utilice true cuando realice búsquedas con varias consultas simultáneas para mejorar el rendimiento. Utilice false cuando realice una sola consulta para reducir la sobrecarga de memoria.