Apache Lucene向量搜索优化：ACORN-1算法在过滤搜索中的应用探索

背景与挑战

在Apache Lucene的向量搜索实现中，过滤条件下的k近邻（kNN）搜索一直存在优化空间。传统HNSW（Hierarchical Navigable Small World）算法在过滤场景下，可能会因为过早终止搜索而错过符合条件的潜在结果，特别是在过滤条件严格（过滤掉大量文档）的情况下表现尤为明显。

ACORN-1算法核心思想

ACORN-1算法提出了一种创新的多跳扩展搜索策略，其核心改进点包括：

1. 谓词子图遍历：仅对通过过滤条件的候选节点进行评分和考虑，避免无效计算
2. 两跳邻居扩展：在搜索过程中不仅查看直接邻居，还探索邻居的邻居，防止遗漏符合条件的远端节点
3. 条件性扩展策略：根据过滤条件的选择性动态决定是否启用两跳扩展，平衡召回率与性能

实现验证与性能表现

通过基准测试（使用20万文档的Cohere嵌入数据集）发现：

传统HNSW表现：

• 在5%选择性的严格过滤下，召回率仅3.7%，延迟达17ms
• 随着过滤条件放宽，性能逐步提升，95%选择性时延迟降至2.4ms

ACORN-1改进方案：

• 严格过滤场景（5%选择性）延迟大幅降低85%至2.7ms
• 中等选择性场景保持相当性能，召回率略有下降
• 宽松过滤场景延迟略有增加但控制在合理范围

关键技术考量

1. 相关性影响：查询向量与过滤条件的相关性对算法效果影响显著。负相关场景需要特殊处理
2. 多层入口优化：考虑在过滤搜索中引入多个底层入口点，以应对低相关性场景
3. 动态参数调整：需要根据过滤选择性和数据分布自动调整扩展策略

未来优化方向

1. 开发相关性检测机制，动态选择搜索策略
2. 探索结合量化估计的图构建方法
3. 研究二分图节点组织对过滤搜索的影响
4. 完善基准测试体系，增加相关性维度评估

这项优化展示了Apache Lucene在保持核心算法稳定性的同时，通过创新性改进持续提升特定场景下的搜索效能，为向量数据库领域提供了有价值的实践参考。