SimilaritySearch.jl

Kesamaan CEART.JL

KesamaanSearch.jl adalah perpustakaan untuk pencarian tetangga terdekat. Secara khusus, ini berisi implementasi untuk SearchGraph, indeks pencarian yang cepat dan fleksibel menggunakan fungsi metrik apa pun. Ini dirancang untuk mendukung multithreading di sebagian besar fungsinya dan strukturnya.

Paket memberikan indeks berikut:

• ParallelExhaustiveSearch : Indeks pencarian kekuatan brute di mana setiap kueri diselesaikan menggunakan semua utas yang tersedia.
• ExhaustiveSearch : Indeks pencarian brute force, setiap kueri dipecahkan menggunakan satu utas.
• SearchGraph : Perkiraan indeks pencarian dengan konstruksi paralel.

Set fungsi utama adalah:

• search : Memecahkan satu kueri.
• searchbatch : Memecahkan satu set kueri.
• allknn : menghitung $ k $ tetangga terdekat untuk semua elemen dalam indeks.
• neardup : Menghapus duplikat dekat dari dataset metrik.
• closestpair : Menghitung pasangan terdekat dalam dataset metrik.

Definisi yang tepat dari fungsi -fungsi ini dan serangkaian fungsi dan struktur lengkap dapat ditemukan dalam dokumentasi.

Ekosistem Pencarian Kesamaan di Julia

Saat ini, ada beberapa paket yang didedikasikan untuk pencarian tetangga terdekat, misalnya kami memiliki NearestNeighbors.jl , RegionTrees.jl , dan JuliaNeighbors menerapkan struktur pencarian seperti pohon kD, pohon bola, quadtrees, octrees, pohon bk, pohon VP dan struktur multidimensi dan metrik lainnya. Struktur ini bekerja dengan baik untuk data dimensi rendah karena dirancang untuk menyelesaikan kueri kesamaan yang tepat.

Ada beberapa paket yang melakukan perkiraan pencarian kesamaan, seperti Rayuela.jl menggunakan skema kuantisasi produk, pembungkus untuk perpustakaan FAISS Faiss.jl . Perpustakaan FAISS menyediakan implementasi kinerja tinggi dari skema kuantisasi produk dan skema hashing yang peka terhadap lokalitas, bersama dengan implementasi kekuatan industri dari indeks HNSW . The NearestNeighborDescent.jl mengimplementasikan algoritma pencarian di belakang pynndescent .

Paket SimilaritySearch.jl mencoba untuk memperkaya ekosistem dengan struktur pencarian dan algoritma yang dirancang untuk memanfaatkan sistem multithreading dan fitur autotuning unik yang menyederhanakan penggunaannya untuk praktisi. Fitur -fitur ini diterapkan secara ringkas dan efisien karena dinamisme dan kinerja bahasa pemrograman Julia. Mengenai karakteristik kinerja, waktu konstruksi sangat berkurang dibandingkan dengan pendekatan serupa tanpa mengurangi kinerja pencarian atau kualitas hasil.

Menginstal Kesamaan Penelitian

Anda dapat menginstal paket sebagai berikut

] add SimilaritySearch . jl

Anda juga dapat menjalankan set tes sebagai berikut

] test SimilaritySearch

Menggunakan perpustakaan

Silakan lihat contoh. Anda akan menemukan daftar buku catatan Jupyter dan Pluto, dan beberapa skrip yang mencontohkan penggunaannya.

Menyumbang

Kontribusi dipersilakan. Harap isi permintaan tarik untuk kontribusi mendokumentasikan dan implementasi. Untuk masalah, silakan isi masalah dengan informasi yang diperlukan (lihat di bawah.) Jika Anda sudah memiliki solusi, harap juga berikan permintaan tarik.

Masalah

Laporkan masalah dalam paket yang memberikan contoh yang dapat direproduksi minimal. Jika masalah ini tergantung pada data, jangan lupa untuk memberikan data yang diperlukan untuk mereproduksi.

Keterbatasan SearchGraph

Struktur pencarian utama, SearchGraph, adalah grafik dengan beberapa karakteristik, banyak dari mereka yang diinduksi oleh dataset yang diindeks. Beberapa batasan yang diketahui terkait dengan karakteristik ini. Misalnya:

• Jarak metrik bekerja dengan baik; Di sisi lain, semi-metrik harus bekerja, tetapi kemampuan perutean belum dikarakterisasi.
• Bahkan ketika berkinerja cukup baik dibandingkan dengan alternatif, metrik diskrit seperti jarak levenshtein dan lainnya yang mengambil beberapa nilai yang mungkin juga dapat memperoleh kinerja rendah.
• Hal serupa akan terjadi ketika ada banyak duplikat dekat (elemen yang cukup dekat). Dalam hal ini, perlu untuk menghilangkan duplikat dekat dan memasukkannya ke dalam tas yang terkait dengan beberapa benda dekatnya.
• Kumpulan data dimensi yang sangat tinggi akan menghasilkan distribusi ekor panjang dari jumlah tepi per titik. Dalam kasus yang ekstrem, Anda harus memangkas lingkungan besar dan memperkaya jalur tepi tunggal.

Tentang struktur dan algoritma

Naskah berikut ini menjelaskan dan membandingkan indeks SearchGraph (versi paket 0.6 ):

 @article{tellezscalable,
  title={A scalable solution to the nearest neighbor search problem through local-search methods on neighbor graphs},
  author={Tellez, Eric S and Ruiz, Guillermo and Chavez, Edgar and Graff, Mario},
  journal={Pattern Analysis and Applications},
  pages={1--15},
  publisher={Springer}
}

Algoritma saat ini (versi 0.8 dan 0.9 ) dijelaskan dan dibandingkan dalam naskah berikut:

@misc{tellez2022similarity,
      title={Similarity search on neighbor's graphs with automatic Pareto optimal performance and minimum expected quality setups based on hyperparameter optimization}, 
      author={Eric S. Tellez and Guillermo Ruiz},
      year={2022},
      eprint={2201.07917},
      archivePrefix={arXiv},
      primaryClass={cs.IR}
}

Paket ini juga dijelaskan dalam kertas Joss:

Eric S. Tellez dan Guillermo Ruiz. SimilaritySearch.jl : Indeks tetangga terdekat yang diandalkan untuk Julia . Jurnal Perangkat Lunak Open Source https://doi.org/10.21105/joss.04442.

Tentang seri v0.9.x

Algoritma versi ini sama dengan v0.8 tetapi break API kompatibilitas:

• Sekarang, menggunakan paket Polyester untuk menangani multithreading, bukan utas.@Threads
• Metode multithreading diaktifkan secara default jika proses dimulai dengan beberapa utas; di v0.8 sebaliknya
• allknn sekarang mempertahankan referensi diri untuk menyederhanakan algoritma dan meningkatkan efisiensi ( allknn dalam v0.8 menghapus referensi diri secara otomatis)

Yang lain:

• Menambahkan fungsi dokumen dan tolok ukur
• Menambahkan metode pemangkasan grafik SearchGraph
• Menghapus fungsi timedsearchbatch

Tentang seri v0.10.x

Mudah untuk menyesuaikan struktur SearchGraph dengan beban kerja dan aplikasi yang berbeda. Misalnya,

• Lebih banyak kontrol untuk parameter konstruksi
• Memuat dan menghemat
• Refactors mencari API untuk konsisten di seluruh struct

Silakan merujuk ke https://github.com/sadit/similaritysearchdemos dan https://github.com/sadit/similaritysearch.jl/blob/main/test/testsearchgraph.jl untuk contoh kerja.

Tentang seri v0.11

Ini memperkenalkan refactoring besar. Secara khusus, itu membuat penggunaan objek konteks secara eksplisit untuk sebagian besar fungsi. Ini juga memperkenalkan prosedur penebangan sederhana. Namun, kami mempertahankan kompatibilitas dalam banyak fungsi publik menggunakan penggunaan implisit objek konteks default.