halo2 vectordb
1.0.0
コミットされたベクトルデータベースにおける検証可能なベクトルの類似性クエリ。
このプロジェクトは、ゼロ知識証明を使用して、検証可能なベクトルデータベースの概念実証を取得することを目的としています。 HALO2-LIBを使用して固定点の算術を可能にする素晴らしいZkfixedPointChipを多用します。
錆をインストールする必要があります：
curl --proto ' =https ' --tlsv1.2 -sSf https://sh.rustup.rs | sh次に、このリポジトリをクローンして、その中のチップを使用できます。
git clone https://github.com/erhant/halo2-vectordb.git
cd halo2-vectordbHALO2の距離メトリック用に1つは2つのチップを実装し、もう1つは基本的なベクトルデータベース操作に実装します。
DistanceChip DistanceChip 、等しい長さの2つのベクトルで動作する距離メトリックを提供します。ベクトル要素は、 FixedPointChipで量子化されると予想されます。次の距離メトリックが実装されています。
euclidean_distance 、2つのベクトル間のユークリッド距離を計算します。manhattan_distance 、2つのベクトル間のマンハッタン距離を計算します。hamming_distance 、2つのベクトル間の1つのマイナスハミングの類似性を計算します。cosine_distance 、2つのベクトル間の1つのマイナスコサインの類似性を計算します。VectorDBChip VectorDBChip 、ベクターのセットで基本的なベクトルデータベース機能を実装します。 DistanceChipと同様に、量子化された値を超えて動作するには、 FixedPointChipが必要です。次の機能を公開します。
nearest_vector 、一連のベクトルとクエリベクトルを取得し、特定の距離関数にクエリWRTに最も類似したベクトルを見つけます。また、後のステップで使用できるインジケータ（つまり、結果ベクトルのインデックスを示す1ホットエンコードベクトル）を返します。merkle_commitment一連のベクトルを取り、ポセイドンのハッシュを備えたマークルツリーを使用してそれらにコミットします。指定されたセットに2つの力の多くの要素が含まれていない場合、残りの葉にゼロをパッドします。私たちのシナリオでは、ベクトル全体のみが必要であるか、まったく必要ありません。そのため、ベクトル内の要素にコミットすることは気にしません。そのため、最初にベクトル全体をハッシュし、次にそのハッシュをリーフノードとして扱います。kmeans 、一連のベクトル、 K定数を採取して重心の数を決定し、 I定数は反復回数を決定します。 K-meansは通常、重心が更新されないときに終了する反復アルゴリズムです。ただし、このようなコントロールフローはZK回路では不可能です。したがって、 Iパラメーターは固定数の反復を決定します。また、ベクトルを量子化および非定常するための単純なユーティリティ関数であるFixedPointChipの特性FixedPointVectorInstructionsとその実装もあります。
実証的なテストスイートは、 demo_testで見つけることができます：
K Centroids＆Clustersになります。K Centroids＆ClustersとK+2 Merkle Rootsを実現します。f64錆の実装ほど正確ではない固定点の精度に注意してください。次のいずれかで例を実行します。
# 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 。 Corpus-Texmexでダウンロードできます。このデータセット128次元ベクトル。テストフォルダー内で、 commonモジュールは2つの機能を公開してこれらのベクトルを読み取ります。
read_vectors_from_diskパスとディメンション（この場合は128）を取り、データセットから.fvecファイルを読み取り、 f32値の単一のベクトルを返します。この単一のベクトルは、一緒に構成されたすべてのベクトル要素で構成されています。select_from_vectors 、その単一のベクトルとインデックスのリストを取得し、選択したベクトルのみを返します。 
