1. 硕士论文（过滤最近邻搜索）
面向场景
- 用户的查询需要限定在数据集的某个子集上时，例如在特定时间范围内的图像或者满足某些特定属性的产品
问题提出
- 在许多向量数据库产品中，过滤器被视为一个黑盒，它以完全无法预测的方式在构建索引时随意包含或排除点
- 元数据可以成为提高过滤近邻搜索（ANNS）性能的强大工具，它有助于构建预见过滤查询需求的索引，并在回答这些查询时保持稳健的性能
- 在可能发生的过滤很多很复杂的情况下，提前为每种可能的过滤建立相关点的索引是不切实际的
- 我们不禁会问：当存在许多可能的过滤条件时，我们能否构建整合了元数据的索引，有效地回答过滤查询？
核心思想
- 构建索引时就考虑到过滤条件（即当数据集的大部分不被视为有效的邻居时，如何构造一个依然有效的索引）
- 局部索引代替全局索引
两种方法
- 布尔过滤（属性为布尔标签元数据）
- 窗口过滤（属性为一个取值范围）
1.1 标签过滤
示例
- 假设一个图片数据库，其中每张图片都有如下布尔标签元数据：“有人物”、“室外”、“黑白”。用户可以查询所有“有人物”且“室外”的图片
目标
- 指定一个或多个标签，在满足这些标签的数据点中查找最近邻。需要有效组织数据和索引，以快速响应这种带过滤条件的查询
索引构建（倒排索引）
- 从标签出发，列出含有该标签的所有数据（将标签映射到包含该标签的所有数据上）
-
小标签
- 带有该标签的数据少（稀疏）
- 与小标签关联的数据点直接使用有序数组进行索引，最小化空间占用
-
大标签
- 大标签的索引由三部分组成：IVF、Vamana search graph、bit vector
- 对大标签建立从标签到点的倒排索引，包含标签的点使用Vamana search graph维护
- 对于特大标签，构建位向量，其中每个数据点在向量中的对应位置如果为1，则表示该数据点包含此标签；如果为0，则表示不包含
- 如果查询时发现两个大标签的交集也大，这种情况下，对他们的交集使用Vamana graph构建索引，用来加速查询
查询过程
- 查询方法由查询形式（单标签 or AND）以及标签大小决定
-
单标签
在查询的过滤器仅依赖于单个标签的情况下，查询简单地变为对该标签索引的k-NN查询
- 小标签：对索引数组进行穷举搜索
- 大标签：在Vamana graph上进行beam search（波束搜索），会得到一个K-NN索引
-
AND复合标签
-
一个标签特别大（有bit vector）一个标签特别小：
进行BitVector Join，将大标签的位向量与小标签的数据点索引进行AND操作（位运算中的“与”操作），快速得到同时满足大标签和小标签条件的数据点集合，然后在集合上进行穷举搜索
-
两个大集合，交集预构建了Vamana graph：
直接在预先构建的搜索图上进行beam search
-
其他情况
各标签分别选出候选者进行join，在结果上进行穷举搜索
- 小标签候选者：该标签的所有数据点
- 大标签候选者：离查询向量最近的标签中的点，选取多少点由参数决定（思想：认为真正离查询向量近的点在大标签中离查询向量也近）
-
2. 硕士论文（过滤最近邻搜索）
面向场景
- 用户的查询需要限定在数据集的某个子集上时，例如在特定时间范围内的图像或者满足某些特定属性的产品
问题提出
- 在许多向量数据库产品中，过滤器被视为一个黑盒，它以完全无法预测的方式在构建索引时随意包含或排除点
- 元数据可以成为提高过滤近邻搜索（ANNS）性能的强大工具，它有助于构建预见过滤查询需求的索引，并在回答这些查询时保持稳健的性能
- 在可能发生的过滤很多很复杂的情况下，提前为每种可能的过滤建立相关点的索引是不切实际的
- 我们不禁会问：当存在许多可能的过滤条件时，我们能否构建整合了元数据的索引，有效地回答过滤查询？
核心思想
- 构建索引时就考虑到过滤条件（即当数据集的大部分不被视为有效的邻居时，如何构造一个依然有效的索引）
- 局部索引代替全局索引
两种方法
- 布尔过滤（属性为布尔标签元数据）
- 窗口过滤（属性为一个取值范围）
2.1 标签过滤
示例
- 假设一个图片数据库，其中每张图片都有如下布尔标签元数据：“有人物”、“室外”、“黑白”。用户可以查询所有“有人物”且“室外”的图片
目标
- 指定一个或多个标签，在满足这些标签的数据点中查找最近邻。需要有效组织数据和索引，以快速响应这种带过滤条件的查询
索引构建（倒排索引）
- 从标签出发，列出含有该标签的所有数据（将标签映射到包含该标签的所有数据上）
-
小标签
- 带有该标签的数据少（稀疏）
- 与小标签关联的数据点直接使用有序数组进行索引，最小化空间占用
-
大标签
- 大标签的索引由三部分组成：IVF、Vamana search graph、bit vector
- 对大标签建立从标签到点的倒排索引，包含标签的点使用Vamana search graph维护
- 对于特大标签，构建位向量，其中每个数据点在向量中的对应位置如果为1，则表示该数据点包含此标签；如果为0，则表示不包含
- 如果查询时发现两个大标签的交集也大，这种情况下，对他们的交集使用Vamana graph构建索引，用来加速查询
查询过程
- 查询方法由查询形式（单标签 or AND）以及标签大小决定
-
单标签
在查询的过滤器仅依赖于单个标签的情况下，查询简单地变为对该标签索引的k-NN查询
- 小标签：对索引数组进行穷举搜索
- 大标签：在Vamana graph上进行beam search（波束搜索），会得到一个K-NN索引
-
AND复合标签
-
一个标签特别大（有bit vector）一个标签特别小：
进行BitVector Join，将大标签的位向量与小标签的数据点索引进行AND操作（位运算中的“与”操作），快速得到同时满足大标签和小标签条件的数据点集合，然后在集合上进行穷举搜索
-
两个大集合，交集预构建了Vamana graph：
直接在预先构建的搜索图上进行beam search
-
其他情况
各标签分别选出候选者进行join，在结果上进行穷举搜索
- 小标签候选者：该标签的所有数据点
- 大标签候选者：离查询向量最近的标签中的点，选取多少点由参数决定（思想：认为真正离查询向量近的点在大标签中离查询向量也近）
-
回复