Scholarlink

The Hierarchical Navigable Small World (HNSW) graph is widely recognized for its state-of-the-art performance in approximate k-NN search, leveraging a multi-layer proximity graph to efficiently navigate high-dimensional spaces. However HNSW graph traversal can become computationally expensive, especially for large-scale datasets. To address this challenge, we introduce a strategy to early terminate HNSW graph traversal, dubbed “Patience in Proximity”. Inspired by techniques from clustering-informed approximate nearest neighbor algorithms, our approach employs a saturation-based threshold to dynamically halt graph exploration, reducing computational overhead without significantly compromising accuracy. We evaluate the proposed method on diverse datasets from the BEIR benchmark.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Patience in Proximity: A Simple Early Termination Strategy for HNSW Graph Traversal in Approximate k-Nearest Neighbor Search

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Tommaso Teofili,
  • Jimmy Lin

摘要

The Hierarchical Navigable Small World (HNSW) graph is widely recognized for its state-of-the-art performance in approximate k-NN search, leveraging a multi-layer proximity graph to efficiently navigate high-dimensional spaces. However HNSW graph traversal can become computationally expensive, especially for large-scale datasets. To address this challenge, we introduce a strategy to early terminate HNSW graph traversal, dubbed “Patience in Proximity”. Inspired by techniques from clustering-informed approximate nearest neighbor algorithms, our approach employs a saturation-based threshold to dynamically halt graph exploration, reducing computational overhead without significantly compromising accuracy. We evaluate the proposed method on diverse datasets from the BEIR benchmark.