Deteksi Duplikat Mirip dengan Kemiripan Jaccard dan MinHash

 (blog.nelhage.com)
1 poin oleh GN⁺ 2024-07-06 | 1 komentar | Bagikan ke WhatsApp
  • Dalam koleksi dokumen berskala besar, proses web crawling bisa mengambil halaman yang sama berkali-kali atau mencampurkan versi dengan sedikit perubahan, sehingga kemiripan Jaccard dan MinHash menjadi metode praktis untuk menemukan dokumen yang “hampir sama”
  • Kemiripan Jaccard mengubah dokumen menjadi himpunan fitur lalu menghitung ukuran irisan / ukuran gabungan, dan pasangan yang berada di atas ambang batas dianggap sebagai duplikat mirip, tetapi relasi ini umumnya tidak transitif
  • Jika semua pasangan dokumen dibandingkan, biayanya menjadi O(n²) terhadap ukuran korpus, sehingga MinHash merangkum setiap dokumen menjadi signature berukuran tetap untuk memperkirakan kemiripan secara probabilistik
  • Dengan menggunakan k fungsi hash, kemiripan dapat diestimasi dari rasio nilai pada posisi yang sama yang cocok di antara signature dua dokumen, dan syarat seperti min-wise independence penting dalam pemilihan fungsi hash
  • Menggunakan seluruh signature atau sebagian signature sebagai kunci grup memungkinkan kita mengatur probabilitas dokumen mirip masuk ke bucket yang sama; pendekatan n-gram dan tokenisasi menentukan sensitivitas deteksi serta biayanya

Sulitnya deteksi duplikat mirip

  • Tujuannya adalah menemukan dokumen yang tidak persis sama, tetapi hampir sama dalam kumpulan dokumen besar
    • Jika web di-crawl selama periode tertentu, halaman yang sama bisa diambil berkali-kali dengan metadata yang sedikit berbeda
    • Bisa juga ada beberapa versi halaman dengan perubahan kecil
  • Pendekatan dasarnya adalah mendefinisikan fungsi kemiripan S(A, B) antara dua dokumen, lalu menganggap pasangan dengan nilai setidaknya ambang batas Scrit sebagai duplikat mirip
  • “Hampir sama” umumnya bukan relasi transitif
    • A dan B, serta B dan C, bisa saja mirip di atas ambang batas
    • Pada saat yang sama, A dan C bisa berada di bawah ambang batas
    • Karena itu, deteksi duplikat mirip berskala besar lebih sulit ditangani daripada deteksi duplikat persis

Definisi kemiripan Jaccard

  • Indeks Jaccard menyatakan kemiripan dua himpunan berhingga sebagai ukuran irisan / ukuran gabungan

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

  • Jika dua himpunan mirip, sebagian besar elemennya sama, sehingga gabungannya hanya sedikit membesar dan irisannya hanya sedikit mengecil

  • Jika dua himpunan sepenuhnya terpisah, ukuran irisannya 0 sehingga kemiripan Jaccard bernilai 0

  • Jika dua himpunan identik, irisan dan gabungannya adalah himpunan yang sama, sehingga kemiripan Jaccard bernilai 1

  • Dokumen nyata berbentuk seperti string Unicode, sehingga dokumen harus terlebih dahulu diubah menjadi himpunan fitur

Masalah skalabilitas saat membandingkan semua pasangan

  • Setelah dokumen diubah menjadi himpunan fitur, definisi untuk menemukan pasangan dengan kemiripan Jaccard tinggi pada dasarnya sederhana
  • Namun jika semua pasangan dokumen dibandingkan, biayanya meningkat menjadi O(n²) terhadap ukuran korpus
  • Dalam deteksi duplikat persis, biaya ini dihindari dengan melakukan hash pada dokumen dan mengelompokkan dokumen yang berada di bucket hash yang sama
  • Dalam deteksi duplikat mirip, diperlukan jalan pintas serupa, dan di bidang ini hal tersebut disebut locality-sensitive hash
  • Untuk kemiripan Jaccard, ada teknik yang cocok untuk tujuan ini, dan intinya adalah MinHash

Memperkirakan kemiripan Jaccard dengan MinHash

  • MinHash memperkirakan kemiripan Jaccard hanya dengan signature kecil yang telah dihitung sebelumnya untuk tiap dokumen, tanpa perlu membandingkan seluruh himpunan setiap kali

  • Ide dasarnya adalah mengambil sampel elemen secara acak seragam dari gabungan, lalu melihat apakah elemen tersebut juga berada di irisan

  • Dalam praktiknya, alih-alih permutasi acak, digunakan fungsi hash H(x) yang baik, lalu fitur dengan nilai hash terkecil dari tiap himpunan disimpan

    [ a_{min} \leftarrow \min_{x \in A} H(x) ]

    [ b_{min} \leftarrow \min_{x \in B} H(x) ]

  • Operasi min memiliki sifat asosiatif, sehingga nilai hash minimum tiap dokumen dapat dipraproses secara independen

  • Probabilitas nilai hash minimum dua himpunan sama adalah sama dengan kemiripan Jaccard kedua himpunan tersebut

Banyak fungsi hash dan vektor signature

  • Jika hanya memakai satu fungsi hash, untuk dua dokumen kita hanya bisa memperoleh estimasi boolean “sama/berbeda”

  • Dengan memakai k fungsi hash yang berbeda, setiap dokumen dapat dirangkum sebagai vektor berisi k nilai MinHash

    [ A_{sig} = (\min_{x \in A} H_1(x), \min_{x \in A} H_2(x), \dots, \min_{x \in A} H_k(x)) ]

  • Kemiripan Jaccard diperkirakan dari rasio nilai pada posisi yang sama yang cocok di antara dua signature

    [ J(A, B) \approx \frac{1}{k} \sum_{i=1}^{k} (A_{sig}[i] = B_{sig}[i]) ]

  • Pemilihan keluarga fungsi hash adalah hal yang subtil

    • Tujuannya adalah memperkirakan permutasi acak atas seluruh ruang fitur
    • Keluarga fungsi hash nyata hanya merepresentasikan bagian yang sangat kecil dari semua permutasi yang mungkin
    • Korelasi yang tidak tepat harus dihindari, dan sifat terkait ini disebut min-wise independence
    • Masalah ini telah cukup banyak diteliti dan solusi yang efisien tersedia dalam literatur

Menemukan pasangan kandidat di seluruh korpus

  • Jika setiap dokumen direduksi menjadi fingerprint berisi k nilai hash, kemiripan Jaccard dapat diperkirakan secara efisien
  • Masalah yang tersisa adalah menemukan dokumen dengan kemiripan tinggi di seluruh korpus tanpa melihat semua pasangan dokumen
  • Strateginya adalah mengelompokkan dokumen berdasarkan suatu kunci, lalu hanya membandingkan dokumen dalam grup yang sama
  • Kunci grup harus dibuat agar dokumen mirip tergabung bersama dengan probabilitas tinggi, sementara dokumen yang tidak mirip sebisa mungkin tidak tergabung bersama

  • Menggunakan seluruh signature MinHash sebagai kunci

    • Cara paling sederhana adalah menggunakan semua k nilai MinHash sebagai satu kunci grup
    • Dua dokumen dianggap duplikat mirip hanya jika semua nilai MinHash cocok
    • Makalah GPT-3 menggunakan penghapusan duplikat mirip dalam pipeline persiapan dataset, dan dari ungkapan yang dikutip, hal itu ditafsirkan sebagai penggunaan implementasi MinHashLSH Spark dengan 10 hash
    • Keunggulan cara ini adalah kesederhanaan dan efisiensi
    • Pengelompokan berdasarkan satu string byte berkardinalitas tinggi mudah diskalakan secara horizontal
    • Ini setara dengan primitif dasar pada alat pemrosesan data, seperti “shuffle” antara map dan reduce di MapReduce
    • Jika kemiripan Jaccard dua dokumen adalah J(A, B) dan semua k nilai harus cocok, probabilitas collision untuk satu pasangan adalah J(A, B)^k
    • Jika k = 10, dokumen dengan kemiripan sekitar 0,6 atau kurang hampir tidak akan mengalami collision
    • Probabilitas kecocokan meningkat di sekitar kemiripan 0,95
    • Untuk tujuan menemukan saudara dokumen yang sangat dekat, ini bisa jadi cukup
    • Perhitungan J^k ini berlaku untuk satu pasangan dokumen
    • Jika ada banyak dokumen yang sangat mirip satu sama lain, probabilitas per pasangan tidak independen
    • Dalam praktiknya, dokumen-dokumen yang sangat mirip umumnya masuk ke paling banyak dua atau tiga bucket, sehingga hampir seluruh duplikat dapat ditemukan

Deteksi duplikat yang lebih longgar

  • Jika ingin menemukan bukan hanya dokumen dengan kemiripan mendekati 1, tetapi juga dokumen dengan kemiripan 0,8 atau 0,7 ke atas, penggunaan seluruh signature sebagai kunci bisa terlalu ketat

  • Jika hanya sebagian dari k MinHash yang digunakan sebagai kunci grup, kemungkinan collision pada kemiripan yang lebih rendah meningkat

    • Misalnya, setelah mengelompokkan berdasarkan 4 nilai MinHash pertama, di dalam bucket yang sama seluruh nilai MinHash dapat digunakan untuk memperkirakan kemiripan sebenarnya

  • Mengurangi jumlah hash memiliki batasan

    • J^r selalu lebih kecil dari J
    • Jika r terlalu kecil, collision yang salah bisa menjadi terlalu banyak

  • Sebagai gantinya, setiap dokumen dapat dibuatkan beberapa kunci dan dimasukkan ke beberapa bucket

    • Misalnya, menghitung k = 20 hash, memasukkannya ke b = 4 bucket, dan setiap kunci terdiri dari r = 5 hash

  • Probabilitas dua dokumen mengalami collision di setidaknya satu bucket adalah sebagai berikut

    [ p = 1 - (1 - J^r)^b ]

  • Dalam contoh yang memakai 4 grup dan 5 hash per grup, titik probabilitas collision 50% bergeser ke sekitar J = 0.7

  • Jika r dan b sama-sama lebih besar dari 1, kurva hasilnya umumnya berbentuk S, sehingga menyediakan ruang penyetelan antara sensitivitas, recall, dan biaya performa

Kaitan dengan HyperLogLog

  • Trik inti MinHash memiliki kemiripan dengan algoritme sketch seperti HyperLogLog
  • HyperLogLog melakukan hash pada setiap elemen stream dan menyimpan maksimum berjalan dari jumlah nol di awal nilai hash
  • Keduanya memetakan elemen masukan ke distribusi seragam dengan fungsi hash, lalu menghitung nilai ekstrem berjalan untuk memperkirakan sifat distribusional hanya dengan ringkasan berukuran konstan
  • Jika urutan bit dibayangkan terbalik, HyperLogLog dapat dilihat sebagai cara menghitung minimum berjalan dari log2(H(x)), sementara MinHash menggunakan minimum dari H(x) itu sendiri
  • Kedua struktur ini dalam suatu arti bersifat dual
    • Jika dua struktur HyperLogLog digabungkan, ukuran gabungan dua himpunan dapat diperkirakan
    • Jika dua struktur MinHash dibandingkan, ukuran relatif irisan dua himpunan dapat diperkirakan
  • Dengan menggabungkan kedua struktur, kita dapat membuat sketch yang mampu menangani pertanyaan tentang irisan dan gabungan himpunan arbitrer

Cara merepresentasikan dokumen sebagai himpunan

  • Untuk memakai Jaccard dan MinHash, dokumen string harus terlebih dahulu diubah menjadi himpunan fitur
  • Apa pun caranya, dokumen dapat dinormalisasi sebagai praproses

  • n-gram atau shingle

    • Dokumen dapat direpresentasikan sebagai himpunan semua n-gram yang muncul di dalamnya
    • Dalam literatur pemrosesan teks berskala besar, istilah “shingle” juga digunakan, tetapi di sini perannya sama dengan n-gram
    • Ada trade-off dalam memilih nilai n
    • Nilai kecil membandingkan dokumen secara lebih kasar
    • Misalnya, sebagian besar teks bahasa Inggris bisa terlihat cukup mirip dari sudut pandang bigram
    • Nilai besar menghasilkan fitur yang lebih membedakan dan himpunan yang lebih besar
    • Jika terlalu besar, sensitivitas bisa menurun, tetapi masalah performa kemungkinan muncul sebelum itu
    • Menurut Mining of Massive Datasets §3.2.2, pada berbagai aplikasi nilai antara n = 5 sampai 9 tampaknya umum dipilih

  • Pemisahan kata atau token

    • Masukan juga dapat dibagi menjadi “kata” atau “token”, lalu menggunakannya sebagai fitur
    • Kutipan dari makalah GPT-3 menyebut tokenizer standar Spark, yang tampaknya merujuk pada pyspark.ml.feature.Tokenizer, yang mengubah masukan menjadi huruf kecil dan memisahkannya berdasarkan spasi
    • NLTK tokenizer yang lebih canggih juga dapat digunakan
    • Pendekatan hibrida yang menggunakan n-gram dari token setelah tokenisasi juga dimungkinkan
    • Karena token individual memiliki entropi lebih tinggi daripada byte atau karakter, nilai n yang lebih kecil digunakan dalam kasus ini

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-06
Opini Hacker News

  • Banyak orang melewatkan bahwa metrik berbasis himpunan seperti kemiripan Jaccard (koefisien Tanimoto) atau skor F1 (koefisien Dice) juga bisa digunakan dengan cara yang sama untuk himpunan fuzzy
    Namun, kita harus memilih pasangan T-Norm / T-Conorm yang tepat untuk merepresentasikan konsep irisan dan gabungan pada himpunan fuzzy, dan jenisnya tak terhingga banyaknya
    Justru ini menjadi kelebihan karena kita bisa memilih pasangan yang sesuai dengan semantik yang diinginkan
    Dalam validasi segmentasi citra medis, saya pernah membahas hal ini ketika hasil segmentasi dan ground truth bukan berupa mask biner, melainkan berbentuk probabilistik/fuzzy: https://link.springer.com/chapter/10.1007/978-3-319-46723-8_..., https://ora.ox.ac.uk/objects/uuid:dc352697-c804-4257-8aec-08...
    Biasanya orang memberi threshold 0,5 untuk membuat himpunan biner lalu memakai varian biner Jaccard/Dice, tetapi ini tampaknya menurunkan presisi operator validasi sekitar dua digit
    Akibatnya, mereka mengumumkan bahwa algoritmanya 0,001 lebih baik daripada teknik terbaru, sambil mengabaikan fakta bahwa rentang kesalahan operator validasinya adalah 0,1

  • Untuk deduplikasi entri warga dalam basis data besar milik pemerintah Prancis, seorang klien pernah membuat implementasi Python sendiri dari teknik ini, dan itu bekerja dengan baik
    Kalau sekarang, mungkin saya akan menyarankan memakai datasketch: https://pypi.org/project/datasketch/
    Setelah mencari, ternyata alat baru untuk topik ini juga terus bermunculan. Misalnya, https://pypi.org/project/rensa/ adalah versi yang lebih khusus dan cepat daripada MinHash di datasketch, ditulis dengan Rust dan diberi sedikit lapisan Python di atasnya

    • Untuk deduplikasi orang, model Fellegi-Sunter juga merupakan pendekatan yang kuat. Splink adalah pustaka Python gratis yang mengimplementasikannya untuk dataset besar, dan tampaknya sebagian dari kedua pendekatan ini juga bisa digabungkan
      Saya perlu menyatakan bahwa saya adalah penulis utamanya
      Saya juga sudah membuat tutorial interaktif yang menjelaskan cara kerjanya: https://github.com/moj-analytical-services/splink, https://www.robinlinacre.com/intro_to_probabilistic_linkage/
    • Ada juga gaoya. Itu buatan saya, ditulis dengan Rust, dan juga menyediakan binding Python
      datasketch memang bagus, tetapi performanya belum cukup untuk use case saya, dan gaoya dipakai dalam sistem operasional clustering berskala besar: https://github.com/serega/gaoya

  • Kebetulannya luar biasa. Saya baru saja mengimplementasikan sebuah sistem MinHash yang mungkin menarik bagi seseorang
    Masalahnya adalah menemukan pseudoinverse dari beberapa submatriks yang sesuai di dalam sebuah matriks persegi besar
    Dengan identitas matriks seperti Woodbury dan Banachiewicz, kita bisa memperbarui invers dari submatriks yang “dekat” untuk menghitung invers baru dengan murah
    Simpan invers yang sudah dihitung dengan indeks baris/kolom sebagai kunci, lalu untuk setiap submatriks baru cari invers lama yang dekat untuk dijadikan titik awal pembaruan
    Saya menyelesaikan masalah ini dengan MinHash, dengan melakukan hash minimum pada indeks agar matriks-matriks yang dekat memiliki peluang tinggi untuk mendapatkan hash yang sama
    Dalam implementasi saya, saya menggunakan hash multi-resolusi agar selektivitas pencarian bisa disesuaikan seiring bertambahnya jumlah invers yang sudah dihitung

  • Untuk menambahkan sedikit latar belakang yang tidak ada di tulisan ini, setahu saya teknik ini dibuat pada masa awal Google untuk deduplikasi kumpulan hasil crawling
    Menarik juga bahwa pekerjaan membuat LLM dan membuat indeks teks web biasa ternyata sangat mirip
    Anda bisa membaca penjelasan detailnya di buku gratis Jeffrey Ullman, “Mining Massive Datasets”, yang menjelaskan banyak teknik keren dan mengesankan yang digunakan saat itu untuk membuat indeks seluruh internet
    Materi terkait bisa ditemukan gratis dengan mencari “chapter 3 pdf mmds ullman”
    Sunting: ternyata saya keliru, dan menurut Wikipedia teknik ini ditemukan di DEC untuk AltaVista: https://en.wikipedia.org/wiki/MinHash
    Bagaimanapun, buku Ullman memiliki penjelasan yang bagus, dan juga membahas bagaimana teknik ini digunakan di Google

  • Saat mencoba memahami MinHash dan variannya, saya merasa sulit mencerna konsepnya, jadi saya sedang membuat alat visualisasi online: https://websla.sh/tools/minhash
    Belum selesai, dan saya juga ingin menampilkan hal-hal seperti perhitungan kemiripan Jaccard, tetapi bahkan sekarang Anda sudah bisa memasukkan beberapa string dan melihat sendiri apa sebenarnya “minhash” itu

  • Menggunakan hashing atau jaringan saraf kecil bersama mesin pencarian vektor dan Tanimoto/Jaccard adalah strategi yang sangat umum dalam deduplikasi dataset berskala besar
    Ini bisa lebih cerdas daripada memakai pekerjaan MapReduce dengan kompleksitas linear
    Ada contoh proyek bagus dari Google yang menggunakan model RETSim dengan 500 ribu parameter dan engine USearch: https://github.com/google/unisim

  • Saat ini ada masalah serupa di PostgreSQL. Ada 600.000 feed_items dan skemanya adalah (feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer)
    Khususnya, kolom content dan summary pada beberapa item berita sangat mirip, tetapi tidak sama
    Ketika diberi dua item berita seperti ini, saya ingin menguranginya menjadi satu; adakah cara yang bagus?

    • Saya pernah mengimplementasikan sistem mirip MinHash di BigQuery, dan dapat menghitung cosine similarity di antara semua item Stack Overflow dalam waktu yang masuk akal
      Prosedur kasarnya seperti ini
      1. Gabungkan semua field teks dan pecah menjadi array n-gram, misalnya satuan 2 hingga n karakter
      2. Deklarasikan array global A dan B sepanjang n dan isi dengan integer acak 32–64 bit
      3. Hash setiap n-gram menjadi integer 32–64 bit, lalu kalikan hash itu dengan setiap nilai acak di array A, ambil sisa pembagian hasilnya dengan setiap nilai acak di array B, lalu ambil nilai minimumnya
        Tujuannya adalah mendapatkan array integer “minhashed” untuk setiap baris, dengan panjang yang sama seperti array pada langkah 2. Jika panjang array global dideklarasikan 64, array MinHash tiap baris juga akan sepanjang 64
      4. Dengan window function, jumlahkan N nilai MinHash yang berurutan untuk membucketkan array hash. Misalnya, jumlahkan tiap 4 baris berurutan
        Jika berhasil, bentangkan array ini sebagai “baris sumber”, lalu join dataset dengan dirinya sendiri berdasarkan tiap nilai MinHash yang sudah dibucketkan, sehingga kolom “baris target” ditambahkan
        Jika mengelompokkan berdasarkan kolom sumber/target dan menghitung jumlah kemunculan, Anda dapat memperkirakan seberapa mirip dua baris tersebut
        Pada dasarnya, semakin sering dua item di-hash ke bucket yang mirip, semakin mirip keduanya; Anda sendiri yang menentukan mulai titik mana perlu menghitung Jaccard atau cosine similarity berpasangan yang sebenarnya
    • Di sini, metode menggunakan text embedding dan cosine similarity bisa berguna: https://simonwillison.net/2023/Oct/23/embeddings/
    • Dengan MinHash, Anda bisa menghindari matriks jarak O(N^2) penuh, tetapi jika itemnya hanya 600.000, demi kesederhanaan mungkin saja menghitung seluruh matriks secara brute force
      Kuncinya adalah berapa banyak anggaran waktu yang tersedia
    • Jika menganggap dua item membahas keyword yang sangat mirip, Jaccard distance akan cocok
      Jika menganggap dua item berbagi teks yang sangat mirip, Levenshtein distance layak dicoba
    • Biarkan LLM membuat inverted index untuk item-item tersebut, tetapi paksa agar kardinalitasnya tetap rendah
      Dengan begitu, Jaccard similarity bisa digunakan

  • Saya suka artikelnya. Di NVIDIA, tim kami baru-baru ini merilis versi akselerasi GPU dari algoritma fuzzy deduplication yang dijelaskan, dan saya pikir komunitas ini juga mungkin tertarik
    Repositorinya ada di sini: https://github.com/NVIDIA/NeMo-Curator/
    Dokumentasi skrip fuzzy deduplication ada di sini: https://docs.nvidia.com/nemo-framework/user-guide/latest/dat...
    Ada juga contoh Python: https://github.com/NVIDIA/NeMo-Curator/blob/main/examples/fu...
    Saya ingin mendengar masukan

  • Teknik seperti ini sulit dipahami saat dibaca sebagai tulisan, tetapi termasuk jenis yang langsung terserap setelah kita beberapa kali memasukkan data sendiri ke contoh kode yang berjalan dan melihat proses internalnya
    Saya pertama kali mempelajari teknik ini dari Douglas Eck: https://research.google/people/douglas-eck/
    Di Google, teknik ini digunakan untuk clustering lagu, dan saya ingat ia berbicara tentang hashing dan vektor acak
    Saat itu saya bingung karena berpikir optimisasi dengan lebih sedikit keacakan akan bekerja lebih baik

    • Intuisi utamanya, setidaknya bagi saya, adalah jika kita membagi objek menjadi tumpukan potongan-potongan yang sangat kecil dan membuat n cara untuk mengurutkan tumpukan itu, objek-objek yang mirip akan memiliki potongan yang sama muncul di paling atas pada banyak pengurutan
      Tambahkan banding dan sedikit probabilitas, maka kita bisa mengaproksimasi Jaccard similarity pada dataset raksasa dengan cara yang murah dan sangat mudah diparalelkan

  • Jika dilihat sebagai teknik clustering dokumen atau deduplikasi dataset, bagaimana kualitas dan kinerja pendekatan “melemparkan machine learning ke masalah ini” dibandingkan dengan pendekatan algoritma diskret yang lebih sederhana seperti ini?
    Misalnya, membuat embedding vektor dokumen dengan encoder LLM pralatih, memasukkan vektor itu ke vector DB, lalu melakukan clustering dengan k-means

    • LLM hanyalah salah satu dari banyak cara untuk menghasilkan embedding
      Untuk melakukan k-means, Anda tetap harus memilih fungsi jarak seperti Jaccard, dan k-means mungkin tidak ideal untuk near-duplicate
      MinHash juga bisa dipakai sebagai praproses untuk k-means agar lebih cepat
      Saya tidak melihat vector DB akan banyak membantu
      Jika Anda memiliki ratusan juta dokumen, itu bisa dipakai untuk mempercepat lookup sketsa MinHash, tetapi secara umum kemungkinan itu pilihan yang berlebihan
    • Saya pernah melihat pendekatan seperti itu bekerja lebih baik daripada LSH
      Setiap kali meng-embedding dokumen, sebelum menambahkannya kita mencari approximate nearest neighbor, sehingga seperti MinHash, kompleksitasnya O(N)
      Indeks vektor seperti HNSW dan PQ memiliki kompromi performa/kualitas yang lebih baik daripada SimHash LSH, yang merupakan padanan MinHash untuk cosine distance
      Kualitasnya bergantung pada bagaimana near-duplicate didefinisikan dan model embedding apa yang digunakan
      Model modern bekerja dengan baik, dan jika ada data berlabel, fine-tuning dapat membuatnya lebih baik
      Kekurangan utamanya adalah biaya tambahan untuk meng-embedding semua dokumen, terutama berat untuk dokumen panjang
      Namun berkat model yang lebih kecil, optimisasi yang lebih baik, dan hardware yang lebih cepat, biaya ini turun sangat cepat