MINHASH_LSH

Эффективная дедупликация и поиск сходства очень важны для больших наборов данных машинного обучения, особенно для таких задач, как очистка обучающих корпораций для больших языковых моделей (LLM). Когда речь идет о миллионах или миллиардах документов, традиционное точное соответствие становится слишком медленным и дорогостоящим.

Индекс MINHASH_LSH в Milvus обеспечивает быструю, масштабируемую и точную приблизительную дедупликацию, объединяя две мощные техники:

• MinHash: Быстро генерирует компактные подписи (или "отпечатки пальцев") для оценки сходства документов.

• Локально-чувствительное хэширование (LSH): Быстрое нахождение групп похожих документов на основе их подписей MinHash.

В этом руководстве вы узнаете о концепциях, предпосылках, настройке и лучших практиках использования MINHASH_LSH в Milvus.

Обзор

Сходство по Жаккарду

Сходство Жаккара измеряет степень совпадения двух множеств A и B, формально определяемую как:

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

Где его значение варьируется от 0 (полностью несовпадающие) до 1 (идентичные).

Однако точное вычисление сходства Жаккара между всеми парами документов в больших наборах данных требует больших затрат времени и памяти - O(n² ), если n велико. Это делает его невыполнимым для таких случаев, как очистка учебных корпусов LLM или анализ документов в веб-масштабе.

Подписи MinHash: Приблизительное сходство по Жаккарду

MinHash - это вероятностная техника, которая предлагает эффективный способ оценки сходства по Жаккарду. Она работает путем преобразования каждого набора в компактный вектор сигнатур, сохраняющий достаточно информации для эффективной аппроксимации сходства наборов.

Основная идея:

Чем более похожи два набора, тем больше вероятность того, что их сигнатуры MinHash будут совпадать в одних и тех же позициях. Это свойство позволяет MinHash аппроксимировать сходство по Жаккарду между наборами.

Это свойство позволяет MinHash аппроксимировать сходство по Жаккарду между наборами без необходимости прямого сравнения полных наборов.

Процесс MinHash включает в себя:

1. Шингование: Преобразование документов в наборы перекрывающихся последовательностей лексем (шинглов).

2. Хеширование: применение нескольких независимых хеш-функций к каждому шинглу.

3. Выбор минимума: Для каждой хэш-функции записываем минимальное значение хэша для всех шинглов.

Весь процесс показан на рисунке ниже:

Рабочий процесс Minhash

LSH для MinHash

Хотя подписи MinHash значительно снижают затраты на вычисление точного сходства по Жаккарду между документами, исчерпывающее сравнение каждой пары векторов подписей все еще неэффективно в масштабе.

Для решения этой проблемы используется 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 Workflow 1

Сначала LSH делит 128-мерную подпись на 32 диапазона по 4 последовательных значения в каждом:

Lsh Workflow 2

Затем каждая полоса хэшируется в различные ведра с помощью хэш-функции. Пары документов, разделяющие бакеты, выбираются в качестве кандидатов на сходство. В приведенном ниже примере документы A и B выбраны в качестве кандидатов на сходство, поскольку их результаты хэширования совпадают в полосе 0:

Lsh Workflow 3

MHJACCARD: Сравнение подписей MinHash

Подписи MinHash аппроксимируют сходство Жаккара между наборами с помощью двоичных векторов фиксированной длины. Однако, поскольку эти сигнатуры не сохраняют исходные наборы, стандартные метрики, такие как JACCARD, L2 или COSINE, не могут быть напрямую применены для их сравнения.

Чтобы решить эту проблему, Milvus вводит специализированный тип метрики, называемый MHJACCARD, разработанный специально для сравнения подписей MinHash.

При использовании MinHash в Milvus:

• Векторное поле должно быть типа 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. Вставить и сохранить: Вставляйте в коллекцию только уникальные элементы. Они становятся доступными для поиска при последующих проверках вычитания.

Предварительные условия

Перед использованием MinHash LSH в Milvus необходимо сначала сгенерировать сигнатуры MinHash. Эти компактные двоичные сигнатуры аппроксимируют сходство Жаккара между наборами и необходимы для поиска в Milvus на основе MHJACCARD.

Выбор метода генерации сигнатур MinHash

В зависимости от объема работы вы можете выбрать:

• Использовать Python's datasketch для простоты (рекомендуется для создания прототипов)

• Использовать распределенные инструменты (например, Spark, Ray) для работы с большими массивами данных

• Реализовать пользовательскую логику (NumPy, C++ и т. д.), если важна настройка производительности.

В этом руководстве мы используем datasketch для простоты и совместимости с входным форматом Milvus.

Установите необходимые библиотеки

Установите необходимые пакеты для этого примера:

pip install pymilvus datasketch numpy

Генерация сигнатур MinHash

Мы сгенерируем 256-мерные подписи MinHash, каждое хэш-значение которых представлено в виде 64-битного целого числа. Это соответствует ожидаемому векторному формату для 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 для поиска приблизительных соседей. Это быстро, но может давать ложные срабатывания или пропускать близкие совпадения.

Если вам нужно точное сходство по Жаккарду, 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 и исходные наборы токенов готовы, вы можете хранить, индексировать и искать их с помощью Milvus с MINHASH_LSH.

Подключитесь к вашему кластеру

from pymilvus import MilvusClient

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

// java

// nodejs

// go

# restful

Определите схему коллекции

Определите схему с:

• Первичный ключ

• Поле BINARY_VECTOR для сигнатур MinHash

• Поле 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

Построение параметров индекса и создание коллекции

Построение индекса 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 для получения быстрых, но вероятностных результатов.

• Уточненный поиск - повторное вычисление сходства по Жаккарду с использованием исходных наборов токенов для повышения точности.

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. Он немного медленнее, но рекомендуется для задач, чувствительных к качеству:

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	Количество полос, на которые делится сигнатура MinHash для LSH. Управляет компромиссом между отзывом и производительностью.	[1, signature_length].	Для 128-мерных сигнатур: начните с 32 полос (4 значения/полосу). Увеличьте до 64 для повышения запоминаемости, уменьшите до 16 для повышения производительности. Длина подписи должна делиться равномерно.
mh_lsh_code_in_mem	Хранить ли хэш-коды LSH в анонимной памяти (true) или использовать отображение памяти (false).	true, false	Используйте false для больших наборов данных (>1M наборов), чтобы уменьшить потребление памяти. Используйте true для небольших наборов данных, требующих максимальной скорости поиска.
with_raw_data	Хранить ли оригинальные сигнатуры MinHash вместе с кодами LSH для уточнения.	true, false	Используйте true, если требуется высокая точность и стоимость хранения приемлема. Используйте false для минимизации затрат на хранение при небольшом снижении точности.
mh_lsh_bloom_false_positive_prob	Вероятность ложного срабатывания для фильтра Блума, используемого при оптимизации LSH bucket.	[0.001, 0.1]	Используйте 0.01, чтобы сбалансировать использование памяти и точность. Меньшие значения (0.001) уменьшают количество ложных срабатываний, но увеличивают объем памяти. Более высокие значения (0.05) экономят память, но могут снизить точность.

Параметры поиска, специфичные для индекса

В следующей таблице перечислены параметры, которые могут быть настроены в search_params.params при поиске по индексу.

Параметр	Описание	Диапазон значений	Tuning Suggestion
mh_search_with_jaccard	Выполнять ли точный расчет сходства по Жаккарду для результатов-кандидатов на уточнение.	true, false	Используйте true для приложений, требующих высокой точности (например, дедупликация). Используйте false для более быстрого приблизительного поиска, когда небольшая потеря точности допустима.
refine_k	Количество кандидатов, которые необходимо получить перед уточнением по Жаккарду. Эффективно только в том случае, если mh_search_with_jaccard - true.	[top_k, *top_k * 10*].	Устанавливается в 2-5 раз больше желаемого top_k для хорошего баланса отзыв-производительность. Более высокие значения улучшают отзыв, но увеличивают стоимость вычислений.
mh_lsh_batch_search	Включать ли пакетную оптимизацию для нескольких одновременных запросов.	true, false	Используйте true при одновременном поиске по нескольким запросам для повышения пропускной способности. Используйте false для сценариев с одним запросом, чтобы уменьшить нагрузку на память.