跳到主要内容
检索

# 近似最近邻搜索

5 篇关联报道

订阅更新
  1. arXiv

    HyperPage 用上一轮智能体搜索日志重排磁盘索引页：同等缓存下比 MARGO 少读 5.2% 到 21.2% 的页

    磁盘驻留图向量索引的页布局决定一次搜索要读多少 SSD 页，而 Starling、MARGO 这类现有布局只从图和向量计算，不用查询日志。HyperPage 把一次已完成的 Search-R1 智能体运行中记录的扩展节点集合当作工作负载，在声明的内存预算下先为未被缓存命中的记录构造布局，再用验证步骤回放选出布局与热记录/页缓存之间的预算切分。在 1M 与 21M 段落索引、七个缓存预算上，它比 MARGO 少读 5.2% 到 21.2% 的页，缓存越小时优势越大。

    Xinyu Zhang（第一作者）
    HyperPage学习式页布局磁盘驻留图索引近似最近邻搜索
  2. arXiv

    图索引搜索学会提前收手：CaST在风险约束下把代价压到类最优的1.132倍以内

    带类别配额约束的向量检索此前只能靠固定访问预算或按平均召回率学习的停止规则，无法保证返回精确答案。CaST把停止规则限定在声明接口上的单调类，用固定序列二项检验校准，并用拉格朗日弱对偶给出该类最优代价的下界。在两个各含一百万条目的数据集上，风险水平0.03至0.10时其回放代价不超过类最优的1.132倍，95%置信度；在0.05风险目标下，其平均时延低于所测其他已校准规则。

    Xinyu Zhang（第一作者）
    CaST校准早停规则早停约束k近邻搜索近似最近邻搜索
  3. arXiv

    e-means 把 k-means 收敛压到十分之一轮次：100 亿嵌入聚类在 GPU 上快 9.5 到 45.5 倍

    e-means 把 k-means 的质心更新换成小批量指数移动平均，并用拟合出的缩放律从问题规模直接定出批大小与步长，不再需要超参数扫描。在多个嵌入数据集上，它用 1.4 到 2.6 个 epoch 就达到 Lloyd k-means 跑 25 个 epoch 的损失，对应相对 Flash-KMeans 的 9.5 到 45.5 倍实际耗时加速，并在收敛后损失更低。在 100 亿向量的 DINO10B 上，精确分配版本用 2.5 个 epoch 把向量分成 1600 万个簇，损失低于 Lloyd 跑 25 个 epoch 的结果。

    Swann Bessa（第一作者）
    e-means算法K均值聚类缩放定律近似最近邻搜索
  4. arXiv

    隐私向量检索不再随库规模线性变慢：HNSecW把在线搜索压到对数时间，十亿级数据上仍保住召回

    在查询与数据库双方都需保密的对称隐私场景下，HNSecW把基于HNSW图索引的近似最近邻搜索改造成可在安全多方计算中执行的全数据无关流程，使单次查询的在线通信与本地计算达到对数复杂度。此前同类协议多采用聚类式流程，在线通信随数据库规模线性增长。在百万到十亿级基准上，HNSecW保持与明文HNSW相当的召回，并在广域网上相对2PC PANTHER取得最高数量级的端到端加速。

    Northwestern UniversityBeihang UniversityNanyang Technological UniversityUniversity of Illinois Urbana-Champaign
    Fahong Zhang（第一作者）
    HNSecW安全近似最近邻协议近似最近邻搜索安全多方计算分层可导航小世界图不经意访问模式
  5. arXiv

    传感器不再重复上传相似画面：命中时只发六字节索引，接收端取回已存原图

    Memento把传感器观测改成按引用传输：先在本地持久存储的向量表里检索相似旧样本，命中就只发一个索引，模型分析显示在LoRa这类低速率链路上，25%命中率即可把延迟和能耗各降约四分之一。

    Chae Young Lee（第一作者）
    Memento通信系统基于检索的通信近似最近邻搜索持久记忆分布偏移

已读完全部报道