Current condition (opensource)

Built by Rust

• qdrant
• cozo

• pgvecto.rs

  Built by Python

• Weaviate

• Milvus

• Lancedb

• Marqo

  What is indexing in vector database?

  Index是優化數據庫檢索的方法。Index是數據庫表中一個或多個row的值存儲的數據結構，可以快速訪問特定信息。類似於書籍的目錄。常見的index類型如B-tree、Hash、Spatial等等

向量數據庫中的Index構建是一個覆雜的過程，涉及到數據預處理、降維、選擇合適的Index結構和算法，以及持續的維護和優化。正確的Index策略取決於具體應用場景、數據特性以及性能要求。

算法相關

向量間的距離

• 歐幾里得距離（Euclidean Distance），兩個點之間的直線距離
• 餘弦相似度（Cosine Similarity），衡量兩個向量的「方向」的相似度
• 點積（Dot Product），兩個向量對應元素乘積的和。它的結果取決於向量的大小和它們之間的角度
• 曼哈頓距離（Manhattan Distance），兩個點在座標系中的絕對週距離和
• 傑卡德相似度（Jaccard Similarity），通常用於比較樣本集合的相似度和多樣性
• 漢明距離（Hamming Distance），對於兩個向量，它計算在相同位置上不同值的數量（？
• 皮爾森相關係數（Pearson Correlation Coefficient），衡量兩個向量間的線性相關程度

搜索相關

• k最近鄰
  • KNN，是最簡單直觀的算法，可以結合
• 局部敏感哈希
  • LSH是一種哈希技術，用於大規模數據集的近似最近鄰搜索
  • 它將向量映射到哈希表中，以便相似的向量具有更高的概率映射到同一個“桶”中。
• 樹結構搜索算法
  • 如KD樹（k-dimension tree）和球樹（Ball Tree）等，這些算法通過構建樹狀結構來組織數據，從而加快搜索速度。
  • 這些方法在高維空間中的性能可能會下降。
• 近似最近鄰搜索（Approximate Nearest Neighbor, ANN）
  • 如Annoy（Approximate Nearest Neighbors Oh Yeah）和FAISS（Facebook AI Similarity Search）等，這些是專門為近似最近鄰搜索設計的高效算法和庫
  • 它們在保持高搜索速度的同時，犧牲了一定的精確度。
• 向量量化（Vector Quantization）
  • 這是一種通過將向量空間分割成有限數量的“簇”，並對這些簇進行編碼的方法。
  • 這種方法可以用於壓縮和快速搜索，特別是在結合了像FAISS這樣的算法時。
• 圖搜索算法
  • 如HNSW（Hierarchical Navigable Small World）等，這些是基於圖的算法，有效地組織數據，以實現快速搜索。

Ref

Repo

• https://www.benchcouncil.org/evaluation/opencs/cn/annual.html

• https://stablecog.com/blog/the-best-vector-database-for-stablecogs-semantic-search

  算法

• https://www.pinecone.io/learn/what-is-similarity-search/

ChangeLog

• 20231123-init

• Next Post →