Skip to content

Latest commit

 

History

History
209 lines (168 loc) · 8 KB

1-向量搜索引擎.md

File metadata and controls

209 lines (168 loc) · 8 KB

向量搜索引擎

介绍

人工智能算法可以对各种数据进行分析，从而得到各种数据的特征向量，这些特征向量可以用来表示各种数据，比如图像、视频、文本等。在实际应用中，我们经常需要对这些数据进行检索，比如在图像搜索引擎中，我们输入一张图片，搜索引擎会返回与这张图片相似的图片。这种基于向量的检索技术，被称为向量搜索引擎。

下面的资料介绍了比较流行的向量搜索引擎：

根据是否开源、文档是否完善、社区活跃度等因素列出了可以根据项目实现参考的向量搜索引擎：

  • Faiss 是 Facebook AI Research 开源的一款向量搜索库，基于 C++ 实现，GitHub 20k star。
    • 优点：多个向量搜索引擎的基础库，支持多种向量索引算法，代码库更新仍然很活跃
    • 缺点：不支持分布式搜索
  • Vearch 是京东开源的向量搜索框架，基于 Go 语言实现，GitHub 1.5k star
    • 优点：基于 Faiss 开发，支持分布式搜索
    • 缺点：代码库已经 1 年没有更新，文档不完善
  • Milvus 基于 Go 语言实现
    • 优点：对比 Vearch，在社区活跃度、支持度上具有更明显的优势，也有很多公司采用 Milvus 作为底层引擎

各个搜索引擎基本上都参考了 Faiss 实现，或者直接使用 Faiss 作为基础库，所以我们可以直接详细介绍 Faiss，以及 Faiss 的一些使用方法和性能评测。

Faiss

Install

详细安装文档和编译选项可以参考官方文档 INSTALL.md，我选择了以下两种环境从源码编译安装：

  • Windows 11 for Sub Linux (x86)
  • M1 MacBook Air (arm)

Requirements:

  • CMake
  • OpenMP
  • BLAS
  • swig

这里禁用了 GPU 构建索引编译

cmake -DFAISS_ENABLE_GPU=OFF -B build .

Basic example

源码的 demos/ 和 tutorial/ 目录包含了一些简单的使用样例。Faiss 包含非常多的索引类型，首先尝试最简单的 IndexFlatL2，基于 L2 距离进行暴力搜索。

IndexFlatL2

// tutorial/cpp/1-Flat.cpp
// make -C build 1-Flat
#include <cstdio>
#include <cstdlib>
#include <random>
#include <chrono>
#include <iostream>

#include <faiss/IndexFlat.h>

// 64-bit int
using idx_t = faiss::idx_t;
using namespace std::chrono;


int main() {
    int d = 128;      // dimension
    int nb = 1000000; // database size
    int nq = 1;  // nb of queries

    std::mt19937 rng;
    std::uniform_real_distribution<> distrib;

    float* xb = new float[d * nb];
    float* xq = new float[d * nq];

    auto start = high_resolution_clock::now();
    for (int i = 0; i < nb; i++) {
        for (int j = 0; j < d; j++)
            xb[d * i + j] = distrib(rng);
        xb[d * i] += i / 1000.;
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(stop - start);
    std::cout << duration.count() << std::endl;

    for (int i = 0; i < nq; i++) {
        for (int j = 0; j < d; j++)
            xq[d * i + j] = distrib(rng);
        xq[d * i] += i / 1000.;
    }

    faiss::IndexFlatL2 index(d); // call constructor
    printf("is_trained = %s\n", index.is_trained ? "true" : "false");
    index.add(nb, xb); // add vectors to the index
    printf("ntotal = %zd\n", index.ntotal);

    int k = 4;

    { // sanity check: search 5 first vectors of xb
        idx_t* I = new idx_t[k * 5];
        float* D = new float[k * 5];

        index.search(5, xb, k, D, I);

        // print results
        printf("I=\n");
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < k; j++)
                printf("%5zd ", I[i * k + j]);
            printf("\n");
        }

        printf("D=\n");
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < k; j++)
                printf("%7g ", D[i * k + j]);
            printf("\n");
        }

        delete[] I;
        delete[] D;
    }

    { // search xq
        idx_t* I = new idx_t[k * nq];
        float* D = new float[k * nq];

        auto start = high_resolution_clock::now();
        index.search(nq, xq, k, D, I);
        auto stop = high_resolution_clock::now();
        auto duration = duration_cast<milliseconds>(stop - start);
        std::cout << duration.count() << std::endl;

        // print results
        printf("I (5 first results)=\n");
        for (int i = 0; i < 1; i++) {
            for (int j = 0; j < k; j++)
                printf("%5zd ", I[i * k + j]);
            printf("\n");
        }

        // printf("I (5 first results)=\n");
        // for (int i = 0; i < 5; i++) {
        //     for (int j = 0; j < k; j++)
        //         printf("%5zd ", I[i * k + j]);
        //     printf("\n");
        // }

        // printf("I (5 last results)=\n");
        // for (int i = nq - 5; i < nq; i++) {
        //     for (int j = 0; j < k; j++)
        //         printf("%5zd ", I[i * k + j]);
        //     printf("\n");
        // }

        delete[] I;
        delete[] D;
    }

    delete[] xb;
    delete[] xq;

    return 0;
}

分别修改 d，nb，q 的值编译运行程序，结果如下：

benchmark

特征库大小 待查询的特征数量 特征维度 内存消耗 运行时间
5k 1 256 - 3ms
5k 1 512 - 7ms
5k 1 1024 - 14ms
5k 10 256 - 4ms
5k 10 512 - 10ms
5k 10 1024 - 17ms
1w 1 256 - 7ms
1w 1 512 - 14ms
1w 1 1024 - 28ms
1w 10 256 - 10ms
1w 10 512 - 17ms
1w 10 1024 - 33ms
10w 1 64 - 18ms
10w 1 128 - 36ms
10w 1 256 - 71ms
10w 1 512 169M 154ms
10w 1 1024 410M 286ms
10w 10 64 - 24ms
10w 10 128 - 41ms
10w 10 256 - 81ms
10w 10 512 141M 161ms
10w 10 1024 372M 320ms
50w 1 64 - 90ms
50w 1 128 - 180ms
50w 1 256 - 359ms
50w 10 64 - 106ms
50w 10 128 - 204ms
50w 10 256 - 404ms
50w 1 512 2G 823ms
50w 1 1024 4G 1423ms
100w 1 64 - 183ms
100w 1 128 1G 361ms
100w 1 256 2G 787ms
100w 10 64 206M 213ms
100w 10 128 1G 515ms
100w 10 256 2G 806ms