概述

Faiss 支持对二进制向量进行索引（使用汉明距离），包括 IndexBinaryFlat、IndexBinaryIVF、IndexBinaryHNSW 以及 IndexBinaryHash / IndexBinaryMultiHash（都继承自 IndexBinary）。

这些索引会将向量以字节（byte）数组的形式存储，因此，长度为 $d$ 的二进制向量在内存中只占用 $d / 8$ 字节。请注意，目前仅支持长度为8的倍数的向量。如果不是，可以进行补齐。

add() 和 search() 方法的输入也要求为字节数组（C++中为uint8_t，Numpy中为uint8）。返回的索引为64位整数，距离为32位整数。

从 Faiss 1.6.3 版本开始，大多数索引类型也支持 range_search（范围查询）。

二进制向量的典型使用场景

存储图片、文本等内容经过二值化编码后的特征
大规模相似性检索时，内存非常紧张且只需二值度量
需要基于汉明距离（Hamming Distance）的快速检索

提示

“汉明距离”是指两个等长二进制序列之间，不同位的数量。在本类索引中，就是衡量两个二进制向量相似度的方式。

IndexBinaryFlat

“Flat”（平面）二进制索引会做全量检索。

全量检索针对256位常用向量进行了特别优化，汉明距离计算会利用 CPU 的 popcount 指令来提高速度。

通过对查询和数据库端同时进行批处理，最大化缓存效率，减少延迟。批处理大小可用 hamming_batch_size 和 faiss::IndexBinaryFlat#query_batch_size 两个参数自定义，但在大多数场景下默认值已较为理想。

下面例子展示了二进制数据的添加与查询方式。

C++ 示例

#include <faiss/IndexBinaryFlat.h>

// 向量维度d，必须为8的倍数
int d = 256;

// 数据库中的向量，每个向量用 d / 8 字节表示，顺序连续存储
int nb = ...;
std::vector<uint8_t> db(nb * (d / 8));
// 初始化 db

// 待查询向量
int nq = ...;
std::vector<uint8_t> queries(nq * (d / 8));

// 初始化索引
faiss::IndexBinaryFlat index(d);

// 添加数据库向量
index.add(nb, db.data());

// 检索每个查询向量的邻近向量个数
int k = ...;

// 查询输出：距离+标签
std::vector<int32_t> distances(nq * k);
std::vector<faiss::Index::idx_t> labels(nq * k);

// 执行查询
index.search(nq, queries.data(), k, distances.data(), labels.data());

// distances[i * k + j] 是第i个查询向量到其第j个最近邻的距离（汉明距离）
// labels[i * k + j] 是对应的数据库ID

Python 示例

import faiss
import numpy as np

# 向量维度
d = 256

# 数据库向量，每个用 d // 8 字节存储，db[i]即第i个向量
nb = ...
db = np.empty((nb, d // 8), dtype='uint8')
# ... 初始化 db ...

# 查询向量
nq = ...
queries = np.empty((nq, d // 8), dtype='uint8')
# ... 初始化 queries ...

# 初始化索引
index = faiss.IndexBinaryFlat(d)

# 添加数据库向量
index.add(db)

# 检索每个查询向量的邻近向量个数
k = ...

# 执行查询
D, I = index.search(queries, k)

# D[i, j] 是第i个查询向量到第j个最近邻的距离（汉明距离）
# I[i, j] 是对应的数据库ID

IndexBinaryIVF

“IVF”模式（Inverse Vector File，逆向向量文件）通过将向量聚类加速检索。聚类时，会用一个二进制量化器（通常为flat索引）进行二值聚类。它与浮点向量的 IndexIVFFlat 类似。

适用场景：当数据库向量规模很大时，IVF可显著加快查询速度，同时部分降低准确率。

C++ 示例

#include <faiss/IndexBinaryIVF.h>

// 向量维度
int d = 256;

// 待索引的二进制向量
int nb = ...;
std::vector<uint8_t> db(nb * (d / 8));

// 训练量化器的向量
int nt = ...;
std::vector<uint8_t> training(nt * (d / 8));

// 查询向量
int nq = ...;
std::vector<uint8_t> queries(nq * (d / 8));

// 初始化量化器
faiss::IndexBinaryFlat quantizer(d);

// 聚类中心数
int nlist = ...;

// 初始化IVF索引
faiss::IndexBinaryIVF index(&quantizer, d, nlist);
index.nprobe = 4; // 查询时检查nprobe个簇

// 训练量化器
index.train(nt, training.data());

// 添加数据库向量
index.add(nb, db.data());

// 查询邻居数量
int k = ...;

// 输出变量
std::vector<int32_t> distances(nq * k);
std::vector<faiss::idx_t> labels(nq * k);

// 执行查询
index.search(nq, queries.data(), k, distances.data(), labels.data());

// distances[i * k + j] 是距离，labels[i * k + j] 是ID

Python 示例

import faiss

# 向量维度
d = 256

# 数据库二进制向量 db[i] 为第i个
db = ...

# 训练量化器用的向量
training = ...

# 查询向量
queries = ...

# 初始化量化器
quantizer = faiss.IndexBinaryFlat(d)

# 聚类中心数
nlist = ...

# 初始化IVF索引
index = faiss.IndexBinaryIVF(quantizer, d, nlist)
index.nprobe = 4 # 查询时访问nprobe个簇

# 训练量化器
index.train(training)

# 添加数据库向量
index.add(db)

# 查询邻居数
k = ...

# 执行查询
D, I = index.search(queries, k)

# D[i, j] 是距离，I[i, j] 是ID

IndexBinaryHNSW（二进制 HNSW 索引）

该方法与浮点向量的 HNSW（分层小世界图，Hierarchical Navigable Small World）实现一致。

示例见：TestHNSW

IndexBinaryHash 与 IndexBinaryMultiHash

支持自 Faiss 1.6.3 版本及以上。

IndexBinaryHash

这种传统方法是从二进制向量中抽取hash值（哈希摘要），根据哈希将数据分组。检索时，会访问与查询向量哈希值在 nflip 汉明半径范围内的所有桶（buckets）。

哈希值取自向量的前 $b$ 位。检索时，访问的桶数为：

1 + b + b \times (b - 1) / 2 + \cdots + \mathrm{comb}(b, nflip)

IndexBinaryMultiHash

这是上述方法的扩展，相关论文：“Fast Search in Hamming Space with Multi-Index Hashing”（Norouzi 等，CVPR'12）。它通过把向量拆分为多个子段，每个子段做哈希表（hash tables）实现。例如用 $nhash$ 个哈希表，分别用向量的 $0:b$ ， $b:2b$ ，...， $(nhash-1) \times b : nhash \times b$ 位。这种方法有时也称为多表 LSH（局部敏感哈希，Locality Sensitive Hashing）。

二进制哈希与IVF的对比请参考：Binary hashing index benchmark

使用 index factory 简化索引创建

使用 faiss::index_binary_factory() 可以用更简洁的方式声明二进制索引。对于需要量化器的 IndexBinaryIVF 特别方便。

如下是示例代码：

C++ 简写方式

不用 factory 的写法：

// 初始化量化器
faiss::IndexBinaryFlat quantizer(d);

// 聚类中心数
int nlist = 32;

// 创建IVF索引
faiss::IndexBinaryIVF index(&quantizer, d, nlist);
index.nprobe = 4;

使用 factory 可简化为：

#include <faiss/AutoTune.h>

// 使用 index_binary_factory 构建
faiss::IndexBinaryIVF *index = dynamic_cast<faiss::IndexBinaryIVF *>(faiss::index_binary_factory(d, "BIVF32"));
index->nprobe = 4;

Python 简写方式

不用 factory 的写法：

quantizer = faiss.IndexBinaryFlat(d)
nlist = 32
index = faiss.IndexBinaryIVF(quantizer, d, nlist)
index.nprobe = 4

使用 factory 可简化为：

index = faiss.index_binary_factory(d, "BIVF32")
index.nprobe = 4

可用的 `index_binary_factory` 字符串列表

名称	类名	每向量字节	说明
BFlat	`IndexBinaryFlat`	d/8	简单平面索引
BIVF1024	`IndexBinaryIVF`	d/8	IVF（1024聚类中心，flat量化器）
BHNSW16	`IndexBinaryHNSW`	d/8 + 16 * 2 * 4	HNSW，分支因子M=16
BIVF1024_HNSW16	`IndexBinaryIVF`	d/8	1024聚类中心，HNSW(M=16)做量化器
BHash32	`IndexBinaryHash`	d/8	使用32位前缀的二进制哈希
BHash4x32	`IndexBinaryMultiHash`	4*64/8	多哈希表，每个32位

备注

每向量字节数为大致估算。实际还因std::vector分配、粗量化器（IVF）、HNSW树额外占用内存。

二进制码的非对称检索（Asymmetric search）

非对称检索指数据库向量已二值化压缩而查询向量未压缩。目前二进制索引不直接支持这种操作。

手工实现可参考脚本：demo_asymmetric_binary.ipynb

二进制向量的典型使用场景​

IndexBinaryFlat​

IndexBinaryIVF​

IndexBinaryHNSW（二进制 HNSW 索引）​

IndexBinaryHash 与 IndexBinaryMultiHash​

IndexBinaryHash​

IndexBinaryMultiHash​