MINHASH_LSH

Deduplikasi yang efisien dan pencarian kemiripan sangat penting untuk dataset pembelajaran mesin berskala besar, terutama untuk tugas-tugas seperti membersihkan korpora pelatihan untuk Model Bahasa Besar (LLM). Ketika berurusan dengan jutaan atau miliaran dokumen, pencocokan tepat tradisional menjadi terlalu lambat dan mahal.

Indeks MINHASH_LSH di Milvus memungkinkan deduplikasi perkiraan yang cepat, terukur, dan akurat dengan menggabungkan dua teknik yang kuat:

• MinHash: Dengan cepat menghasilkan tanda tangan ringkas (atau "sidik jari") untuk memperkirakan kemiripan dokumen.

• Hashing yang Peka terhadap Lokalitas (LSH): Menemukan dengan cepat kelompok dokumen yang mirip berdasarkan tanda tangan MinHash mereka.

Panduan ini memandu Anda melalui konsep, prasyarat, penyiapan, dan praktik terbaik untuk menggunakan MINHASH_LSH di Milvus.

Gambaran Umum

Kesamaan Jaccard

Kesamaan Jaccard mengukur tumpang tindih antara dua set A dan B, yang secara formal didefinisikan sebagai:

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

Di mana nilainya berkisar dari 0 (benar-benar terpisah) hingga 1 (identik).

Namun, menghitung kemiripan Jaccard dengan tepat antara semua pasangan dokumen dalam set data berskala besar akan memakan waktu dan memori yang sangat mahal - O(n²) jika n besar. Hal ini membuatnya tidak memungkinkan untuk kasus-kasus penggunaan seperti pembersihan korpus pelatihan LLM atau analisis dokumen berskala web.

Tanda tangan MinHash: Perkiraan kesamaan Jaccard

MinHash adalah teknik probabilistik yang menawarkan cara yang efisien untuk memperkirakan kemiripan Jaccard. Teknik ini bekerja dengan mengubah setiap set menjadi vektor tanda tangan yang ringkas, menyimpan informasi yang cukup untuk memperkirakan kemiripan set secara efisien.

Ide intinya:

Semakin mirip dua set, semakin besar kemungkinan tanda tangan MinHash mereka akan cocok pada posisi yang sama. Properti ini memungkinkan MinHash untuk memperkirakan kemiripan Jaccard antar set.

Properti ini memungkinkan MinHash untuk memperkirakan kemiripan Jaccard antar set tanpa perlu membandingkan set lengkap secara langsung.

Proses MinHash melibatkan:

1. Shingling: Mengonversi dokumen menjadi kumpulan urutan token yang tumpang tindih (shingling)

2. Hashing: Menerapkan beberapa fungsi hash independen ke setiap sirap

3. Seleksi Min: Untuk setiap fungsi hash, catat nilai hash minimum di semua sirap

Anda dapat melihat seluruh proses yang diilustrasikan di bawah ini:

Alur Kerja Minhash

LSH untuk MinHash

Walaupun tanda tangan MinHash secara signifikan mengurangi biaya komputasi kemiripan Jaccard yang tepat antara dokumen, membandingkan setiap pasangan vektor tanda tangan secara menyeluruh masih tidak efisien dalam skala besar.

Untuk mengatasi hal ini, LSH digunakan. LSH memungkinkan pencarian kemiripan yang cepat dengan memastikan bahwa item yang mirip di-hash ke dalam "bucket" yang sama dengan probabilitas yang tinggi - menghindari kebutuhan untuk membandingkan setiap pasangan secara langsung.

Prosesnya meliputi:

1. Segmentasi tanda tangan:

   Tanda tangan MinHash n-dimensi dibagi menjadi b band. Setiap pita berisi r nilai hash yang berurutan, sehingga total panjang tanda tangan memenuhi: n = b × r.

   Sebagai contoh, jika Anda memiliki tanda tangan MinHash 128 dimensi(n = 128) dan membaginya menjadi 32 band(b = 32), maka setiap band berisi 4 nilai hash(r = 4).

2. Hash tingkat band:

   Setelah segmentasi, setiap pita diproses secara independen menggunakan fungsi hash standar untuk menetapkannya ke dalam sebuah bucket. Jika dua tanda tangan menghasilkan nilai hash yang sama dalam sebuah band-yaitu, mereka masuk ke dalam ember yang sama-mereka dianggap sebagai pasangan yang potensial.

3. Pemilihan kandidat:

   Pasangan yang bertabrakan dalam setidaknya satu pita dipilih sebagai kandidat kemiripan.

Pertimbangkan tiga dokumen dengan tanda tangan MinHash 128 dimensi:

Alur Kerja Lsh 1

Pertama, LSH membagi tanda tangan 128 dimensi menjadi 32 band yang masing-masing terdiri dari 4 nilai yang berurutan:

Alur Kerja Lsh 2

Kemudian, setiap band di-hash ke dalam ember yang berbeda menggunakan fungsi hash. Pasangan dokumen yang berbagi ember dipilih sebagai kandidat kemiripan. Pada contoh di bawah ini, Dokumen A dan Dokumen B dipilih sebagai kandidat kemiripan karena hasil hash mereka bertabrakan di Band 0:

Alur Kerja Lsh 3

MHJACCARD: Membandingkan tanda tangan MinHash

Tanda tangan MinHash memperkirakan kesamaan Jaccard antara set menggunakan vektor biner dengan panjang tetap. Namun, karena tanda tangan ini tidak mempertahankan set asli, metrik standar seperti JACCARD, L2, atau COSINE tidak dapat diterapkan secara langsung untuk membandingkannya.

Untuk mengatasi hal ini, Milvus memperkenalkan jenis metrik khusus yang disebut MHJACCARD, yang didesain secara khusus untuk membandingkan tanda tangan MinHash.

Ketika menggunakan MinHash di Milvus:

• Bidang vektor harus bertipe BINARY_VECTOR

• index_type haruslah MINHASH_LSH (atau BIN_FLAT)

• metric_type harus diatur ke MHJACCARD

Menggunakan metrik lain akan menjadi tidak valid atau memberikan hasil yang salah.

Untuk informasi lebih lanjut tentang jenis metrik ini, lihat MHJACCARD.

Alur kerja deduplikasi

Proses deduplikasi yang didukung oleh MinHash LSH memungkinkan Milvus untuk secara efisien mengidentifikasi dan menyaring teks yang hampir duplikat atau catatan terstruktur sebelum memasukkannya ke dalam koleksi.

1. Potongan & proses awal: Pisahkan data teks yang masuk atau data terstruktur (misalnya, catatan, bidang) menjadi potongan-potongan; menormalkan teks (huruf kecil, penghapusan tanda baca), dan menghapus kata henti sesuai kebutuhan.

2. Konstruksi fitur: Membangun set token yang digunakan untuk MinHash (misalnya, shingles dari teks; token bidang gabungan untuk data terstruktur).

3. Pembuatan tanda tangan MinHash: Menghitung tanda tangan MinHash untuk setiap potongan atau catatan.

4. Konversi vektor biner: Mengonversi tanda tangan menjadi vektor biner yang kompatibel dengan Milvus.

5. Cari sebelum memasukkan: Gunakan indeks MinHash LSH untuk mencari koleksi target untuk mencari duplikat yang hampir sama dari item yang masuk.

6. Sisipkan & simpan: Sisipkan hanya item unik ke dalam koleksi. Item-item tersebut akan dapat dicari untuk pemeriksaan dedup di masa mendatang.

Prasyarat

Sebelum menggunakan MinHash LSH di Milvus, Anda harus membuat tanda tangan MinHash terlebih dahulu. Tanda tangan biner ringkas ini mendekati kemiripan Jaccard antar set dan diperlukan untuk pencarian berbasis MHJACCARD di Milvus.

Pilih metode untuk menghasilkan tanda tangan MinHash

Tergantung pada beban kerja Anda, Anda dapat memilih:

• Menggunakan Python datasketch untuk kesederhanaan (direkomendasikan untuk pembuatan prototipe)

• Menggunakan alat terdistribusi (misalnya, Spark, Ray) untuk dataset berskala besar

• Menerapkan logika khusus (NumPy, C++, dll.) jika penyetelan kinerja sangat penting

Dalam panduan ini, kami menggunakan datasketch untuk kesederhanaan dan kompatibilitas dengan format input Milvus.

Menginstal pustaka-pustaka yang diperlukan

Instal paket-paket yang diperlukan untuk contoh ini:

pip install pymilvus datasketch numpy

Hasilkan tanda tangan MinHash

Kita akan menghasilkan tanda tangan MinHash 256 dimensi, dengan setiap nilai hash direpresentasikan sebagai bilangan bulat 64-bit. Ini sesuai dengan format vektor yang diharapkan untuk 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

Setiap tanda tangan berukuran 256 × 64 bit = 2048 byte. String byte ini dapat langsung dimasukkan ke dalam bidang BINARY_VECTOR. Untuk informasi lebih lanjut mengenai vektor biner yang digunakan di Milvus, lihat Vektor Biner.

(Opsional) Menyiapkan set token mentah (untuk pencarian yang disempurnakan)

Secara default, Milvus hanya menggunakan tanda tangan MinHash dan indeks LSH untuk menemukan perkiraan tetangga. Ini cepat tetapi dapat menghasilkan positif palsu atau melewatkan kecocokan yang dekat.

Jika Anda menginginkan kemiripan Jaccard yang akurat, Milvus mendukung pencarian yang disempurnakan yang menggunakan set token asli. Untuk mengaktifkannya:

• Simpan set token sebagai bidang VARCHAR yang terpisah

• Tetapkan "with_raw_data": True saat membangun parameter indeks

• Dan aktifkan "mh_search_with_jaccard": True saat melakukan pencarian kesamaan

Contoh ekstraksi set token:

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

Gunakan MinHash LSH

Setelah vektor MinHash dan set token asli Anda siap, Anda dapat menyimpan, mengindeks, dan mencarinya menggunakan Milvus dengan MINHASH_LSH.

Menghubungkan ke klaster Anda

from pymilvus import MilvusClient

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

// java

// nodejs

// go

# restful

Tentukan skema koleksi

Tentukan skema dengan:

• Kunci utama

• Bidang BINARY_VECTOR untuk tanda tangan MinHash

• Bidang VARCHAR untuk kumpulan token asli (jika pencarian yang disempurnakan diaktifkan)

• Secara opsional, sebuah bidang document untuk teks asli

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

Membangun parameter indeks dan membuat koleksi

Buat indeks MINHASH_LSH dengan penyempurnaan Jaccard diaktifkan:

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

Untuk informasi lebih lanjut tentang parameter pembuatan indeks, lihat Parameter pembuatan indeks.

Memasukkan data

Untuk setiap dokumen, siapkan:

• Tanda tangan MinHash biner

• String set token yang diserialisasikan

• (Opsional) teks asli

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

Lakukan pencarian kemiripan

Milvus mendukung dua mode pencarian kemiripan menggunakan MinHash LSH:

• Pencarian perkiraan - hanya menggunakan tanda tangan MinHash dan LSH untuk hasil yang cepat namun probabilistik.

• Pencarian yangdisempurnakan - menghitung ulang kemiripan Jaccard menggunakan set token asli untuk meningkatkan akurasi.

5.1 Menyiapkan kueri

Untuk melakukan pencarian kemiripan, buatlah tanda tangan MinHash untuk dokumen kueri. Tanda tangan ini harus sesuai dengan dimensi dan format pengkodean yang sama dengan yang digunakan saat penyisipan data.

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

// java

// nodejs

// go

# restful

5.2 Pencarian perkiraan (khusus LSH)

Pencarian ini cepat dan terukur, tetapi mungkin melewatkan kecocokan yang dekat atau menyertakan positif palsu:

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 Pencarian yang disempurnakan (direkomendasikan untuk akurasi):

Ini memungkinkan perbandingan Jaccard yang akurat menggunakan set token asli yang disimpan di Milvus. Ini sedikit lebih lambat tetapi direkomendasikan untuk tugas-tugas yang sensitif terhadap kualitas:

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

Parameter indeks

Bagian ini memberikan gambaran umum tentang parameter yang digunakan untuk membangun indeks dan melakukan pencarian pada indeks.

Parameter pembangunan indeks

Tabel berikut mencantumkan parameter yang dapat dikonfigurasi di params saat membangun indeks.

Parameter	Deskripsi	Rentang Nilai	Saran Penyetelan
mh_element_bit_width	Lebar bit dari setiap nilai hash dalam tanda tangan MinHash. Harus dapat dibagi dengan 8.	8, 16, 32, 64	Gunakan 32 untuk performa dan akurasi yang seimbang. Gunakan 64 untuk presisi yang lebih tinggi dengan set data yang lebih besar. Gunakan 16 untuk menghemat memori dengan kehilangan akurasi yang dapat diterima.
mh_lsh_band	Jumlah band untuk membagi tanda tangan MinHash untuk LSH. Mengontrol tradeoff recall-performance.	[1, panjang_tanda tangan]	Untuk tanda tangan 128-bit: mulai dengan 32 pita (4 nilai/pita). Naikkan ke 64 untuk penarikan yang lebih tinggi, turunkan ke 16 untuk performa yang lebih baik. Harus membagi panjang tanda tangan secara merata.
mh_lsh_code_in_mem	Apakah akan menyimpan kode hash LSH di memori anonim (true) atau menggunakan pemetaan memori (false).	benar, salah	Gunakan false untuk set data yang besar (>1 juta set) untuk mengurangi penggunaan memori. Gunakan true untuk kumpulan data yang lebih kecil yang membutuhkan kecepatan pencarian maksimum.
with_raw_data	Apakah akan menyimpan tanda tangan MinHash asli bersama dengan kode LSH untuk penyempurnaan.	benar, salah	Gunakan true ketika presisi tinggi diperlukan dan biaya penyimpanan dapat diterima. Gunakan false untuk meminimalkan biaya penyimpanan dengan sedikit pengurangan akurasi.
mh_lsh_bloom_false_positive_prob	Probabilitas positif palsu untuk filter Bloom yang digunakan dalam pengoptimalan bucket LSH.	[0.001, 0.1]	Gunakan 0.01 untuk penggunaan memori dan akurasi yang seimbang. Nilai yang lebih rendah (0.001) mengurangi positif palsu tetapi meningkatkan memori. Nilai yang lebih tinggi (0.05) menghemat memori tetapi dapat mengurangi presisi.

Parameter pencarian khusus indeks

Tabel berikut mencantumkan parameter yang dapat dikonfigurasi di search_params.params saat mencari di indeks.

Parameter	Deskripsi	Rentang Nilai	Saran Penyetelan
mh_search_with_jaccard	Apakah akan melakukan penghitungan kemiripan Jaccard yang tepat pada hasil kandidat untuk penyempurnaan.	benar, salah	Gunakan true untuk aplikasi yang membutuhkan presisi tinggi (misalnya, deduplikasi). Gunakan false untuk pencarian perkiraan yang lebih cepat ketika sedikit kehilangan akurasi dapat diterima.
refine_k	Jumlah kandidat yang harus diambil sebelum perbaikan Jaccard. Hanya efektif jika mh_search_with_jaccard adalah true.	[top_k, *top_k * 10*]	Setel ke 2-5x top_k yang diinginkan untuk keseimbangan performa-penarikan yang baik. Nilai yang lebih tinggi meningkatkan penarikan tetapi meningkatkan biaya komputasi.
mh_lsh_batch_search	Apakah akan mengaktifkan pengoptimalan batch untuk beberapa kueri simultan.	benar, salah	Gunakan true saat mencari dengan beberapa kueri secara bersamaan untuk hasil yang lebih baik. Gunakan false untuk skenario kueri tunggal untuk mengurangi overhead memori.