Scholarlink

<p>Approximate vector similarity search (ANN) is fundamental for applications such as recommendations, multimedia retrieval, and retrieval-augmented generation. In many scenarios, search results must also satisfy constraints on auxiliary attributes such as timestamps or locations, giving rise to the range-filtered approximate <i>k</i>-nearest neighbor (RFANN) problem. Existing RFANN approaches, including pre-filtering, post-filtering, and in-filtering, perform well on servers but are poorly suited for edge devices due to limited memory and high I/O costs. We present MiniRFANN, a disk-resident RFANN scheme for edge environments. MiniRFANN builds dual B+trees over product-quantized vectors, keyed respectively by attributes and cluster identifiers, enabling range scans with early pruning under tight memory budgets. An adaptive index selection strategy models range filtering and similarity pruning as hard and soft selectivities, choosing the index that minimizes I/O for each query. A Z-order data layout over attribute and cluster identifier spaces further improves locality, reducing random access during exact re-ranking. Experiments on standard benchmarks show that MiniRFANN achieves high recall with substantially lower memory usage and latency compared to state-of-the-art RFANN methods adapted for edge deployment.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

MiniRFANN: Range-Filtered Approximate Vector Similarity Search on Edge Devices

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年4月29日

查看全文
  • Shuyuan Li,
  • Yuheng Liu,
  • Yuxiang Wang,
  • Zimu Zhou,
  • Kaining Zhang,
  • Yongxin Tong

摘要

Approximate vector similarity search (ANN) is fundamental for applications such as recommendations, multimedia retrieval, and retrieval-augmented generation. In many scenarios, search results must also satisfy constraints on auxiliary attributes such as timestamps or locations, giving rise to the range-filtered approximate k-nearest neighbor (RFANN) problem. Existing RFANN approaches, including pre-filtering, post-filtering, and in-filtering, perform well on servers but are poorly suited for edge devices due to limited memory and high I/O costs. We present MiniRFANN, a disk-resident RFANN scheme for edge environments. MiniRFANN builds dual B+trees over product-quantized vectors, keyed respectively by attributes and cluster identifiers, enabling range scans with early pruning under tight memory budgets. An adaptive index selection strategy models range filtering and similarity pruning as hard and soft selectivities, choosing the index that minimizes I/O for each query. A Z-order data layout over attribute and cluster identifier spaces further improves locality, reducing random access during exact re-ranking. Experiments on standard benchmarks show that MiniRFANN achieves high recall with substantially lower memory usage and latency compared to state-of-the-art RFANN methods adapted for edge deployment.