หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ดอื่น ๆ
ดาวน์โหลด

halo2 vectordb

การสืบค้นความคล้ายคลึงกันของเวกเตอร์ที่ตรวจสอบได้ผ่านฐานข้อมูลเวกเตอร์ที่มุ่งมั่น

โครงการนี้มีจุดมุ่งหมายเพื่อให้ได้รับการพิสูจน์แนวคิดสำหรับฐานข้อมูลเวกเตอร์ที่ตรวจสอบได้โดยใช้หลักฐานที่ไม่มีความรู้ เราใช้ประโยชน์จาก ZKFixedPointChip ที่ยอดเยี่ยมอย่างหนักซึ่งช่วยให้การคำนวณทางคณิตศาสตร์คงที่ด้วย Halo2-LIB

การติดตั้ง

คุณต้องติดตั้งสนิม: 

curl --proto ' =https ' --tlsv1.2 -sSf https://sh.rustup.rs | sh

จากนั้นคุณสามารถโคลนที่เก็บนี้และใช้ชิปภายใน: 

git clone https://github.com/erhant/halo2-vectordb.git
cd halo2-vectordb

การใช้งาน

เราใช้ชิปสองตัวหนึ่งตัวสำหรับการวัดระยะทางใน Halo2 และอีกอันสำหรับการดำเนินการฐานข้อมูลเวกเตอร์พื้นฐาน

DistanceChip

DistanceChip ให้การวัดระยะทางที่ทำงานกับเวกเตอร์สองตัวที่มีความยาวเท่ากัน องค์ประกอบของเวกเตอร์คาดว่าจะได้รับการวัดปริมาณด้วย FixedPointChip ตัวชี้วัดระยะทางต่อไปนี้มีการใช้งาน:

  • euclidean_distance คำนวณระยะห่างแบบยุคลิดระหว่างเวกเตอร์สองตัว
  • manhattan_distance คำนวณระยะห่างระหว่างแมนฮัตตันระหว่างเวกเตอร์สองตัว
  • hamming_distance คำนวณหนึ่งลบ hamming ความคล้ายคลึงกันระหว่างสองเวกเตอร์
  • cosine_distance คำนวณความคล้ายคลึงกันของโคไซน์หนึ่งลบระหว่างเวกเตอร์สองตัว

VectorDBChip

VectorDBChip ใช้ฟังก์ชั่นฐานข้อมูลเวกเตอร์พื้นฐานผ่านชุดของเวกเตอร์ เช่นเดียวกับ DistanceChip นั้นต้องการให้ FixedPointChip ดำเนินการมากกว่าค่าเชิงปริมาณ มันเปิดเผยฟังก์ชั่นต่อไปนี้:

  • nearest_vector ใช้ชุดเวกเตอร์และเวกเตอร์แบบสอบถามและพบเวกเตอร์ที่คล้ายกับการสืบค้น WRT ฟังก์ชั่นระยะทางที่กำหนด นอกจากนี้ยังส่งคืนตัวบ่งชี้ (เช่นเวกเตอร์ที่เข้ารหัสหนึ่งร้อนซึ่งระบุดัชนีของเวกเตอร์ผลลัพธ์) ซึ่งอาจใช้ในขั้นตอนต่อไป
  • merkle_commitment ใช้ชุดเวกเตอร์และมุ่งมั่นที่จะใช้ต้นไม้ Merkle กับ Poseidon Hashes หากชุดที่กำหนดไม่รวมถึงพลังของสององค์ประกอบหลายอย่างมันจะเพิ่มศูนย์ไปยังใบไม้ที่เหลือ ในสถานการณ์ของเราเราต้องการเฉพาะเวกเตอร์ทั้งหมดหรือไม่มีเลยและด้วยเหตุนี้เราจึงไม่สนใจที่จะทำตามองค์ประกอบภายในเวกเตอร์ ด้วยเหตุนี้เราจึงแฮชเวกเตอร์ทั้งหมดก่อนแล้วจึงถือว่าแฮชเป็นโหนดใบไม้
  • kmeans ใช้ชุดของเวกเตอร์ค่าคงที่ K เพื่อกำหนดจำนวนเซนทรอยด์และค่าคงที่ I เพื่อกำหนดจำนวนการวนซ้ำ K-mean มักจะเป็นอัลกอริทึมซ้ำที่สิ้นสุดลงเมื่อเซนทรอยด์ไม่ได้รับการปรับปรุงอีกต่อไป อย่างไรก็ตามการไหลของการควบคุมดังกล่าวไม่สามารถทำได้ในวงจร ZK ดังนั้นพารามิเตอร์ I จะกำหนดจำนวนการวนซ้ำคงที่

นอกจากนี้เรายังมีลักษณะเฉพาะ FixedPointVectorInstructions และการใช้งานสำหรับ FixedPointChip ซึ่งเป็นฟังก์ชั่นยูทิลิตี้ที่ง่ายในการหาปริมาณและกำจัดเวกเตอร์

สาธิต

ชุดทดสอบสาธิตสามารถพบได้ที่ demo_test :

  • ก่อนอื่นเราฝึกฐานข้อมูลโดยไม่มีวงจร ZK ใด ๆ ที่เกี่ยวข้องส่งผลให้ K Centroids & Clusters
  • จากนั้นเราฝึกอบรมฐานข้อมูลอื่นด้วยวงจร Halo2 ส่งผลให้ K Centroids & Clusters พร้อมกับ K+2 Merkle Roots
  • เวกเตอร์แบบสอบถามแบบสุ่มจะถูกกำหนดให้กับฐานข้อมูลทั้งสองและผลลัพธ์จะถูกเปรียบเทียบองค์ประกอบที่ชาญฉลาดกับข้อผิดพลาดสัมพัทธ์ โปรดทราบว่าความแม่นยำของจุดคงที่ไม่ถูกต้องเท่ากับการใช้งาน f64 Rust
  • ราก Merkle ถูกนำมาเปรียบเทียบระหว่างการจัดทำดัชนีและเฟสแบบสอบถามและคาดว่าจะตรงกัน

ตัวอย่าง

เรียกใช้ตัวอย่างผ่านข้อใดข้อหนึ่งต่อไปนี้: 

 # demonstrate distance computations
LOOKUP_BITS=12 cargo run --example distances -- 
  --name distances -k 13 mock

# example merkle commitment to vectors
LOOKUP_BITS=12 cargo run --example merkle -- 
  --name merkle -k 13 mock

# exhaustively find the similar vector & commit to the database
LOOKUP_BITS=12 cargo run --example query -- 
  --name query -k 13 mock

# compute centroids
LOOKUP_BITS=15 cargo run --example kmeans -- 
  --name kmeans -k 16 mock

คุณสามารถให้อินพุตเฉพาะผ่านตัวเลือก --input <input-name>

การทดสอบ

เพื่อเรียกใช้การทดสอบ: 

cargo test

การทดสอบบางอย่างใช้ประโยชน์จากชุดข้อมูล ANN_SIFT_10K โดยJégouและคณะ ซึ่งสามารถดาวน์โหลดได้ที่ Corpus-Texmex ชุดข้อมูลนี้ 128 มิติเวกเตอร์ ภายในโฟลเดอร์การทดสอบของเราโมดูล common จะเปิดเผยฟังก์ชั่นสองฟังก์ชั่นเพื่ออ่านเวกเตอร์เหล่านี้:

  • read_vectors_from_disk ใช้เส้นทางและมิติ (128 ในกรณีนี้) และอ่านไฟล์ .fvec จากชุดข้อมูลโดยส่งคืนเวกเตอร์เดียวของค่า f32 เวกเตอร์เดียวนี้ประกอบด้วยองค์ประกอบเวกเตอร์ทั้งหมดประกอบเข้าด้วยกัน
  • select_from_vectors ใช้เวกเตอร์เดียวและรายการดัชนีและส่งคืนเวกเตอร์ที่เลือกเท่านั้น

กิตติกรรมประกาศ

  • โครงการนี้ได้รับการพัฒนาเป็นส่วนหนึ่งของโปรแกรม Axiom Open Source V2
  • โครงการนี้จะเป็นไปไม่ได้หากไม่มี ZKFixedPointChip
ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด