SimilaritySearch.jl

ความคล้ายคลึงกัน search.jl

LamentSearch.jl เป็นห้องสมุดสำหรับการค้นหาเพื่อนบ้านที่ใกล้ที่สุด โดยเฉพาะอย่างยิ่งมันมีการใช้งานสำหรับ SearchGraph, เป็นดัชนีการค้นหาที่รวดเร็วและยืดหยุ่นโดยใช้ฟังก์ชั่นการวัดใด ๆ มันถูกออกแบบมาเพื่อรองรับมัลติเธรดในฟังก์ชั่นและโครงสร้างส่วนใหญ่

แพ็คเกจมีดัชนีต่อไปนี้:

• ParallelExhaustiveSearch : ดัชนีการค้นหาแรงเดรัจฉานที่แต่ละแบบสอบถามได้รับการแก้ไขโดยใช้เธรดที่มีอยู่ทั้งหมด
• ExhaustiveSearch : ดัชนีการค้นหาแรงเดรัจฉานแต่ละแบบสอบถามได้รับการแก้ไขโดยใช้เธรดเดียว
• SearchGraph : ดัชนีการค้นหาโดยประมาณพร้อมการก่อสร้างแบบขนาน

ชุดฟังก์ชันหลักคือ:

• search : แก้คำถามเดียว
• searchbatch : แก้ชุดการสืบค้น
• allknn : คำนวณไฟล์ $ k $ เพื่อนบ้านที่ใกล้ที่สุดสำหรับองค์ประกอบทั้งหมดในดัชนี
• neardup : ลบข้อมูลใกล้ชิดจากชุดข้อมูลเมตริก
• closestpair : คำนวณคู่ที่ใกล้ที่สุดในชุดข้อมูลเมตริก

คำจำกัดความที่แม่นยำของฟังก์ชั่นเหล่านี้และชุดฟังก์ชันและโครงสร้างที่สมบูรณ์สามารถพบได้ในเอกสารประกอบ

ระบบนิเวศ การค้นหาที่คล้ายคลึงกันในจูเลีย

ขณะนี้มีแพ็คเกจหลายอย่างที่อุทิศให้กับการค้นหาเพื่อนบ้านที่ใกล้ที่สุดเช่นเรามี NearestNeighbors.jl กับ neumnneighbors.jl, RegionTrees.jl และ JuliaNeighbors ใช้โครงสร้างการค้นหาเช่น KD-Trees, ต้นบอล, Quadtrees, Octrees, BK-Trees, VP-Tree และโครงสร้างหลายมิติและ metric โครงสร้างเหล่านี้ทำงานได้ค่อนข้างดีสำหรับข้อมูลมิติต่ำเนื่องจากได้รับการออกแบบมาเพื่อแก้ปัญหาการสืบค้นความคล้ายคลึงกันที่แน่นอน

มีแพ็คเกจหลายอย่างที่ทำการค้นหาความคล้ายคลึงกันโดยประมาณเช่น Rayuela.jl โดยใช้แผนการเชิงปริมาณผลิตภัณฑ์ wrapper สำหรับห้องสมุด FAISS Faiss.jl ห้องสมุด FAISS ให้การใช้งานที่มีประสิทธิภาพสูงของแผนการเชิงปริมาณผลิตภัณฑ์และแผนการแฮชที่ไวต่อท้องถิ่นพร้อมกับการใช้งานด้านอุตสาหกรรมของดัชนี HNSW NearestNeighborDescent.jl jl ใช้อัลกอริทึมการค้นหาที่อยู่เบื้องหลัง pynndescent

แพ็คเกจ SimilaritySearch.jl พยายามที่จะเสริมสร้างระบบนิเวศด้วยโครงสร้างการค้นหาและอัลกอริธึมที่ออกแบบมาเพื่อใช้ประโยชน์จากระบบมัลติเธรดและคุณสมบัติการสร้างอัตโนมัติที่เป็นเอกลักษณ์ซึ่งทำให้การใช้งานของผู้ปฏิบัติงานง่ายขึ้น คุณสมบัติเหล่านี้มีการดำเนินการอย่างรัดกุมและมีประสิทธิภาพเนื่องจากพลวัตการเขียนโปรแกรมของ Julia การเขียนโปรแกรมและประสิทธิภาพ เกี่ยวกับลักษณะการปฏิบัติงานเวลาการก่อสร้างจะลดลงอย่างมากเมื่อเทียบกับวิธีการที่คล้ายกันโดยไม่ลดประสิทธิภาพการค้นหาหรือคุณภาพผลลัพธ์

การติดตั้งความคล้ายคลึงกัน

คุณสามารถติดตั้งแพ็คเกจดังนี้

] add SimilaritySearch . jl

นอกจากนี้คุณสามารถเรียกใช้ชุดการทดสอบได้ดังนี้

] test SimilaritySearch

ใช้ห้องสมุด

โปรดดูตัวอย่าง คุณจะพบรายการสมุดบันทึก Jupyter และ Pluto และสคริปต์บางส่วนที่เป็นตัวอย่างของการใช้งาน

มีส่วนช่วย

ยินดีต้อนรับการมีส่วนร่วม กรุณากรอกคำขอดึงสำหรับการจัดทำเอกสารและการใช้งานการมีส่วนร่วม สำหรับปัญหาโปรดกรอกข้อมูลด้วยข้อมูลที่จำเป็น (ดูด้านล่าง) หากคุณมีวิธีแก้ปัญหาอยู่แล้วโปรดจัดทำคำขอดึงด้วย

ปัญหา

รายงานปัญหาในแพ็คเกจซึ่งเป็นตัวอย่างที่ทำซ้ำได้น้อยที่สุด หากปัญหาขึ้นอยู่กับข้อมูลโปรดอย่าลืมให้ข้อมูลที่จำเป็นเพื่อทำซ้ำ

ข้อ จำกัด ของ SearchGraph

โครงสร้างการค้นหาหลักคือ SearchGraph, เป็นกราฟที่มีคุณสมบัติหลายอย่างซึ่งส่วนใหญ่เกิดจากชุดข้อมูลที่ถูกจัดทำดัชนี ข้อ จำกัด ที่ทราบบางอย่างเกี่ยวข้องกับลักษณะเหล่านี้ ตัวอย่างเช่น:

• ระยะทางการวัดทำงานได้ดี ในทางกลับกันกึ่งเมทริกควรทำงาน แต่ความสามารถในการกำหนดเส้นทางยังไม่โดดเด่น
• แม้ว่ามันจะทำงานได้ค่อนข้างดีเมื่อเทียบกับทางเลือกตัวชี้วัดที่ไม่ต่อเนื่องเช่นระยะทาง Levenshtein และอื่น ๆ ที่ใช้ค่าที่เป็นไปได้น้อยอาจได้รับการแสดงต่ำ
• สิ่งที่คล้ายกันจะเกิดขึ้นเมื่อมีการทำซ้ำจำนวนมาก (องค์ประกอบที่ ค่อนข้าง ใกล้) ในกรณีนี้มีความจำเป็นที่จะต้องลบแบบใกล้เคียงและใส่ไว้ใน ถุง ที่เกี่ยวข้องกับวัตถุใกล้ ๆ
• ชุดข้อมูลมิติที่สูงมากจะสร้างการกระจาย หางเป็นระยะยาว ของจำนวนขอบต่อจุดยอด ในกรณีที่รุนแรงคุณต้องตัดพื้นที่ใกล้เคียงขนาดใหญ่และเสริมเส้นทางเดียว

เกี่ยวกับโครงสร้างและอัลกอริทึม

ต้นฉบับต่อไปนี้อธิบายและเปรียบเทียบดัชนี SearchGraph (แพ็คเกจเวอร์ชัน 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}
}

อัลกอริทึมปัจจุบัน (เวอร์ชัน 0.8 และ 0.9 ) อธิบายและเปรียบเทียบในต้นฉบับต่อไปนี้:

@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}
}

แพ็คเกจนี้อธิบายไว้ในกระดาษ Joss:

Eric S. Tellez และ Guillermo Ruiz SimilaritySearch.jl : ดัชนีเพื่อนบ้านที่ใกล้ที่สุดสำหรับจูเลีย วารสารซอฟต์แวร์โอเพ่นซอร์ส https://doi.org/10.21105/joss.04442

ประมาณ v0.9.x ซีรีส์

อัลกอริทึมของรุ่นนี้เหมือนกับ v0.8 แต่ทำลายความเข้ากันได้ของ API:

• ตอนนี้มันใช้แพ็คเกจ Polyester เพื่อจัดการมัลติเธรดแทนเธรด@เธรด
• วิธีการแบบมัลติเธรดถูกเปิดใช้งานโดยค่าเริ่มต้นหากกระบวนการเริ่มต้นด้วยหลายเธรด ใน v0.8 เป็นสิ่งที่ตรงกันข้าม
• ตอนนี้ allknn รักษาการอ้างอิงตนเองเพื่อทำให้อัลกอริทึมง่ายขึ้นและปรับปรุงประสิทธิภาพ ( allknn ใน v0.8 ลบการอ้างอิงตนเองโดยอัตโนมัติ)

คนอื่น:

• เพิ่มฟังก์ชั่นเอกสารและมาตรฐาน
• เพิ่มวิธีการตัดกราฟ SearchGraph กราฟ
• ลบฟังก์ชัน timedsearchbatch

ประมาณ v0.10.x ซีรีส์

ทำให้ง่ายต่อการปรับโครงสร้าง SearchGraph ให้เป็นเวิร์กโหลดและแอปพลิเคชันที่แตกต่างกัน ตัวอย่างเช่น

• การควบคุมพารามิเตอร์การก่อสร้างมากขึ้น
• กำลังโหลดและบันทึก
• refactors ค้นหา API ให้สอดคล้องกันข้าม structs

โปรดดูที่ https://github.com/sadit/similaritysearchdemos และ https://github.com/sadit/similaritysearch.jl/blob/main/test/testsearchgraph.jl สำหรับตัวอย่างการทำงาน

เกี่ยวกับ V0.11 ซีรี่ส์

มันแนะนำ refactoring ที่สำคัญ โดยเฉพาะอย่างยิ่งมันทำให้การใช้วัตถุบริบทอย่างชัดเจนสำหรับฟังก์ชั่นส่วนใหญ่ นอกจากนี้ยังแนะนำขั้นตอนการบันทึกอย่างง่าย อย่างไรก็ตามเรารักษาความเข้ากันได้ในฟังก์ชั่นสาธารณะจำนวนมากโดยใช้การใช้วัตถุบริบทเริ่มต้นโดยนัย