研究人员开发了一个新的“认证后修正”（Certify-then-Rectify）框架，以提高分层可导航小世界（HNSW）图的准确性。HNSW图因其速度而被广泛使用，但缺乏理论正确性保证。该框架使用统计认证器评估HNSW搜索结果的质量，并在需要时升级到精确恢复算法。通过将HNSW图重新解释为几何跨度图并应用极值理论，该系统可以在数学上界定到真正最近邻的距离，从而实现HNSW的速度和精确搜索的最坏情况正确性。 AI
影响 增强了近似最近邻搜索的可靠性，这对于许多AI应用至关重要。
排序理由 学术论文，详细介绍了图搜索算法的新技术框架。[lever_c_demoted from research: ic=1 ai=1.0]
AI 生成摘要 · Google Gemini · 来自 2 个来源。 我们如何撰写摘要 →
arXiv:2607.02338v1 Announce Type: cross Abstract: Hierarchical Navigable Small World (HNSW) graphs serve as the industry standard due to their logarithmic complexity and strong empirical performance. However, HNSW relies on greedy graph traversal, a heuristic that provides no the…
Hierarchical Navigable Small World (HNSW) graphs serve as the industry standard due to their logarithmic complexity and strong empirical performance. However, HNSW relies on greedy graph traversal, a heuristic that provides no theoretical guarantees of correctness. In this paper,…