Graph Reordering for Cache-Efficient Near Neighbor Search
Authors: Benjamin Coleman
Santiago Segarra
Alex Smola
Anshumali Shrivastava
Venue: NeurIPS 2022 Accept (2022)
Keywords: near-neighbor search
embedding search
graph ordering
machine learning systems

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 greedy walk along a pruned near neighbor graph. 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 issue, we formulate the graph traversal problem as a cache hit maximization task and propose multiple graph reordering as a solution. Graph reordering is a memory layout optimization that groups commonly-accessed nodes together in memory. We mathematically formalize the connection between the graph layout and the cache complexity of search. 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%, we present analysis and improvements for existing graph layout methods, and we demonstrate that the time needed to reorder the graph is negligible compared to the time required to construct the index.

Graph Reordering for Cache-Efficient Near Neighbor Search
Benjamin Coleman"
Santiago Segarra ECE Department Rice University Houston, TX 77005 segarraßrice.co edu
ECE Department
Rice University
Houston, TX 77005
ray. www..ry...ollmaaggaal...ommmm
Alex Smola
Anshumali Shrivastava
Amazon Web Services
Department of Computer Science
alex@smola, org
Rice University Houston, TX 77005
anshumali@rice edu
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, greedy walk along pruned traversal applications often suffer from poor memory access patterns, and near neighbor search is no exception this rule. Our measurements show that popular search indices such as the hierarchical navigable small-world graph (HNSW) have poor cache miss performance. To address this issue, formulate the graph traversal problem as a cache hit maximization task and propose multiple graph reordering solution. Graph reordering is memory layout optimization that groups commonly-accesso formalize the connection between the graph layout and the cache complexity of search. We present exhaustive experiments applying several reordering algorithms leading graph-based near neighbor method based on the HNSW index. We find that reordering improves the query time by to 40%, we present analysis and improvements for existing graph layout methods, and we demonstrate that the time needed to reorder the graph is negligible compared to the time required to construct the index.
neighbor graph. However, graph
nodes together in memory. We mathematically
Introduction
Near neighbor search is fundamental building block within many applications in machine learning systems. Informally, the task can understood as follows. Given dataset D {z1, .2, ... we wish to build data structure that can be queried with any point obtain the k points E D that have the smallest distance the query. This structure called a near neighbor index. Near neighbor indices of tremendous practical importance, as they form the backbone of production models in recommendation systems, natural language processing Mikolov et al. (2013). genomics Ondov et al. (2016), computer vision Lowe (999) and other applications in machine learning Shakhnarovich et al. (2008).
Applications. The accuracy and speed of several machine learning algorithms critically depend on the recall and latency of near neighbor search. The problem the focus of intense research activity
Work was completed while the author was with Amazon Web Services.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

20%
75%
60%
5%
A
B
C
D
Figure I: Breakdown of query subroutines: initialization (A), visited lists (B), node traversal (C), and distance computation (D-E): x 40% of the query time is spent accessing vectors from memory (E).
The remainder (D) is floating point math.
due to its central role in neighbor-based classification, regression and prediction with embedding models. In neural embedding model, objects are transformed into embeddings in R4, where d ranges from 100 to 1000 and N often exceeds 100 million. Prediction typically consists of finding the k nearest embeddings. For example. Amazon's 's deep semantic search engine works by embedding the product catalog and the search query into the same high-dimensional space. The engine recommends the products whose embeddings nearest the embedded search query Nigam et al. (2019)
Since the search occurs for every query, the latency and recall of the system depend on the abil- ity to perform fast search in the high-recall regime. Similar problems exist in natural language processing Kusner et al. (2015), information retrieval eetrievalHHuang et al. (2013) and other application domains. Beyond machine learning, near neighbor indices are used to match audio recordings, detect plagiarism, classify ECG signals healthcare, and perform copyright attribution with blockchain Jafari et al. (2021). The problem is central bottleneck for many applications.
al. (2013), computer vision Frome
Latency Challenges. Solutions to the near neighbor problem are incredibly diverse, ranging from hardware-acceleratee brute force Johnson et al. (2099) to space-partie paaccepariiioning trees |Beygllzimer et al.) (2006). Graph algorithms have emerged as a markedly effective class of methods for high- digh-dimensional near neighbor search. For example, four of the top five search libraries on the well-established ANN- benchmarks leader board use graph index Aumüller et al. (2020). Because these libraries have been integrated with many large-scale production systems Johnson et al. (201)); Malkov Yashunin) (2018), they have been hand-optimized in C++ at large engineering cost. Practical techniques for fast graph search represent a highly active research area with clear impact.
Profiling the Query Time of HNSW. Figure shows the relative time spent performing different operations in the hicrarchical navigable small-world graph (HNSW) algorithm, which we obtained using the perf tool De Melo (2010) on the leading nmslib implementation. Approximately 40% of the time is spent on instructions corresponding to the first dimension of the distance computation, which is dominated by the cost of fetching the vectors from main memory. Thus, a good strategy to reduce the query latency is to target its major bottleneck, which appears to memory fetching.
1.1 Our Contribution
In this paper, propose graph reordering improve approximate near neighbor search. Graph reordering is a cache optimization that places neighboring nodes in consecutive (or consecunse memory locations. The new memory layout speed up traversal- based graph algorithms that are constrained by RAM access. The mechanism commonly understood to drive performance that of packing multiple nodes into cache line does not apply to near neighbor graphs, where a single node spans many cache lines. However, we demonstrate that hardware prefetching mechanisms make reordering viable optimization even in this sarge-node setting. Our work reveals that near neighbor search can be significantly accelerated through graph reordering, a hiterto unexplored optimization for this important task.
New Reordering Results. Graph reordering has not been thcoretically analyzed under any formal computational model. Beginning from first principles, we analyze the cost of breadth-first search under the idcalized cache model for several layouts and we develop an objective to find an optimal- cost layout. We also introduce mrofile-guides reordering, frequency of edge traversal to inform the co-location of nodes. By including observations of query traffic patterns through the graph, obtain speedup over query-agnostic algorithms. We show that the problem reduces to weighted graph reordering, which we solve with a greedy algorithm.
optimization that uses the empirical
Extensive Experimental Benchmark. We present a rigorous evaluation where we integrate graph reordering into HNSW. We perform an exhaustive comparison on large embedding datasets where we benchmark the query time and cache miss rate. Our experiments show that graph reordering

---

is a viable and effective way to improve practical machine learning deployments that involve near neighbor search. We make the following new observations:
1. Latency Improvement: Graph reordering improves the mean and 99th percentile latency by up to 40% and 20%, respectively.
2. Small Marginal Cost: The reordering time is an order of magnitude smaller than the time needed
to construct the search index.
3. Query-Enhanced Ordering: Our prfile-guides method provides an additional speedup over existing query query-agnostic algorithms.
4. Theoretical Analysis: We rigorously analyze popular heuristics in the ideal cache model, showing that objective-based methods provably attain speedups (while lightweight methods do not).
2 Background and Related Work
CPU Cache Hierarchy. Modern computers organize memory access into series of intermediate storage locations known as caches, When the CPU core is instructed to load data from RAM, it first checks to see whether the data resides in the nearest (LI) cache. If there is cache miss (i.e. the data not found), the processor performs secondary search in the L.2 and L3 caches, resorting to main memory if the data is not present in any cache. Caches are organized into sets of cache lines, small (32 or 64 byte) blocks of memory that are always moved together. Upon a cache miss, the CPU evicts the least recently-usee line to make room for the requested line. The access times for L1, L2, L3 and DRAM are about 1, 3, 10, and 100 nanoseconds, respectively Levinthal (2009). To ensure that data resides in the nearest possible cache, one may repeatedly access the same data (temporal locality) or ensure that saweenttalll-accessee data have nearby memory addresses (spatial locality).
Hardware and Software Prefetching. Cache lines are smaller than the size of many data objects. To increase cache hits, modern CPUs use a prefetcher to predict future lookups and preemptively place the corresponding lines in the L1 or 1.2 cache. Hardware prefetching is done by the processor using heuristics and simple learning algorithms. Software prefetching happens when the programmer manually inserts special prefetch instructions into the code. The two mechanisms interact in complex ways, with both synergistic and antagonistic effects, but improving the spatial locality of memory access is sound principle to improve performance Lee et al. (2012)
Near Neighbor Graphs. Graph-based algorithms such as HNSW, pruned approximate near neighbor graphs (PANNG) [wasaki (2016), and optimized near neighbor graphs (ONNG) Iwasaki & Miyazaki (2018) feature prominently in leader boards and production systems at web-scale companies. Apart from recent theoretical progress Prokhorenkova & Shekhovtsov (tppitssoo(((0)))) (2020), the primary focus of graph index research has been to develop heuristics (such as diversification, pruning, and hierarchical structures) that improve the properties of the graph, increase search accuracy. and reduce search time. We argue that most search algorithms have essentially the same computational workload because these heuristics produce highly similar graph structures.
Graph Structure and Graph Search. The core algorithmic components of graph search remain the same across most popular graph indices. We begin with a graph constructed by connecting each point in the dataset to a set of nearby points. These edges undergo diversification and pruning, where edges are added/deleted based on method-deeenderr heurstics. To perform the search, we select initial node and walk along the edges of the graph until a neighbor is found, recording the distance between the node and query at each step. Our crucial observation is that major search indices do not differ in terms of node access pattern or graph propertics relevant to reordering. We provide a more complete description in the supplementary materials.
Cache Locality of Graphs. Due to their industrial importance, search index implementations have been optimized aggressively in terms of memory access and computation. For example, the HNSW software manual Naidan INiddnn
al.) (2015) describes a "flattened index" to improve the memory access pattern and reduce memory fragmentation Boytsov & Naidan (2013). The flat layout stores nodes and data together in a contiguous pre-allocated block of memory. By avoiding pointers, the efficient layout avoids unnecessary implicit addressing and improves the ability of software and hardware prefetching to improve the algorithm Malkov & Yashunin (2018). The method provides sound improvements, but it leaves some performance on the table because is agnostic to the graph structure. Graph reordering
3

---

is an orthogonal improvement that uses information about the graph to further improve the layout by re-ordering nodes within the contiguous block of memory.
Ordering with Space-Filling Curves. Another similar idea involves the use of space-filling curves for search problems Chan (002). A space-filling curve is the shortest line that passes through each point in the dataset. One may use a cache efficient linear scan through the ordered data for fast search and graph construction in low-dimensional (d S 3) spaces Connor & Kumar (2100). However, the method suffers from the curse of dimensionality and does not work well for machine learning problems. To the best of our knowledge, our paper is the only investigation of graph reordering for fast near neighbor queries.
3 Graph Reordering
Formally, graph reordering can be seen as constructing a labeling function P: V + [1,...,NN N that assigns each node v V in a graph unique integer index (or label) between and N following pre-specified rule or in order to maximize some objective. Many formulations are possible, but we typically expect P to map connected nodes to similar (nearby) labels. The function P is then used as the memory layout for the graph, with node v assigned to memory location P(v).
Existing Techniques for Graph Reordering. We assess the ability of several recent methods to ac- celerate neighbor search. We consider the verse Cutkill-McKee order (RCM)Cuthil & McKee (1969); George 197I), gorder Weii et al. (2016), de- gree sorting, hub sorting Zhang et al. (2017). hub clustering Balaji & Lucia (2018), and bagree-based grouping Faldu et al. (2019). Gorder and RCM are objective-driven methods that seek to a minimizer of cost function, while the others are degree-based heuristics.
Reordering Time
Conprrutie
Reytort Sal
Time (secondis)
Diptart
HAC soter
137
Gorder. We discuss all layout methods in the sup- plementary materials, but Gorder (graph-order) is the current state of the art to accelerate analyses such as PageRank and graph diameter Wei al. (2016). The Gorder layout PGo optimizes the average neighbor- hood overlap between the connections of nearby nodes by maximizing the number of shared edges among size-w blocks of consecutive nodes. Since nodes are penalized for having neighbors further than w locations away, this objective a reasonable proxy for cache efficiency.
D1T200M DE0P100M
STT1EM DEEPSEN
Dataset
0GT
Figure 2: In our experiments, the reorder- ing algorithms required less time run than graph construction.
PGO arg max P
Σ BL V... IP(4)-
S,(u, + (n,
We use the notation S, v) to count the number of directed connections between u and v. S, (u, v) to count the number of shared in-neighbors between and u, and FGo (P) for the objective score. Two consecutive nodes improve FGO if they share a direct edge or have many common neighbors. Maximizing the objective is NP-hard, but greedy algorithm provides 1 1/(2w) (aproximai solution.
4 Theory
Here, we formalize the connection between graph layout and cache performance. We defer all proof's to the supplementary materials.
Idealized Cache Model. Our main theoretical contribution is to analyze the cache complexity of graph search under the idealized cache model Frigo et al. (1999) for various graph layouts. The idealized cache model is theoretical model of computation that counts the number of cache misses. The model assumes a cache with B "objects" per line and cache lines, which are evicted in the order that minimizes the overall number of cache misses.

---

Processing Time
Processing Time
Garder
RCV
104
RepSort (1t
Time (seconds)
Time (seconds)
Desfort Sout)
10P
RCM
Degton D1l Degtort (uO
237
100
Number of Nodes
Maximum Node Degree
Figure 3: Graph reordering scales to large datasets and complex near neighbor graphs. In experiments, the reordering algorithms required less time to run than graph construction. Reordering is feasible even for large graphs with many nodes (SIFT with k 16, middle) and for densely connected graphs (k: s 120) on large datasets (GISTIM, right).
Even though the size of graph node exceeds the size of real cache line, suppose that each line contains B nodes. This is reasonable because next-line prefetchers often implement this behavior and because auxiliary data structures, such as visited lists, represent nodes using only few bytes. We also assume that the cache empty at the start of the program, and we analyze the cost to perform step of breadth-first search under the common "tall cache" assumption (i.e. T B²).
important to note that our analysis is pessimistic the sense that the cache might include neighbors from previously -cccessed nodes, which could reduce the cost explore neighborhood. While real-world performance does benefit from this situation, our one-step clean-cache analysis provides a lower bound on the performance.
Given graph G (V, E). we consider the number of cache misses, or the cost C, of accessing node e and its neighbors. We also consider the cache efficiency CE2, or the number of cache hits involved when accessing a node and then each its out-neighbors in sequence.
C 1+
Σ B)EB(e)
(oye(())) II 1 ((ge((())) KC
CE₁
Σ BEEB(e)
(0yet(()) ((w))
del...
j=g...
Here, I(v) is the cache line containing and E(v) is the set of outbound edges of v. The 1 represents the initial cost to load U, and the sum represents the cost to load the lines containing neighbors of u
Goal of Reordering, We seek to minimize the average cost of depth-firse first search over the graph, or equivalently maximize the average efficiency CEprs = N E.,ev CF2. That is, we wish to find p* arg max CEpes(P).
Cache Complexity Objective. The cache efficiency score is cumbersome to work with directly. We use the following incqualities to transform CEDrs(P) into a form that is more amenable to optimization and analysis.
Theorem 1. Given a gruph =
GV, (V,E),
[t/B] Σ
((wr))mm - -1, 0)
UB
Σ
Σ
S.(v,, u;) + (x max
8=(o/B1+1
j=
Then the cache efficiency score CEDEs(P) obeys the following inequalities.
UB Triplets(v:) < CEDES S UB
where Sa(vi, v2)) and Sa vT) are as defined in Equation 7 Nand Triplets((:) is the number of triplet combinations of v; out-neighbors that fall into the same cache line.
5

---

Note that when B v 2, the upper bound and lower bound are equal (since we cannot form triplets from B 2 items). It is easy to show that this problem an NP-hard instance of the maximum weight perfect hypergraph matching problem.
Lemma 1. Given a graph G = (V,E), the problem of finding the layout with an optimal DFS cache cost an NP-hard instance of maximum weight perfect hypergraph matching.
Analysis of Gorder. One interesting and new observation is that the Gorder objective (Equation D is similar to our upper bound on cache complexity. By bounding the size the "extra" terms in the upper and lower bounds, we analyze the cost of the layout found by Gorder
Theorem 2. Let G = (V, E") be graph with maximum out-degree M, P be layout with objective score Foo (P), and P' be the layout obtained by running Gorder plus a simple cache boundary alignment procedure
P. P' satisfies the following inequalities:
1 1 B Foo(P)) - N(B- - [
(3)
CEDES(P*)
CEDES(P") S Fco(P)
3
We use the convention = 0 when a < b.
Using these inequalities, we can derive conditions under which Gorder is guaranteed to improve the cache efficiency.
Theorem 3. Given two node orderings P1 and P2 a graph with maximum out-degree M, CEDES P2) 2 CEDrs((i) if (Go(P2) 2 BFao + B(B 1)N + NM))
Theorem guarantees a cache efficiency improvement we increase the Gorder objective (and run simple alignment process). However, the objective must improve substantially for the theory to apply: the final score should be 2 B times the initial score, not to mention the combinatorial B term and linear N term. To address this concern, we computed the initial and final scores after running Gorder with B = (Table 2). We found that the improvement is large enough to guarantee cache benefits on practical tasks.
Implications for Other Methods. Lightweight algorithms cannot provably decrease the cache complexity without power-law assumption about the graph. For simple counterexample, consider a nearly-regular graph where all nodes have the same degree, except one. Degree-based sorting can easily move this node away from its neighbors, increasing the cost. A similar argument holds for the RCM order, since it considers only the maximum label discrepancy.
4.1 Improving the Ordering Process
Theorem requires a combinatorial term bound the deviation of CEDrs (P) from its upper bound. To investigate the gap between this bound and existing methods, we examine "Corder" objective (for cache order) which directly maximizes the lower bound. We also introduce a method based on empirical profiling of the node access pattern, which we call "Porder" (for profile order).
Cache Order. The Corder layout obtained follows:
Peo = arg max Fco
Σ S,(,u,m)
N.F.M stt. (P(a)-((b)<<n v(a.b)E(u.P.m)
S,(u, v m) is the number of shared parents among the triplet (u, v, m). Thanks this additional term, we optimize for the lower bound of Theorem rather than the upper bound. We use greedy selection algorithm to solve the optimization problem.
Profile Order: Intuition suggests that some parts of the search index graph are visited more frequently than others. Our Porder algorithm prioritizes important neighborhoods by considering a weighted graph order problem. We provide pseudocode in the supplementary materials and an application- agnostic implementation in the code.
Plus cache alignment procedure described in the supplementary materials.

---

Table 1: Perf stat results for cache misses and TLB misses on SIFTI00M. Other datasets show similar results.
Table 2:
Initial (F) and final (Py) the
Gorder scores with
maximum out-degree.
Original
RCM
Gorder
Dataset M
N
Fj
Fj
L1 (%)
19.53
17.37
14.46
SIFTIM
8
1M
6.6k
2.6M
L2 (%)
13.9
7.61
9.6
F-MNIST
4
60k
64
102k
L3 (%)
6.5
5.1
4.0
NYTimes
8
290k
417
736k
TLB (%)
3.85
2.56
2.14
Table 3: Cache miss rates for node traversals and distance computations on SIFTI00M (lower is better). It should be noted that due to the 100x latency difference between cache and RAM, small improvements to the cache miss rate can substantially speed up an algorithm. The ranking of algorithms by cache miss rate agrees with the ranking by speedup in Figure
Original Gorder RCM DegSort (in) DegSort (out) HubSort HubCluster DBG
L1 (%)
22.76
19.28
20.61
22.76 13.55
22.76 13.56
22.85
22.77
22.81
L3 (%)
13.56
8.32
8.91
13.63
13.51
13.34
Each edge is weighted proportional to its importance for near neighbor queries. In practice, we estimate the edge weights by issuing small number of search queries and counting the number of times the edge is traversed in the query process. This idea may incorporated into many existing ordering techniques, but we consider weighted version of Equation]
Pro arg max P
Σ
Sms v) + (w,
(3)
OL Vs.t. PP())
Here, (u, v) computes the sum of weighted out-edges between and v and Swn (u, v) computes sum of weighted in-edges from neighbors shared by u and v.
Experiments
Experiment Setup. Our experiments measure index performance using wall-clock query time with different memory layouts.
Query Latency. We benchmark the system after "warm start," where assets such the index, query, and data are pre-loaded into RAM. To avoid the difficulties associated with timing very short events, record the total time needed to perform 10k queries and report the average query time. Finally, we restrict the query program to a single core and ensure that the benchmark is the only program running the server. We run all of our experiments on server with 252 GB of RAM, 28 Intel Xeon E5-2697 CPUs, and a shared 36 MB L3 cache.
Cache Misses. We measure cache miss rates using the Linux perf tool to record hardware CPU counters for events such as data reads and cache hits. We use these counters to compute the cache miss rate by dividing the number of data cache misses by the number of data references. We run our most successful reordering methods (Gorder and RCM) on SIFTI00M and report results for the L1, L2, L3 and TLB caches. To validate these measurements, we also run the program through the cachegrind virtual processor. Using cachegrind, we annotate the source code of our program to verify that the cache miss reduction is from lines of code that execute node traversals and distance computations.
Implementation. We extended the nmslib implementation of HNSW to support graph reordering, with minor changes to speed up graph construction. We use the flat layout described by Naidan et al. (2015) to avoid memory fragmentation. To ensure that we benchmark realistic workload. we verified that our implementation uses the same memory layout, requires the same number of distance computations and produces the same graph umslib-HNSSe We implement eight reordering
7

---

SIFT10M
DEEP1OM
25
Speedup (%)
10.0
Speedup (%)
30-
2,5
Gorter
Sender
RCM
RFM
06-
Doyoutt Ind
Itut
Doybot 16)
Degpot
Recall@
Recall@100
SIFT10OM
DEEP10OM
Speedup (96)
Speedup (%)
20-
-07
Seetee
Sender
KCM
RMH
Degfort In)
DegSot I00
20
Degsort (uut)
Degiortenn TE11
Recall@
Recall@100
MNIST
GISTIM
10.0
Speedup (%)
10-
Speedup (%)
Orignad
Origial
-2.5
DugSart
Depfort 3el
Degiott 1o:1l
-50
hetdot
Depdont Sar)
-7.5
0.52
0.996
3,500
5.00
0.90
3.00
Recall@100
Recall@100
Figure 4: Effect of graph reordering on the query time vs. recall tradeoff. Reordering algorithms above the black line have faster query time than the original ordering. Algorithms below the line cause a slowdown. The speedup changes with the recall because the memory access pattern of beam search changes with the buffer size.
methods, including our techniques from Section 4 We do not use graph partitioning because such methods generate orders that too coarse accelerate cache access Lecuyer & Tabourier (2021). Additional details about baseline selection and memory layout are available in the supplementary materials and code documentation.
Datasets. We use large datasets that are representative of embedding search tasks. We perform experiments on datasets from ANN-benchmarks as well as 10M and 100M sized subsets of the SIFTIB and DEEPIB benchmark tasks. contains information about our datasets. In all of experiments, request the top 100 neighbors of a query and we report the recall of the top 100 ground truth neighbors.
Hyperparameters. For construction, HNSW requires two parameters: the maximum number of edges for each node (k:)) and the size of the beam search buffer (Ma) used to find the ke neighbors during graph construction. We set M. = 100 and construct indices for ke E (4, 8, 16, 32, 64, 96). From these options, we select the index with the best recall-latency trade-off (for recall > 0.95) and use that index for our graph reordering experiments. While it is true that the best hyperparameters change based on the recall, there typically a clear winner for the high-recall regime. To query the index. HNSW requires the beam search buffer size (M₂), which controls the trade-off between recall

---

Table 4: Each dataset has N entries and features ("vector size" bytes / row).
Table 5: Query time (T²) and speedup on SIFTIOM and Yandex IB T2I.
Dataset
N
d
vector size
Algorithm
To (Speedup %)
SIFTIOM
Yandex 10M
GIST
1 M
960
3.8 kB
SIFT
10 100 M
128
128 B
None
22.8 (0%)
16.3 (0%)
DEEP
10 100 M
96
384 B
Gorder
17.9(27%)
12.8 (22%)
MNIST
60
784
3.1 kB
Porder 16.8(36%)
12.4 (24%)
and query latency. We reorder the graph and issue the same set of 10K queries for each ordering.
When query the index, we vary the beam search buffer size Mg from 100 5000. We use window size w = 5 for Gorder and use the standard hyperparameter settings suggested by the literature for the other methods. For Porder method, we create the weighted graph by profiling on the first 1K queries from the test set and reporting results over 10K test queries.
6 Results
Query Time. Figure 4 shows the effect of graph re- ordering on the query time vs. recall tradcoff. We report the R100@ 100 recall, or the recall of the top 100 ground truth neighbors among the top 100 re- turned search results. For given recall value, we calculate the speedup as the ratio of average latency without/with reordering, where the averages are over 10K queries and 5 runs. Finally, we measured the 99th percentile of latency (P99) for the SIFTI00M dataset in Figure to ensure that our altered graph layout does not increase the tail latency. Gorder and RCM improve the P99 latency by at least 20% in the high-recall regime.
SIFT100M
Oignaa Gonder -..: REM
p99 Latency (ms)
10
0.52
3.00
Recall@ 100
New Layout Methods. We conducted a separate study to determine whether profile-guided reordering (Porder) can further refine the layout obtained using existing techniques. We construct a weighted graph by issuing 1000 queries and counting the number of times Tr that edge is traversed by the search algorithm. used in Equation 3 We found that Porder improved over Gorder by up 5-10% (Table We also implemented Corder as an ablation study to determine whether there is a practical performance gap between the upper bound (Gorder objective) and lower bound (Corder objective) of Theorem [ On SIFTIOM, we found that Corder was 4% worse than Gorder, leading us to conclude that Gorder obtains layout with near-optimal cache efficiency (i.e. the combinatorial term is small).
Figure 5: 99th percentile of latency (P99). RCM (-17%) and Gorder (-30%) outperform the original order.
The edges are weighted as + T. and
Reordering Cost and Cache Performance. Figure presents the cost of reordering the graph Reordering time scales well with the number of nodes N and the maximum degree ki of each node. Table D contains perf eache measurements and 3 contains cachegrind information for graph search over the SIFT100M dataset. Because these two experiments have similar results, we conclude that the mechanism by which Gorder and RCM improve latency is by reducing cache miss rate.
Prefetcher and Node Size Ablations. To isolate the effect of cache coherency from that of hardware prefetching, we turned off the LI/L2 hardware prefetcher. Without LI/L2 prefetching (but with TLB caching and L3 prefetch). we obtain speedups that are much smaller than when the prefetcher is active (-10% on MNIST, -5% on DEEPIOM and -5% on SIFTIOM), We also consider two equivalent versions of the SIFTIM dataset one where vectors are represented as 32-bit floats (512 bytes / vector) and one where vectors are represented as 8-bit integers (128 bytes vector). We use the same graph for each index and observe that larger vectors result in smaller speedup (average of 11 1% vs 19%). These results support the idea that prefetching and vector size play a substantial role in our latency improvement. See the supplementary material for detailed experiment results.

---

7 Discussion
Objective-based reordering algorithms such as Gorder, Porder and RCM are the most effective methods to accelerate near neighbor search, with typical speedup of 10% on small datasets (N < IM) and speedups of up to 40% on large datasets and the high-recall regime (Figure 4 Our theoretical and experimental results suggest that graph reordering should become standard preprocessing step to improve the query time. In practice, reordering only affects the representation of nodes in memory and does not change the recall, search algorithm, other properties of the graph index. Furthermore, reordering does not substantially inflate the index construction time and, using the theory from Section 4 we argue that Gorder does no harm under typical application scenarios.
Cost of Reordering. Many studies focus on applications such as PageRank, where the graph is processed small number of times to obtain an output. Such applications favor lightweight (but less effective) algorithms that obtain an end-to-end speedup. However, the production requirements of near neighbor search are exactly the opposite: single index may be queried millions of times over its life cycle. Therefore, the reordering cost is justified, especially since it is an order of magnitude smaller than HNSW construction for most datasets (Figure 3).
Benefits of Reordering, Reordering is an index-agnostic method to improve the performance of graph-based based near neighbor search. Because reordering depends on the node access pattern of beam search, which common to most algorithms, reordering is applicable to a wide range of practical search tasks. It should be noted that most real-world deployments function under strict latency requirements: a maximum search time of 20 ms a common constraint Nigam et al. (2019). A 20% improvement in search time allows the system to perform more sophisticated processing of the search results, operate at a higher recall or serve a larger collection embeddings.
What drives performance? A natural question is to ask what mechanisms drive the performance improvements seen in our experiments. Since data vectors are larger than single cache line, prefetching is likely responsible for many of the cache improvements seen in Table [] Reordering the graph improves the spatial locality of nodes, allowing the hardware prefetcher be more effective, as well as auxiliary data structures, such as visited lists and priority queues. Although auxiliary functions are only responsible for about 20% of the query time (Figure D. they represent nodes using only few bytes and therefore do fit into a single cache line. These structures benefit from concurrent loading as well as prefetching.
Limitations. It is possible that highly-engineerg implementation with software prefetching could have similar performance naive implementation that uses reordering. However, we believe that graph reordering is valuable even for tuned implementation. Studies show that both hardware and software prefetching work best on data that obeys the spatial locality principle Lee et al. (2012). and software prefetching comes at a high engineering cost.
Synergy with Algorithms and Production Systems. Reordering is likely exhibit synergy with recent K-NN algorithms. For example, partition- based search may benefit from reordering because recent algorithms for locality-sensitive hashing use k--N graph cuts to form data partitions Dong et al.) 2020)). Near neighbor graphs are also frequently combined with sample compression methods such as product quantization or other codebooks Jegou et al. (2010). Recent experiments with preprocessing transformations suggest that it is beneficial to perform the graph search on a subspace of reduced dimension Prokhorenkova & Shekhovtsov (2020). This could amplify the effects of graph reordering because a larger sub-graph can fit into the CPU cache for small vector sizes. Our experiments support this hypothesis, as we observe larger speedups for SIFT and DEEP than MNIST and GIST, which have a large per-sample storage cost. Finally, we expect our profile- -giided technique to be beneficial for near neighbor indices in production systems. It is common for production databases to periodically re- re-format the contents of the database according to recent statistics about access frequency and workload. Since reordering the index only requires a few minutes, we find it useful to dynamically adjust the memory layout when the query distribution changes.
Acknowledgements
This work was supported by National Science Foundation 18115, BIGDATA-1839) ONR DURIP Grant, and grants from Adobe, Intel, Total, and VMware. We also thank Senthil Rajasekaran for help with the formulation and proof of Lemma
10

---

References
Aumüller, M., Bernhardsson, E., and Faithfull, A. Amn-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020.
Balaji, V. and Lucia, B. When is graph reordering optimization? studying the effect of lightweight graph reordering across applications and input graphs. In 2018 IEEE International Symposium on Workload Characterization (ISSCC), pp. 203-214 IEEE, 2018
Beygelzimer, A., Kakade, S., and Langford, Cover trees for nearest neighbor. In Proceedings of the 23rd international conference on Machine learning, pp. 97-104, 2006.
Boytsov, L. and Naidan, B. Engineering efficient and effective non-metric space library. In Brisaboa, N., Pedreira, O., and Zezula, P. (eds.), Similarity Seurch and Applications, pp. 280-293, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. ISBN
Chan, T. M. Closest-pon proest-ppintttie problems simplified the ram. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 472-473, 2002.
Connor, M. and Kumar, P. Fast construction of k-nearest neighbor graphs for point clouds. IEEE transactions on visualization and computer graphics, 16(4):599-608, 2010.
Cuthill, E. and McKee, J. Reducing the bandwidth of sparse symmetric matrices. In Proceedings of the 1969 24th national conference, pp. 157-172, 1969.
De Melo, A. C. The new linux perf tools. In Slides from Linux Kongress, volume 18, pp. 1-42, 2010.
Dong, Y., Indyk, P., Razenshteyn, P., and Wagner, T. Learning space partitions for nearest neighbor search. ICLR, 2020.
Faldu, P., Diamond, J., and Grot, B. A closer look at lightweight graph reordering. In 2019 IEEE International Symposium Workload Characterization (IISWC), pp. 1-13. IEEE, 2019.
Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. Cache-oblivious algorithms. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 285-297. IEEE, 1999.
Frome, A., Corrado, G. S., Shlens, J., Bengio, S., Dean, J., Ranzato, M., and Mikolov, T. Devise: deep visual-semantic embedding model. In Proceedings of the 26th International Conference Neural Information Processing Systems-Voile Volume 2, pp. 2121-2129, 2013.
George, J. A. Computer implementation of the finite element method. Technical report, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, 1971.
Huang, P.-S., He, X., Gao, Deng, L., Acero, A., and Heck, L. Learning deep structured semantic models for web search using clickthrough data. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pp. 2333-2338, 2013.
Iwasaki, M. Pruned bi-directed k-nearest neighbor graph for proximity search. In International Conference on Similarity Search and Applications, pp. 20-33. Springer, 2016.
Iwasaki, M. and Miyazaki, D. Optimization of indexing based on k-nearest neighbor graph for proximity search high-dimensional data. arXiv preprint 181.001810.07355 2018.
Jafari, O., Maurya, P., Nagarkar, P., Islam, K. M., and Crushev, C. survey on locality sensitive hashing algorithms and their applications. arXiv preprint ar arXiv:2102.08944 2021.
Jegou, H., Douze, M., and Schmid, C. Product quantization for nearest neighbor search. IEEE Iransactions on pattern analysis and machine intelligence, 33(1): 2010.
Johnson, J., Douze, M., and Jégou, H. Billion-scale similarity search with gpus. arXiv preprint arXiv: 100.::770.87.333 2017.
Johnson, J., Douze, M., and Jégou, Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 2019.

---

Kusner, M. J., Sun, Y., Kolkin, N. I., and Weinberger, K. Q. From word embeddings to document distances. In Proceedings of the 32nd International Conference on International Conference on Machine Learning- Sooniing-Volumee Volume 37, pp. 957-966, 2015.
Lecuyer, Fabrice, M. D. and Tabourier, L. [re] speedup graph processing by graph ordering. The ReScience Journal, 7, 2021.
Lee, J., Kim, H.,, and Vuduc, R. When prefetching works, when it doesn't i, and why. ACM Transactions Architecture and Code Optimization (TACO), 9(1):1-29, 2012.
Levinthal, D. Performance analysis guide for intelr core (tm) i7 processor and intel xeon (um) 5500 processors. Intel Corporation, 2009.
Lowe, D. G. Object recognition from local scale-invariant features. In Proceedings of the seventh IEEE international conference on computer vision, volume 2, pp. 1150-1 157. leee, 1999.
Malkov, Y. A. and Yashunin, D. A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions pattern analysis and machine intelligence, 2018.
Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, Distributed representations of words and phrases and their compositionality. Advances in Neural Information Processing Systems, 26: 3111-3119 3119, 2013.
Naidan, B., Boytsov, L., Malkov, Y., and Novak, D. Non-metric space library manual. arXiv preprint arXiv: 05470, 2015.
Nigam, P., Song. Y., Mohan, V., Lakshman, V., Ding, W., Shingavi, A., Teo, C. H., Gu, H., and Yin, B. Semantic product search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2876 2885, 2019.
Ondov, B. D., Treangen, T. J., Melsted, P., Mallonee, A. B., Bergman, N. H., Koren, S., and Phillippy, A. M. Mash: fast genome and metagenome distance estimation using minhash. Genome biology, 17(1):1-14, 2016.
Prokhorenkova, L. and Shekhovtsov, A. Graph-based nearest neighbor search: From practice to theory. In International Conference on Machine Learning, pp. 7803-7813, PMLR, 2020.
Shakhnarovich, G., Darrell, T., and Indyk, Nearest-neighbor methods in learning and vision. IEEE Trans. Neural Networks, 19(2):377, 2008.
Wei, H., Yu, J. X., Lu, C., and Lin, X. Speedup graph processing by graph ordering. In Proceedings of the 2016 International Conference on Management of Data, pp. 1813-1828, 2016.
Zhang, Y., Kiriansky, V., Mendis, C., Amarasinghe, S., and Zaharia, M. Making caches work for graph analytics. In 2017 IEEE International Conference Big Data (Big Data), pp. 293-302. IEEE, 2017.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The "up to 40%" claim is backed up by results in Figure and Figure The theory is presented in Section
(b) Did you describe the limitations your work? [Yes] This is described in the discussion section.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We do not foresee any negative consequences from this work. This simply an implementation- level improvement
common algorithm.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We assume an initial state of the cache, and we analyze depth-first search because it is difficult to analyze beam search directly.
(b) Did you include complete proofs of all theoretical results? [Yes] The full proofs are in the supplementary materials.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL.? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In the supplementary materials.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [No] We report the average of 10,000 queries. Since we report the speedup
percentage, it is difficult to compute error bars. We do, however, show the 99th percentile of latency (shown in Figure 5 which is a stronger measure of variation than the standard deviation used to report error bars.
(d) Did you include the total amount of compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [Yes] This description is in the experiments section.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite ANN- benchmarks for the datasets.
(b) Did you mention the license of the assets? [Ys]] ANN-benchmarks is released under the MIT license.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] We include code, which is not yet released under any license.
(d) Did you discuss whether and how consent obtained from people whose data you's 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "cI6zBekkfvd", "reviewer": "Reviewer_kSKW", "summary": "This paper presents a formal analysis for the impact of graph reordering (i.e., ordering the in-memory storage sequence of graph node embeddings) on the cache efficiency of near neighbour searches using near neighbour graphs. The connection of the graph ordering (i.e., memory layout of the graph nodes) and the cache complexity is formulated, based on which the cache complexity of the Gorder (Wei et al., 2016) is analysed and two other graph ordering (Corder and Porder) are proposed. Experimental results on large real datasets confirm the effectiveness of the analysis and the importance of graph reordering for near neighbour search efficiency. ", "questions": "A lot of experimental results focused on Gorder (Wei et al., 2016). How will the results look like when Porder is also included in those experiments (Figures. 3&4, Tables 1&3)?", "limitations": "The paper included an interesting discussion on the results and limitations. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper has presented a solid analysis for the impact of graph reordering (i.e., ordering the in-memory storage sequence of graph node embeddings) on the cache efficiency of near neighbour searches using near neighbour graphs. \n\n2. Experimental results on large real datasets are presented, with an interesting discussion on the results. \n\n3. Source code of the paper is available. \n\nWeaknesses:\n1. The proposed method Corder is ineffective as discussed in the experimental results. Perhaps this method can be dropped to make room for adding more details on the experimental settings to the main content of the paper. \n\n2. The other proposed method Porder is only somewhat better than the existing method Gorder (Table 5).\n\n3. A lot of contents have been included as supplementary material, which makes the paper somewhat difficult to follow. \n\nTypo: \"degree-based groupingFaldu et al. (2019)\"; \"Studies show that Studies show that\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Sd1Zn-J9K4R", "reviewer": "Reviewer_Ewkj", "summary": "This paper proposes to use graph reordering to improve the cache locality of graph-based nearest neighbor search algorithms. An analysis is conducted to show why graph reordering works and the experiments show that graph reordering significantly improves performance.", "questions": "See weakness.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n1.\tGraph-based nearest neighbor search algorithms are very popular and graph reordering improves the performance of graph-based nearest neighbor search algorithms.\n\n2.\tAlthough the conditions are restricted, the analysis explains why graph reordering improves performance.\n\n3.\tThe profiling-based ordering scheme makes sense.\n\nWeakness\n\n1.\tThe authors should dig deeper to show why recording improves performance. Currently, the explanations are vague (e.g., due to software prefetcher and auxiliary functions). The authors may want to make them more specific by explaining how software prefetcher works or conduct some experiments to show where the reduction comes from. \n\n2.\tI believe that graph reorder works for graph-based algorithms in general. But it helps to show by experiments that graph reorder improves the performance for algorithms other than HNSW (e.g., NSG or NGT).\n\n3.\tThe legends in the figures are too small to read.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "L1s1q1hISTq", "reviewer": "Reviewer_Li81", "summary": "The paper studies practical performance of different methods for rearranging the node layout in the memory for graph-based approximate nearest neighbor search algorithms (HNSW specifically). It also proposes a simple modification of the existing methods based on query profiling. The paper claims to have up to 30-50% improvement in query latency on 100M datasets and is accompanied by code (though not clear if it is going to be released).", "questions": "I would recommend improving the code presentation and completeness. The approach is focused on hardware optimization, so having an exact working code seems to be essential for the further research from other teams.\n\nIt would be nice to check some of the assumptions of the paper, like that the speedup is from the hardware prefetcher. E.g. turning the hardware prefetcher off and/or experimenting with the size of the vectors. \n\nMisc: “Studies show that Studies show that” typo\nPlease use “nearest neighbor search index” or similar instead of \"near neighbor index\". \"near neighbor index\" is used in other contexts, and I was able to find the public version of this paper in google top results just by searching for \"near neighbor index\" .\n", "limitations": "I do not think there is any negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Simple change that is very likely to be agnostic to the type of the graph algorithm used.\n- Sizable gains from the algorithm on large datasets.\n- Source-code (hopefully will be released with the publication - not clear from the text).\n- Long discussions of the results.\n\nWeaknesses:\n- The paper does not have a clear description of the methods (no pseudocode or even text description of step-by-step actions). I guess the readers are suggested to follow the cited papers, but IMO there should be at least a sketch of the best solution.\n- The source of 1000 queries for POrder not discussed in the paper. Were they used from the train set or the test set?\n- There is no implementation of POrder in the code, which is confusing. The code also has bugs (e.g. nonexistent “-openmp” flag), it does not compile without fixing the dependencies (could had been fixed if you provide Dockerfile) and there are errors in its description.\n- Judging the code, the construction is done in a single thread. If index construction time provided in the paper is for this regime (which is not clear from the paper, but seems to be the case), it should be redone in the multi-threaded regime.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept