Approximate Nearest Neighbor Search with Window Filters
作者: Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, Julian Shun
分类: cs.DS, cs.IR, cs.LG
发布日期: 2024-02-01 (更新: 2024-06-04)
备注: Code available: https://github.com/JoshEngels/RangeFilteredANN
💡 一句话要点
提出c-近似窗口搜索以解决标签范围内的邻近搜索问题
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 近似最近邻 窗口搜索 标签过滤 树形结构 数据检索
📋 核心要点
- 核心问题：现有的c-近似最近邻搜索方法在处理带有标签范围的查询时效率较低，难以满足实际应用需求。
- 方法要点：论文提出了一种模块化树形框架，能够将传统的c-近似最近邻索引转化为适用于窗口搜索的高效数据结构。
- 实验或效果：在标准基准数据集上，提出的方法在相同召回率下实现了高达75倍的速度提升，显示出显著的性能优势。
📝 摘要（中文）
本文定义并研究了c-近似窗口搜索问题：在数据集中每个点都有一个数值标签，目标是在任意标签范围内找到查询的最近邻。许多语义搜索问题，如带时间戳过滤的图像和文档搜索，或带成本过滤的产品搜索，都是这一问题的自然例子。我们提出并理论分析了一种模块化树形框架，用于将解决传统c-近似最近邻问题的索引转换为解决窗口搜索的数据结构。在配备随机标签值、对抗性构造的嵌入以及具有真实时间戳的图像搜索嵌入的标准最近邻基准数据集上，我们在相同的召回率下实现了高达75倍的速度提升。
🔬 方法详解
问题定义：本文旨在解决c-近似窗口搜索问题，即在数据集中每个点都有数值标签的情况下，如何在任意标签范围内高效找到查询的最近邻。现有方法在处理此类查询时，往往面临效率低下和性能不足的挑战。
核心思路：论文的核心思路是通过构建一个模块化的树形框架，将传统的c-近似最近邻索引转化为能够处理窗口搜索的数据结构。这种设计旨在提高查询效率，特别是在标签范围过滤的场景中。
技术框架：整体架构包括几个主要模块：首先是数据预处理阶段，生成带标签的数据集；其次是索引构建阶段，利用树形结构存储数据；最后是查询处理阶段，通过标签范围快速检索最近邻。
关键创新：最重要的技术创新点在于提出了一个新的索引结构，能够有效支持带标签范围的查询，显著提高了搜索速度和准确性。这与现有方法的本质区别在于其模块化设计和针对特定查询类型的优化。
关键设计：在关键设计方面，论文详细讨论了树形结构的构建方式、节点的分裂策略以及标签范围的处理机制。这些设计确保了在高维数据中依然能够保持良好的查询性能。
🖼️ 关键图片
📊 实验亮点
实验结果表明，提出的方法在标准最近邻基准数据集上实现了高达75倍的速度提升，同时保持了相同的召回率。这一显著的性能提升展示了新方法在处理复杂查询时的优势，超越了现有的解决方案。
🎯 应用场景
该研究的潜在应用领域包括图像和文档搜索、电子商务产品搜索等场景，尤其是在需要根据时间戳或成本等标签进行过滤的情况下。其实际价值在于能够显著提高搜索效率，满足用户对快速响应的需求，未来可能影响多个行业的数据检索方式。
📄 摘要（原文）
We define and investigate the problem of $\textit{c-approximate window search}$: approximate nearest neighbor search where each point in the dataset has a numeric label, and the goal is to find nearest neighbors to queries within arbitrary label ranges. Many semantic search problems, such as image and document search with timestamp filters, or product search with cost filters, are natural examples of this problem. We propose and theoretically analyze a modular tree-based framework for transforming an index that solves the traditional c-approximate nearest neighbor problem into a data structure that solves window search. On standard nearest neighbor benchmark datasets equipped with random label values, adversarially constructed embeddings, and image search embeddings with real timestamps, we obtain up to a $75\times$ speedup over existing solutions at the same level of recall.