DSE精选文章
MiniRFANN: Range-Filtered Approximate Vector Similarity Search on Edge Devices
文章介绍
现有RFANN方法通常采用预过滤、后过滤或查询过程中联合过滤的策略。预过滤方法先根据属性范围筛选数据，再进行向量相似性搜索，适合范围较窄的查询，但当属性范围较宽时会引入大量磁盘访问；后过滤方法先在全量数据上进行ANN搜索，再剔除不满足属性条件的结果，在范围较窄时容易产生大量无效候选；而联合过滤方法虽然能够在索引遍历过程中提前剪枝，但通常依赖内存常驻索引，难以适用于手机、终端设备等内存受限的边缘环境。随着越来越多的向量检索任务需要在边缘设备上完成，如何在有限内存和较高磁盘I/O成本下实现低延迟、高召回的RFANN查询，成为一个具有实际价值的问题。
为此，本文提出了面向边缘设备的磁盘友好型RFANN框架MiniRFANN。该方法通过层次聚类为向量分配能够反映相似性局部性的簇编号，并利用乘积量化将高维向量压缩为紧凑的PQ编码；在此基础上，MiniRFANN分别构建基于属性值和基于簇编号的双B+树索引，使系统既能利用属性范围进行硬过滤，也能利用向量相似性进行软剪枝。针对不同查询中属性过滤和距离过滤剪枝能力不一致的问题，MiniRFANN进一步设计了自适应索引选择策略，根据查询范围和候选规模动态选择更省I/O的索引路径。同时，方法还采用Z-order布局对磁盘中的原始向量进行重排，使属性相近、簇编号相近的数据尽可能连续存储，从而减少精确重排序阶段的随机磁盘访问。总体来看，MiniRFANN的价值在于将范围过滤、向量近似搜索和磁盘数据布局进行协同优化，使RFANN查询能够在资源受限的边缘设备上兼顾检索准确性、查询延迟和内存开销，为端侧多媒体检索、移动设备RAG、本地传感器数据分析等应用提供了更高效的向量检索方案。
方法框架
1. 问题定义
给定一个属性向量数据集O = {o1, o2, ..., on}，每个对象oi由两部分组成：一是高维特征向量vi，二是一个数值型属性ai。其中，高维向量可以表示图像、文本、推荐物品或传感器数据的embedding，数值属性则可以是时间戳、地理位置、价格等辅助信息。
范围过滤近似最近邻搜索（Range-Filtered Approximate Nearest Neighbor, RFANN）的目标是：给定一个查询Q = {vQ, (aL, aR)}，在数据库中找到既满足属性范围aL ≤ ai ≤ aR，又与查询向量vQ最相似的Top-k对象。例如，在端侧相册检索中，用户可能希望查询“最近七天在校园附近拍摄的相似照片”；在传感器数据分析中，用户也可能需要检索“某一区域范围内与目标模式相近的监测记录”。
与普通ANN检索不同，RFANN不仅要考虑向量空间中的相似性，还要同时满足属性范围约束。因此，本文将任务形式化为：
离线阶段：为带有属性的高维向量数据构建适合边缘设备的磁盘友好型索引结构，并优化原始向量在磁盘上的存储布局
在线阶段：给定查询向量和属性范围，系统自适应选择合适的索引路径，通过属性过滤和距离剪枝共同缩小候选集合，再经过粗排与精排得到最终Top-k结果。
该任务的核心挑战在于：1. 如何在手机、嵌入式设备等内存受限的边缘环境中，避免将完整索引和原始向量全部加载到内存？2. 如何同时处理属性范围约束和向量相似性约束，避免预过滤、后过滤在不同查询范围下产生大量无效I/O？3. 如何在最终精确重排序阶段减少随机磁盘访问，从而降低整体查询延迟？
针对上述问题，作者提出了MiniRFANN，一种面向边缘设备的磁盘驻留式范围过滤向量检索框架。其核心思想是：将属性过滤看作“硬过滤”，将向量相似性剪枝看作“软剪枝”，并通过双B+树索引、自适应索引选择和Z-order磁盘布局协同降低查询过程中的内存占用和I/O开销。
2. 整体流程
MiniRFANN的整体框架如图1所示，可以分为两大部分：左侧是索引构建与数据布局优化，主要在离线阶段完成；右侧是查询处理，主要在在线阶段执行。
图1. MiniRFANN框架示意图
整体来看，MiniRFANN 由四个关键步骤构成：
（1）预处理（Preprocessing）
MiniRFANN首先对原始高维向量进行预处理，主要包括层次聚类和乘积量化两部分。
层次聚类用于解决高维向量缺乏天然排序的问题。对于时间、价格这类属性，可以直接按照数值大小排序；但对于高维embedding而言，并不存在一个天然的一维顺序。因此，MiniRFANN采用层次聚类将相似向量划分到相近的簇中，并为每个向量分配一个簇编号cluster ID。这样，向量之间的相似性关系就可以通过簇编号进行近似表达，后续查询时也可以优先访问与查询向量更接近的簇。
乘积量化（Product Quantization, PQ）则用于压缩高维向量。MiniRFANN 将原始向量划分为多个子空间，并在每个子空间中用码本进行量化，最终把一个高维向量编码为紧凑的 PQ code。这样做的好处是，查询阶段可以先利用 PQ code 快速估计向量距离，而不必一开始就读取完整原始向量，从而降低内存开销和磁盘访问成本。
经过预处理后，每个对象都会被组织成一条结构化记录，其中包含对象ID、属性值、簇编号以及PQ编码。这些信息将作为后续索引构建和查询过滤的基础。
（2）双B+树索引构建（Dual B+Tree Indexing）
在得到结构化记录后，MiniRFANN构建两棵互补的B+树索引：属性B+树和簇编号B+树。
属性B+树以对象的属性值ai为键进行组织，主要用于支持时间、位置、价格等范围条件的快速扫描。当查询的属性范围较窄时，系统可以通过属性B+树快速定位满足范围约束的数据，从而避免访问大量无关对象。
簇编号B+树以对象所属的cluster ID为键进行组织，主要用于支持基于向量相似性的候选剪枝。由于相似向量在层次聚类后会被分配到相近簇中，因此系统可以优先扫描与查询向量距离较近的簇，减少不相关候选的访问。
这里选择B+树而不是常见的图索引，是因为MiniRFANN面向的是边缘设备场景。在这类场景下，数据通常无法全部放入内存，而B+树天然适合磁盘存储和范围扫描，可以将主要索引结构保存在磁盘上，只在查询时加载必要节点，从而更好地适配内存受限环境。
（3）磁盘数据布局优化（Data Layout Optimization）
完成索引构建后，MiniRFANN进一步优化原始向量在磁盘上的物理存储顺序。原因在于，PQ编码只能用于近似距离估计，系统最终仍然需要读取部分候选对象的原始向量，进行精确距离计算和最终重排序。如果这些原始向量在磁盘上分布得很分散，就会造成大量随机I/O，显著增加查询延迟。
为了解决这一问题，MiniRFANN使用Z-order曲线对原始向量进行重排。具体来说，它将每个对象的属性值ai和簇编号c(vi)看作二维坐标，并将这个二维空间映射为一维的磁盘存储顺序。这样，属性相近且向量相似的数据更可能被连续存放在磁盘上。
这一设计的作用是提高磁盘访问的局部性。当系统在精排阶段读取某个候选原始向量时，一次连续读取往往可以同时带出多个相关候选，从而减少随机访问次数，提高重排序效率。
图2. MiniRFANN查询处理示例
（4）在线查询处理（Query Processing）
在查询阶段，MiniRFANN首先接收一个由查询向量vQ和属性范围(aL,aR)组成的RFANN查询。随后，系统并不会固定使用某一种索引，而是先进行自适应索引选择。MiniRFANN会估计两类选择性：属性选择性和距离选择性。属性选择性表示有多少对象落在给定属性范围内，距离选择性表示需要访问多少相似簇才能获得足够候选。若属性范围较窄，说明属性过滤可以排除大量对象，此时系统选择属性B+树；若属性范围较宽，属性过滤效果较弱，而相似簇剪枝更有效，则系统选择簇编号B+树。
图2进一步展示了这一自适应选择过程。对于查询Q1，其属性范围为[7,10]，满足条件的数据较少，因此MiniRFANN选择属性B+树，先定位并扫描对应属性区间内的叶子节点，再结合簇编号和PQ距离筛选出与查询向量更相似的候选对象；而对于查询Q2，其属性范围更宽，如果仍然从属性范围入手会访问更多无关数据，因此系统选择簇编号B+树，先访问与查询向量更接近的簇范围，再检查其中对象是否满足属性约束。也就是说，MiniRFANN在查询过程中会根据不同查询范围动态切换索引路径，将属性硬过滤和距离软剪枝结合起来，使候选集合尽可能小而有效。
最后，系统对候选对象进行两阶段重排序。第一阶段是粗粒度重排序，直接利用PQ编码估计候选对象与查询向量之间的距离，并筛选出排名靠前的一批候选；第二阶段是细粒度重排序，系统从磁盘中读取这些候选的原始向量，计算精确距离，并返回最终Top-k结果。由于原始向量已经通过Z-order进行布局优化，精排阶段的磁盘访问也能获得更好的连续性，从而进一步降低查询延迟。
总体来看，MiniRFANN的方法并不是单独优化某个检索环节，而是围绕边缘设备“内存有限、磁盘I/O成本高”的特点，对向量压缩、索引结构、查询路径选择和磁盘布局进行了协同设计。通过层次聚类和PQ编码，MiniRFANN降低了高维向量检索的存储与计算成本；通过双B+树索引，它同时支持属性范围过滤和向量相似性剪枝；通过自适应索引选择，它能够根据不同查询范围动态选择更低I/O的执行路径；通过Z-order布局，它进一步减少了精确重排序阶段的随机磁盘访问。最终，该框架能够在资源受限的边缘设备上实现低延迟、高召回的范围过滤向量相似性搜索。实验结果
1. 实验设置
本文在SIFT、GIST和Paper三个标准数据集上进行了系统性实验，分别覆盖图像局部特征、图像全局特征以及论文文本嵌入等不同类型的高维向量数据。对比方法包括Pre-Filtering、DiskIVF-PostFiltering和SPANN-PostFiltering，评估指标主要包括查询延迟、Recall@10、内存开销以及索引构建时间。为了模拟不同范围过滤场景，论文设置了多种属性查询范围，从窄范围到宽范围考察各方法在不同查询条件下的性能变化。
2. 主要检索性能对比
图3展示了三类数据集在不同属性范围下的查询延迟与Recall@10对比结果。整体来看，MiniRFANN在所有数据集和查询范围下都取得了更优的延迟-召回率平衡：在保持相同召回率水平的情况下，MiniRFANN相比现有基线方法将查询延迟降低了10.02%到87.13%。
图3. 三个数据集在不同属性范围下的查询性能对比
这一优势在属性范围较窄的查询中更加明显。例如在Paper数据集、查询范围比例为2⁻⁶的设置下，MiniRFANN的查询延迟为39.88 ms，相比最佳基线方法的82.02 ms降低了51.38%。这说明，当查询条件能够有效缩小候选集合时，MiniRFANN的双B+树索引和自适应选择策略可以更充分地减少无效磁盘访问。
同时，实验也展示了不同查询范围对方法性能的影响。对于Pre-Filtering方法，属性范围越宽，需要扫描和加载的有效对象越多，因此延迟会明显上升；对于Post-Filtering方法，范围变宽后更容易在候选集中命中满足属性条件的对象，因此延迟反而可能下降。而MiniRFANN会根据查询范围动态选择属性B+树或簇编号B+树，在不同范围设置下都能保持更稳定的检索效率。
3. 内存开销对比
图4展示了不同方法在查询过程中的内存开销。实验结果表明，MiniRFANN在所有数据集和查询范围下都具有最低的内存占用，相比最佳基线方法降低了5.88%到66.67%。
图4. 三个数据集在不同属性范围下的查询内存开销对比
这一结果说明，MiniRFANN的磁盘驻留式设计能够有效适配边缘设备的内存限制。由于系统主要在磁盘上维护索引和原始向量，并通过PQ编码、B+树叶节点扫描和候选重排序减少内存中需要保留的数据量，因此在SIFT1M和Paper数据集上的查询内存开销均低于50MB，在GIST1M上也低于80MB。对于手机、嵌入式终端等内存受限设备来说，这种低内存占用是MiniRFANN相比传统RFANN方法的重要优势。
4. 索引构建时间对比
表1给出了不同方法在三个数据集上的索引构建时间。Pre-Filtering的构建时间最短，这是因为它只需要基于属性值建立简单索引，不需要复杂的向量索引结构。相比之下，MiniRFANN需要进行层次聚类、乘积量化、双B+树构建以及磁盘布局优化，因此构建过程更复杂。
表1: 不同方法的索引构建时间对比
不过，与更强的Post-Filtering类方法相比，MiniRFANN的索引构建成本仍然是可接受的。相较于SPANN-PostFiltering，MiniRFANN在SIFT、GIST和Paper三个数据集上的额外构建时间开销分别仅为7.4%、2.1%和9.1%。这说明，MiniRFANN在引入自适应双索引和磁盘布局优化后，并没有带来过高的离线构建负担。
结语
本文围绕范围过滤近似向量检索在边缘设备中面临的内存受限与磁盘I/O开销过高这一核心问题，提出了MiniRFANN框架。与传统RFANN方法不同，MiniRFANN并不依赖将完整索引常驻内存，而是从边缘设备“数据主要驻留磁盘、内存资源有限”的现实条件出发，对索引结构、查询策略和磁盘布局进行了协同设计。
MiniRFANN的核心创新主要体现在三个方面：首先，通过层次聚类和乘积量化，将高维向量转化为更适合磁盘索引和近似距离计算的紧凑表示；其次，通过属性B+树和簇编号B+树构建双索引结构，并结合自适应索引选择机制，在不同查询范围下动态选择更低I/O的执行路径；最后，利用Z-order数据布局优化原始向量在磁盘上的存储顺序，减少精确重排序阶段的随机访问开销。实验结果表明，MiniRFANN在多个标准数据集上能够同时降低查询延迟和内存占用，并保持较高召回率。
总体来看，MiniRFANN为边缘设备上的带属性约束向量检索提供了一种高效可行的解决方案。它的价值不仅在于提升了RFANN查询性能，更重要的是证明了在资源受限环境中，通过“向量压缩、范围索引、自适应查询和磁盘布局”协同优化，可以有效支撑端侧多媒体检索、移动设备RAG、本地传感器数据分析等实际应用场景。作者简介
期刊简介
