Graph Reordering for Cache-Efficient Near Neighbor Search

Benjamin Coleman, Santiago Segarra, Anshumali Shrivastava, Alex Smola

Abstract

Graph search is one of the most successful algorithmic trends in near neighbor search. Several of the most popular and empirically successful algorithms are, at their core, a simple walk along a pruned near neighbor graph. Such algorithms consistently perform at the top of industrial speed benchmarks for applications such as embedding search. However, graph traversal applications often suffer from poor memory access patterns, and near neighbor search is no exception to this rule. Our measurements show that popular search indices such as the hierarchical navigable small-world graph (HNSW) can have poor cache miss performance. To address this problem, we apply graph reordering algorithms to near neighbor graphs. Graph reordering is a memory layout optimization that groups commonly-accessed nodes together in memory. We present exhaustive experiments applying several reordering algorithms to a leading graph-based near neighbor method based on the HNSW index. We find that reordering improves the query time by up to 40%, and we demonstrate that the time needed to reorder the graph is negligible compared to the time required to construct the index.

Introduction

In modern AI applications, data is frequently represented as high-dimensional embeddings. Searching for similar items—whether products, documents, or images—requires efficient Approximate Nearest Neighbor (ANN) search. Currently, graph-based indices like the Hierarchical Navigable Small World (HNSW) graph are the state-of-the-art. These indices operate by traversing edges to find nodes closest to a query vector.

However, these traversals are often bottlenecked by the "Memory Wall." While CPUs have become significantly faster, memory latency remains a major hurdle. Graph traversals are inherently "cache-unfriendly" because following an edge often results in a jump to a distant, random memory location. This leads to frequent cache misses, forcing the CPU to idle. This research investigates optimizing the physical layout of these graphs in memory to keep neighbors physically proximal, thereby reducing latency and improving cache efficiency.

Methodology and Datasets

The researchers treat graph reordering as a post-processing step performed after index construction but before querying. They evaluated three categories of reordering algorithms:

  1. Objective-Based (Global): Algorithms like Gorder (maximizing neighborhood overlap in consecutive memory) and RCM (Reverse Cuthill-McKee, minimizing adjacency matrix bandwidth).
  2. Lightweight (Local): Simple heuristics such as Degree Sorting or Hub Sorting.
  3. Grouping/Partitioning: Methods like Degree-Based Grouping (DBG) that cluster nodes based on connectivity.

The evaluation utilized several large-scale industrial benchmarks: SIFT100M (100M image descriptors), DEEP100M (100M deep learning embeddings), GIST1M, and MNIST.

Key Insights: The Pruning Paradox and Overhead

A critical observation is that while theoretical $k$-nearest neighbor graphs are regular, real-world indices like HNSW use pruning heuristics that create non-uniform degree distributions. This non-uniformity—where some nodes act as "hubs"—provides an exploitable structure for reordering algorithms.

Crucially, the computational cost of this optimization is minimal. As shown in the data, the time required to reorder even a 100-million-node graph is an order of magnitude less than the initial graph construction time, making it a highly efficient performance boost.

Reordering time across various datasets compared to initial graph construction time.

Experimental Results

The application of global reordering methods yielded significant performance gains:

  • Latency Reduction: Gorder improved query time by up to 40% on large datasets. RCM provided a 17-20% improvement.
  • Cache Efficiency: On SIFT100M, Gorder reduced L1 cache misses from ~19.5% to 14.5% and L3 misses from 6.5% to 4.0%.
  • High-Recall Synergy: Performance gains were most pronounced in high-recall regimes where more nodes are visited, making cache efficiency paramount.

As illustrated in the latency analysis, the optimization significantly improves the 99th percentile (P99) latency, which is critical for real-time production environments.

P99 Latency vs. Recall on SIFT100M dataset, showing improvements from Gorder and RCM.

Conclusion and Future Work

Graph reordering offers a significant performance boost for graph-based ANN search by aligning the logical graph structure with the physical memory layout. While currently tested as a static optimization, future work could explore dynamic reordering for evolving graphs and the synergy between reordering and vector quantization techniques like Product Quantization (PQ). Additionally, investigating the impact across different hardware architectures remains a promising avenue for further research.

Summary updated

Abstract

Graph search is one of the most successful algorithmic trends in near neighbor search. Several of the most popular and empirically successful algorithms are, at their core, a simple walk along a pruned near neighbor graph. Such algorithms consistently perform at the top of industrial speed benchmarks for applications such as embedding search. However, graph traversal applications often suffer from poor memory access patterns, and near neighbor search is no exception to this rule. Our measurements show that popular search indices such as the hierarchical navigable small-world graph (HNSW) can have poor cache miss performance. To address this problem, we apply graph reordering algorithms to near neighbor graphs. Graph reordering is a memory layout optimization that groups commonly-accessed nodes together in memory. We present exhaustive experiments applying several reordering algorithms to a leading graph-based near neighbor method based on the HNSW index. We find that reordering improves the query time by up to 40%, and we demonstrate that the time needed to reorder the graph is negligible compared to the time required to construct the index.
BibTeX
@inproceedings{coleman2022graph,
  author = {Benjamin Coleman and Santiago Segarra and Anshumali Shrivastava and Alex Smola},
  title = {{Graph Reordering for Cache-Efficient Near Neighbor Search}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=8LeCgKb6UX},
}
Figure