无需索引的动态向量检索,查询速度提升6.9倍且召回率100%。
Index-Free Dynamic Edge Retrieval with Energy-Tail-Aware Partial Scans
- 通过截断低能量尾部坐标,仅计算高重要性维度提升效率
- 在九个数据集上平均召回率99.2%,查询速度超精确扫描4倍以上
- 适用于实时更新场景,尤其适合移动端部署
动态最大内积搜索(MIPS)在支持插入、替换和删除的同时,返回与查询向量内积最大的前K个存储向量。边缘检索需兼顾高召回率与快速查询,同时避免更新开销过大。全向量扫描虽更新简单,但查询成本高;而索引方法虽降低查询代价,却增加更新复杂度。本文提出ETAR,一种无索引方法,在保持简单更新的同时显著减少查询工作量。ETAR保留查询向量中平方值最大的坐标,直到覆盖其总平方幅值的大部分,其余视为低能量尾部。通过紧凑的低精度表示估算相似性,修正被跳过的坐标,并使用全精度向量对固定数量候选进行重排序。在九个静态数据集上五次运行中,ETAR平均达到99.2% Recall@10,且在代表性设置下比精确扫描快4倍以上。该加速效果也延伸至基于ARM的移动设备,在四个合成分布上最快达6.9倍加速。在五种流式工作负载下,始终维持100% Recall@10,无需重建索引。总体而言,ETAR为动态MIPS提供了实用的折中方案,降低查询成本并保留无索引更新优势。代码开源:https://github.com/arasyi/etar-mips。
原文摘要 · Abstract (English)
Dynamic maximum inner-product search (MIPS) returns the $K$ stored vectors with the largest dot products with a query while allowing the dataset to change through insertions, replacements, and deletions. For edge retrieval, the challenge is to achieve high recall and fast queries without making updates expensive. Full-vector scanning keeps updates simple but compares each query with every stored vector, while indexed methods reduce query cost at the expense of maintaining additional structures during updates. We propose ETAR, an index-free method that reduces query work while preserving simple updates. ETAR keeps the query coordinates with the largest squared values until they cover most of its total squared magnitude and treats the rest as a low-magnitude tail. It estimates similarity from the retained coordinates using a compact lower-precision representation, corrects for skipped coordinates, and reranks a fixed number of candidates using full-precision vectors. Across five runs on nine static datasets, ETAR averages 99.2% Recall@10, the fraction of exact top-10 results recovered, while running over 4$\times$ faster than exact scanning at a representative setting. This speedup also extends to an ARM-based mobile device, where ETAR is up to 6.9$\times$ faster across four synthetic distributions. Under five streaming workloads, it maintains 100% Recall@10 at every measured point without index rebuilds. Overall, ETAR offers a practical middle ground for dynamic MIPS by reducing query cost while retaining simple, index-free updates. Code is available at https://github.com/arasyi/etar-mips.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。