{'fraction_non_alphanumeric': 0.0363232023721275, 'fraction_numerical': 0.016139901610620663, 'mean_word_length': 4.91028577118391, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Speed-ANN: Low-Latency and High-Accuracy Nearest Neighbor Search via Intra-Query Parallelism

Nearest Neighbor Search (NNS) has recently drawn a rapid increase of interest due to its core role in managing high-dimensional vector data in data science and AI applications. The interest is fueled by the success of neural embedding, where deep learning models transform unstructured data into semantically correlated feature vectors for data analysis, e.g., recommend popular items. Among several categories of methods for fast NNS, similarity graph is one of the most successful algorithmic trends. Several of the most popular and top-performing similarity graphs, such as NSG and HNSW, at their core employ best-first traversal along the underlying graph indices to search near neighbors. Maximizing the performance of the search is essential for many tasks, especially at the large-scale and high-recall regime. In this work, we provide an in-depth examination of the challenges of the state-of-the-art similarity search algorithms, revealing its challenges in leveraging multi-core processors to speed up the search efficiency. We also exploit whether similarity graph search is robust to deviation from maintaining strict order by allowing multiple walkers to simultaneously advance the search frontier. Based on our insights, we propose Speed-ANN, a parallel similarity search algorithm that exploits hidden intra-query parallelism and memory hierarchy that allows similarity search to take advantage of multiple CPU cores to significantly accelerate search speed while achieving high accuracy. We evaluate Speed-ANN on a wide range of datasets, ranging from million to billion data points, and show its shorter query latency than NSG and HNSW, respectively. Besides, with multicore support, we show that our approach offers faster search latency than highly-optimized GPU implementation and provides good scalability as the increase of the number of hardware resources (e.g., CPU cores) and graph sizes.


INTRODUCTION
Nearest neighbor search (NNS) is a fundamental building block for many applications within machine learning systems and database management systems, such as recommendation systems [16], large-scale image search and information retrieval [41,49,59], entity resolution [31], and sequence matching [13]. NNS has recently become the focus of intense research activity, due to its core role in semantic-based search of unstructured data such as images, texts, video, speech using neural embedding models. In semantic-based search, a neural embedding model transfers objects into embeddings in R , where often ranges from 100 to 1000 and N ranges from millions to billions. The task then is to find the nearest embeddings for a given query. For example, major e-commerce players such as Amazon [58] and Alibaba [79] build semantic search engines, which embed product catalog and the search query into the same highdimensional space and then recommends products whose embeddings that are closest to the embedded search query; Youtube [15] embeds videos to vectors for video recommendation; Web-scale search engines embed text (e.g., word2vec [54], doc2vec [43]) and images (e.g., VGG [65]) for text/image retrieval [14,66]. We expect applications built on top of the embedding-based search to continue growing in the future, due to the success and continual advancement of neural embedding techniques that can effectively capture the semantic relations of objects. We also expect the objects to embed will grow rapidly, due to ubiquitous data collections, e.g., through phones and IoT devices.
Since the search occurs for every query, the latency and the accuracy (recall) of the search engine critically depend on the ability to perform fast near neighbor search in the high-recall range. Various solutions for approximate nearest neighbor search (ANNS) have been proposed, including hashing-based methods [2,3,17,33], quantization-based methods [23,35,72,73], tree-based methods [12,64,70], and graph-based methods [22,51,74]. Among them, graph-based algorithms have emerged as a remarkably effective class of methods for high-dimensional ANNS, outperforming other approaches for very high recalls on a wide range of datasets [7]. As a result, these graph-based algorithms have been integrated with many large-scale production systems [22,52], where optimizations for fast search and high recall are the focus of a highly active research area and have a clear practical impact.
To provide scalability, existing ANN search libraries often resort to coarse-grained inter-query parallelism, by dispatching each query to a core or even across different machines such that multiple queries can be processed simultaneously [11,22]. Although inter-query parallelism obtains impressive throughput improvements, it does not help reduce query latency. In particular, online applications often process each query upon its arrival and have stringent latency service level agreements (e.g., a few milliseconds). As the size of datasets grows rapidly, the increased latency of current graph-based ANN algorithms has been restraining ANN-based search engines from growing to large-scale datasets, especially for high-recall regimes. To provide relevant results with consistently low latency, in this work, we investigate the possibility of intraquery parallelism on individual nodes to meet latency goals.
Although graph-based ANN consists of primarily graph operations, simply dividing the work of graph traversal into multiple threads is insufficient for supporting efficient ANN search, as it cannot efficiently leverage the underline multi-core processors due to complex interactions between graph operations and the hardware threads and memory hierarchy. In our studies, the intra-query parallelism may sometimes hurt search efficiency, because the communication and synchronization overhead increases as we increase the number of cores, making it especially harder to achieve high efficiency.
In this work, we provide an in-depth examination of the graphbased ANN algorithms with intra-query parallelism. Through a series of experiments, we have identified that an intrinsic challenge of the graph search process lies in its long convergence stepexisting best-first search leads to long convergence steps and introduces heavy control dependencies that limit the upper bounds on speedup by using more cores, as predicted by Amdahl's Law. In our study, we find that, by enlarging the Best-First Search to Speed-ANN , the search process can converge in much fewer iterations, suggesting that the search process can achieve better overall performance by running individual queries with more hardware resources. However, exposing the path-wise parallelism also changes the search dynamics of queries, leading to additional challenges that may adversely affect search efficiency, which resides in the aspects of redundant computations, memory-bandwidth under-utilization, high synchronization overhead, and irregular accesses caused poor data locality.
Based on the insights from our analysis, we present Speed-ANN , a similarity search algorithm that combines a set of optimizations to address these challenges. Speed-ANN introduces three tailored optimizations to provide improved performance for graph-based ANN search. First, Speed-ANN uses parallel neighbor expansion to divide the search workload to multiple workers in coarse-grained parallelism. Among it, every worker performs its private best-first search in an asynchronous manner to avoid heavy global communication. Second, Speed-ANN employs a staged search scheme, which reduces redundant computations caused by over-expansion during a parallel search. Third, Speed-ANN is characterized by redundant-expansion aware synchronization to lazily synchronize among workers while still providing fast search speed high recall. Finally, Speed-ANN provides additional optimizations such as loosely synchronized visiting maps and a cache-friendly neighbor grouping mechanism to improve cache locality during parallel search. In summary, this paper makes the following contributions: (1) provides the first comprehensive experimental analysis of intra-query parallelism for ANN search on multi-core architecture and identifies several major bottlenecks to speedup graphbased approximate nearest neighbors in high recall regime; (2) studies how the characteristics of a query vary as the search moves forward from multiple aspects, e.g., by increasing the edge-wise parallelism degree and the dynamics in search queue update positions, which reveals the opportunities and challenges it brings; (3) introduces a search algorithm named Speed-ANN with novel optimizations such as staged parallel neighbor expansion and redundant-expansion aware synchronization that allow parallel search on graph-based ANN to achieve significantly lower latency with high recall on different multi-core hardwares. (4) conducts thorough evaluation on a wide range of real-world datasets ranging from million to billion data points to show that Speed-ANN speeds up the search by 1.3×-76.6× compared to highly optimized state-of-the-art CPU-based search algorithms NSG [22] and HNSW [52]. Speed-ANN sometimes achieves super-linear speedups in the high recall regime as the number of threads increases, obtaining up to 37.7× speedup over NSG and up to 76.6× speedup over HNSW when using 32 threads. Speed-ANN also outperforms a state-of-the-art GPU implementation and provides good scalability.

PRELIMINARIES 2.1 Approximate Nearest Neighbors
The nearest neighbor search problem in high-dimensional space is fundamental in various applications of information retrieval and database management. In this paper, the Euclidean space under the 2 norm is denoted by . The closeness of any two points 1 and 2 is defined by the 2 distance ( 1 , 2 ) between them [22]. The Nearest Neighbor Search (NNS) can be defined as follows [24]: Definition 1 (Nearest Neighbor Search). Given a finite point set of points in the space , preprocess so as to answer a given query point by finding the closest point ∈ .
Please note that the query point is not in the point set , i.e. ∉ . The above definition generalizes naturally to the Nearest Neighbor Search (K-NNS) where we want to find > 1 points in the database that are closest to the query point. A naïve solution is to linearly iterate all points in the dataset and evaluate their distance to the query. It is computationally demanding and only suitable for small datasets or queries without a time limit of response. Therefore, it is practical to relax the condition of the exact search by allowing some extent of approximation. The Approximate Nearest Neighbor Search (ANNS) problem can be defined as follows [24]: Definition 2 ( -Nearest Neighbor Search). Given a finite point set of points in the space , preprocess so as to answer a given query point by finding a point ∈ such that ( , ) ≤ (1 + ) ( , ) where is the closest point to in .
Similarly, this definition can generalize to the Approximate Nearest Neighbor Search (AKNNS) where we wish to find > 1 (a) Data points and a query point.   Circles are data points. The golden star is query target (not in dataset). Four red circles are its nearest neighbors. Graph-based ANNS builds a graph index on the dataset in 1c. The yellow circle is the starting point. Orange circles are visited vertices during the search via Algorithm 1.
where is the th closest point to .
In practice, determining the exact value of requires some hard efforts. Instead, we use recall as the metric to evaluate the quality of the approximation. A high recall implies a small , thus a good quality of the approximation. It is defined as the value of the recall. Suppose the approximate points set found for a given query is ′ , and the true nearest neighbor set of is , the recall is defined as follows [21]: For a particular recall target, i.g. 0.990 or 0.995, our goal is to make the query latency as short as possible.

Graph-based ANN Search
Various ANNS solutions have been proposed over decades, e.g., the ones based on trees [5], hashing [32], quantization [4], and graphs [22,51,74]. Recently, many experimental results [22,51] show that graph-based approaches usually outperform others, resulting in the best execution performance and recall. That is because graph-based approaches can better express the neighbor relationship, allowing to check much fewer points in neighbor-subspaces.
Graph-based ANNS relies on a graph structure as its index, in which a vertex represents a data point in the data set and an edge links two points as shown in Figure 1. A vertex 2 is called a neighbor of a vertex 1 if and only if there is an edge from 1 to 2 . Many prior efforts focus on constructing optimal graphs for efficient ANNS [22,52]-which is not the focus of this work. In contrast, this work is based on the state-of-the-art graph construction approach [22], and aims to parallelize ANNS itself with a thorough study of its bottleneck and a set of advanced techniques addressing these bottlenecks.
Given the graph-based index built ready, Best-First Search algorithm is widely used by many graph-based methods for searching nearest neighbors [6,18,26,29,38,51,52]. Given a query point and a starting point , the algorithm is to search for nearest neighbors to . In the first search step, it visits 's neighbors and computes their distance to respectively to choose the closest vertex or candidate, and the next search step starts from the chosen candidate from the last step. All visited vertices are recorded and kept in order according to their distance to . The search step stops when the first visited vertices do not change anymore, which are the final nearest neighbors. The time spent to find the nearest neighbors is the query's latency.

COMPLEXITIES IN GRAPH-BASED ANN SEARCH FOR OPTIMIZATIONS 3.1 Overview of Graph-based ANN Search
The search procedure in existing similarity graph algorithms, such as NSG [22] and HNSW [52], is a best-first traversal that starts at a chosen (e.g., medoid o random) point and walks along the edges of the graph while getting closer to the nearest neighbors at each step until it converges to a local minimum. Algorithm 1 shows its basic idea. In a similarity graph, nodes represent entities in a problem domain (e.g., a video or image in a recommendation system), with each carrying a feature vector. Edges between nodes capture their closeness relationship, which can be measured through a metric distance (e.g., Euclidean). There are a few main differences between the best-first traversal and classic BFS (breadth-first search) and DFS (depth-first search) algorithms. The first is an ordering-based expansion. During graph traversal, the algorithm selects the closest unchecked node , called an active node, and computes the distance of all neighbors of to the query with their feature vectors (Line 8-12), and only inserts promising neighbors into a priority queue as new unchecked candidates for future expansion. In this way, the search can limit the number of distance computations needed to converge to near neighbors. Second, different from the BFS and DFS, which traverse all the connected nodes, the best-first search converges when no new (unchecked) vertex can be found to update the priority queue, leading to a different number of convergence iterations (i.e., the number of while loop iterations in Algorithm 1) for different datasets and queries.

Complexities for Optimizations
The graph traversal process in similarity graphs shares some common complexities with traditional graph processing for performance optimizations, but it also owns some distinctive features.  Figure 2: The storage structure of the graph-based index. The graph topology is stored in compressed sparse row (CSR) format, and the data vectors are stored in consecutive arrays. However, no previous work has given a systematic examination of these complexities. Such knowledge is essential for optimizing similarity graph search, especially at a large scale.
Challenge I: Best-First Search (BFiS) takes long iterations to converge, resulting in a prolonged critical path with heavy control dependency. As Algorithm 1 shows, this search consists of a sequence of search steps (Line 5-13) in which the candidates in the current step are determined by the last step. Consider that ANNS usually queries for the top K nearest neighbors, requiring the first K elements in the priority queue to become stable. This state update usually converges slowly (e.g., > 400 search steps or convergence steps to find the 100-nn with 0.999 recall for a millionscale dataset SIFT1M), resulting in a long critical path of execution.
Challenge II: Limited edge-wise parallelism in traversal and memory bandwidth under-utilization. Beyond the aforementioned long convergence steps, it is possible to parallelize the neighbor expansion step (Line 8-12 in Algorithm 1) to reduce the execution time by dividing the neighbors into disjoint subsets and having multiple threads each compute the distance for a subset in parallel, which is called edge-wise parallelism. However, this parallelism strategy often achieves sub-optimal performance, because many similarity graphs have a small truncated out-degree on all nodes to avoid the out-degree explosion problem [22]. As a result, dividing the work across more worker threads would result in each thread processing only a very small number of vertices. Furthermore, edge-wise parallelism also adds synchronization overhead (e.g., at Line 14) to maintain an ordered expansion. Our preliminary experiment results in Table 1 show that the edge-wise parallelism strategy (e.g., running with 64 threads on five datasets) leads to less than 5% of the peak hardware memory bandwidth (∼80 GB/s), indicating a large performance potential remains yet to tap into. Challenge III: Strict expansion order leads to high synchronization cost. Existing similarity graph search algorithms use a priority queue to maintain the strict priority order of all candidates according to their distances to the queue point. Although it is possible in principle to use a concurrent priority queue that uses locks or lock-free algorithms to synchronize the candidate insertions (Line 14), we observe that the parallel scalability is severely limited by maintaining this strict order because each worker thread only performs distance computations for a few vertices.
Challenge IV: Poor locality brought by irregular memory accesses. Existing similarity graphs often store the graph index (e.g., in the compressed sparse row (CSR) format that contains a vertex  Figure 3: Overview of Speed-ANN . array and an edge array) and feature vectors (e.g., in one embedding matrix) separately in memory as different objects, as shown in Figure 2. There are two points in this design that lead to inefficiencies. First, the accessed nodes often reside discontinuously in memory, which leads to unpredictable memory accesses. Second, it requires one-level of indirection to access feature vectors, leading to difficulties for memory locality optimizations.

DESIGN OF Speed-ANN
Based on the observations from Section 4.1, we introduce Speed-ANN , a parallel search algorithm that exploits lightweight intraquery parallelism (i.e., path-wise parallelism and edge-wise parallelism) to accelerate the search efficiency of similarity graphs on multi-core CPU architectures. We first provide an overview of our architecture-aware design, and then we discuss technical details. Figure 3 depicts Speed-ANN 's overall design that addresses the challenges mentioned in Section 3 to perform an efficient similarity graph search. To reduce the long critical path dependency (Challenge I) and increase the amount of parallelism, Speed-ANN uses parallel neighbor expansion to deliver coarse-grained parallelism. Speed-ANN further introduces a staged search strategy to reduce redundant computations caused by over-expansion during a parallel search. To limit global synchronization overhead (Challenge III), Speed-ANN adopts redundant-expansion aware synchronization to adaptively adjust synchronization frequency. As such, Speed-ANN reduces the number of global synchronizations while still achieving high search accuracy. Besides, Speed-ANN uses loosely synchronized visit maps for lightweight communication and also performs the neighbor grouping technique to improve memory locality (Challenge IV).

Parallel Neighbor Expansion
Although it is challenging to parallelize the Best-First Search (BFiS) process due to its long critical path and limited edge-wise parallelism, the semantics of the algorithm does not seem to always require a strict order as long as the goal is to minimize the total search time of near neighbors. In this section, we exploit whether the search is robust to deviation from a strict order by allowing concurrent expansion of multiple active nodes. For practical similarity search, e.g., NSG and HNSW, there is no guarantee that a monotonic search path always exists for any given query [22]. As a result, the search can easily get trapped into the local optimum. To address this issue, BFiS may backtrack to visited nodes and find another out-going edge that has not been expanded to continue the   is specified by the xaxis. Although BFiS can find the first neighbor quickly, it still needs many steps to find all others.   Figure 4(a) illustrates a search path with backtracking. The search starts from vertex and calculates the distance (indicated by the number following the letter on each vertex) between the three neighbors of ( , , and ) and the query point. Because 's distance is locally the smallest, BFiS would select as the active node in the next step. However, given that further expanding no longer leads to a closer candidate, the search reaches a local minimum and performs a backtracking to the next promising candidate . The search process then may backtrack multiple times until it either finds the near neighbor (e.g., ) or exhausts the search budget.
Backtracking creates additional dependencies in BFiS process and increases the convergence steps to find near neighbors. However, many of these backtracking dependencies can be "fake" dependencies if we perform a parallel neighbor expansion, e.g., by expanding multiple active nodes concurrently, it is possible to shorten the convergence steps by starting early at one of those backtracking points. As an example, while it takes 11 steps to find the near neighbor in Figure 4(a), it only takes 5 steps in Figure 4(b) if we expand nodes F, G, J, M right after expanding their parent nodes.
Based on this insight, we introduce Speed-ANN . In this scheme, the priority order is relaxed such that in each step, top unchecked candidates are selected as active nodes for expansion instead of just the best candidate. Speed-ANN exposes hidden parallelism. The relaxation of the order enables two levels of parallelism: the path-wise parallelism   where multiple threads can concurrently expand the search frontier, and the edge-wise parallelism when expanding an individual active node. Moreover, instead of having a global queue to maintain strict expansion orders among all workers, each worker has a local priority queue, which allows a thread to exploit a small number of order inversions (i.e., allowing a worker thread to locally select and expand active nodes ahead of the global order), which can dramatically reduce communication, synchronization, and coordination between threads. Speed-ANN converges faster to near neighbors. One key benefit of Speed-ANN is that it significantly shortens the convergence steps compared to BFiS. Figure 5 shows the comparison results of convergence steps between BFiS and Speed-ANN . The results are measured on dataset SIFT1M using 10K queries with 0.90 recall target, and is set to 64. Speed-ANN takes on average 3.4, 5.0, and 5.4 steps to find the 1st, 50th, and 100th nearest neighbor, respectively, whereas BFiS takes 10.1, 69.4, and 88.1 steps, respectively. From another aspect, Speed-ANN takes much fewer steps to finish examining all the unchecked vertices in than BFiS, as shown in Figure 5b. Both results indicate that Speed-ANN has a much faster convergence speed than BFiS.
Tree-based Expansion View. Similar to the classical DFS/BFS, BFiS naturally introduces an expansion tree: the root node of the tree is the starting vertex in graph ; the children of a tree node (corresponding to a graph vertex ) are the unvisited neighbors of . The expansion of BFiS bears many similarities to DFS, as each time, it will expand only one leaf node. However, different from DFS, which expands the one with the most depth, BFiS expands the one which is closest to query . Thus, we have the same concepts of backtracking and Steps in BFiS.
The power of Speed-ANN is that it expands the leaves simultaneously of the tree, which are nearest neighbors of query among all the leaves of the current expansion tree. This effectively searches/extends paths in parallel instead of a single path (in BFiS). Thus, Speed-ANN can potentially reduce the total number of steps of BFiS by a factor of times, as for Steps, Speed-ANN can expand tree nodes/leaves. Further, due to the hardware capability, at the same time, Speed-ANN can process leaves/paths expansion as only what is in BFiS (one single leave or path expansion), leading to the low latency of query processing. We also note that the BFiS becomes a special case of Speed-ANN where = 1, and both parallelization are under Bulk Synchronous Parallel (BSP) model [68] though BFiS has rather limited parallelism to explore.

Staged Speed-ANN to Avoid Over-Expansion
Despite the faster convergence speed, intra-query parallel search incurs additional challenges in increased distance computations.   shows that to reach the same recall, Speed-ANN often leads to more distance computations than BFiS. Speed-ANN has more computations because parallel neighbor expansion allows a query to take fewer steps to reach the near neighbors by avoiding fake dependencies from backtracking but it also introduces more computations to explore additional paths. Furthermore, we observe that although the convergence steps continue to decrease with larger , the number of distance computations also increases dramatically, as shown in Figure 7.
When the number of parallel workers is large, the search speed of Speed-ANN might be sluggish because the over-expansion of neighbors can result in many redundant computations during the entire search process. To avoid unnecessary distance computations caused by over-expansion, we take a staged search process by gradually increasing the expansion width (i.e., M) and the number of worker threads every steps during the search procedure. The intuition is that the search is less likely to get stuck at a local minimum at the beginning of the search, so the best-first search with a single thread can already help the query to get close to near neighbors. As the search moves forward, it becomes more likely that a query will get stuck at a local minimum and requires backtracking to escape from the local minimum. Therefore, a parallel neighbor expansion search with a larger expansion width in later phases can better help reduce the convergence steps. We find that a simple staging function works well in practice: when the search begins, we first set a starting value and a maximum value for . The starting value is usually one, and the maximum value can be as large as the number of available hardware threads. Subsequently, for every steps (e.g., = 1) we double the value of until reaches its maximum. Figure 8a shows that by taking staged search, Speed-ANN reduces the amount of redundant significantly in comparison to Speed-ANN without staged search and leads to distance computations close to BFiS. On the other hand, Speed-ANN is able to converge as almost fast as Speed-ANN without staged search, as shown in Figure 8b. These results indicate that our staged search method still achieves fast convergence speeds without incurring too many distance computations caused by over-expansion through the parallel search on a large number of workers.

Redundant-Expansion Aware Synchronization
As mentioned in Section 3, yet another big performance bottleneck in intra-query parallelism resides in the synchronization overhead. Figure 9 shows how the global synchronization frequency influences the synchronization overhead (calculated by synchronization time divided by overall execution time) and the overall distance computations. All results in this figure return the same recall value. It shows that the synchronization overhead increases significantly when the synchronization frequency grows. We also find that order inversion (without enough synchronization) slows down the search convergence and results in growing distance computations (as shown in Figure 9). This is because, without enough synchronization, worker threads keep searching their own (unpromising) areas without benefiting from other threads' latest search results that may lead to faster convergence. This study demonstrates that a proper synchronization frequency is desired to achieve high system performance.
Measuring redundant expansion via update positions. To unleash the full power of multi-core systems, Speed-ANN performs a unique form of lazy synchronization so that worker threads do not need to synchronize at every search step in most cases. Especially, our synchronization scheme is redundant-expansion aware, which means instead of having a strict order through the entire convergence steps, we allow some relaxation of the order as long as each worker thread is still performing some effective search and the global order becomes consistent again after a large amount of redundant expansion has been detected. In this paper, we propose a new way to measure the effectiveness of intra-query parallel search based on the update positions of workers. When a worker expands an unchecked candidate, its neighbors are then inserted into the worker's local queue, and the update position is defined as the lowest (best) position of all newly inserted candidates. Thus, the average update position is the mean of all update positions of workers. Figure 10 demonstrates how an example query's average update position changes during the search steps without global synchronization. It shows that the average update position increases gradually to the local queue capacity and resides there to the end. When the average update position is close to the queue capacity, it indicates that most workers are searching among unpromising areas and cannot find good enough candidates to update their local results. Therefore, the average update position can be used as a metric to determine if all workers need to synchronize their local results to adjust the search order. We would like to note that there could be more than one metric to decide when to perform the lazy synchronization. We leave it as an open research question and more advanced methods might lead to better performance improvements. Algorithm 2 describes how to use the average update position as the metric to decide when to perform a lazy synchronization. Given the queue capacity and a position ratio , the threshold of the average update position to do synchronization is set as · . If the checker finds the average update position is greater than or equal to the threshold (Line 2), it returns true indicating a global synchronization in Algorithm 3. Empirically, the ratio is close to 1.0, such as 0.9 or 0.8. The input vector of all update positions is updated by workers regularly without locks. The return flag is only written by the checker who is assigned among workers in a round-robin manner.  Table 2 shows preliminary results about the performance comparison between adaptive synchronization and no-synchronization. No-synchronization means each thread performs its local search and only combines the results in the end. The results show that adaptive synchronization is able to improve search efficiency with fewer distance computations. Overall, the reduced synchronization and distance computation from our redundant-expansion-aware synchronization is especially helpful for parallel neighbor expansion on a large number of workers, because global synchronization across multiple threads is still expensive and not very scalable as the number of cores increases.

Additional Optimizations
Loosely Synchronized Visiting Map. There is one potential bottleneck to multi-threaded parallel scaling in Algorithm 3 on our target architectural platforms (multi-core systems). Consider visiting a neighbor of a candidate. This is typically after a check and then an update to a visiting map to ensure that a vertex is calculated once (Line 15-16). During parallel neighbor expansion, the visiting map is shared by all workers to indicate if a vertex has been visited. Since multiple threads may access the shared visiting map concurrently, locking or lock-free algorithms are required if we still want to ensure a vertex is visited only once. However, this approach involves a significant scalability bottleneck, because it leads to lock contention and sequentialization of updating the visiting map.  Figure 11: Example of neighbor grouping and hierarchical data storage. Vertices are ranked according to their in-degree. Vertices are first reordered into new ids according to their ranks. High ranked vertices are stored in an optimized index where every vertex's neighbors' data are stored in consecutive locations right after its own data to make expanding cache-friendly. Other low ranked vertices are stored in a standard index where the graph index and data vectors are stored separately.
We observe that the ANN search algorithm is still correct even if a vertex is calculated multiple times because the local candidates are guaranteed to be merged back to the global priority queue and the visiting map is also guaranteed to have eventual consistency the next time of global synchronization. Furthermore, by inserting memory fences, cache coherence further ensures that the updated visiting map is visible to other cores. Due to the potential outof-order execution in processors, modern multi-core processors provide fence instructions as a mechanism to override their default memory access orders. In particular, we issue a fence after a thread updates the visiting map to guarantee a processor has completed the distance computation of the corresponding vertex and has updated the visiting map (otherwise, there is no guarantee the updated visiting map is visible to other cores before next step of global synchronization).
By doing the loosely synchronized local search, we observe that the search algorithm only performs a very small percentage of additional distance computations (less than 5%) for SIFT1M (and similar for other datasets) with 8-way parallelism. This reduces the overhead from synchronization by 10% and allows us to avert the issue of non-scaling locking across the multi-threading search. This optimization was also considered by Leiserson and Schardl [44] (termed as "benign races") for their parallel breadth-first search algorithm. Furthermore, we use a bitvector to implement the visiting map instead of a byte-array. This optimization allows the cache to hold the largest possible portion of the visiting map and therefore improves the data locality for memory accesses.
Cache Friendly Neighbor Grouping. When a feature vector is loaded into memory for distance computation, modern CPU architectures actually automatically load vectors from nearby memory locations as well. Our neighbor grouping technique taps into this feature to mitigate the two levels of irregularity mentioned in Section 3.
First, Speed-ANN flattens the graph indices by placing the embeddings of neighbor vertices in consecutive memory, which would avoid one-level of implicit memory addressing and enables a thread to pre-fetch neighbor feature vectors once an active node is selected. Second, Speed-ANN also regroups nodes, such that vertices that are likely to be visited during the graph traversal are already pre-load into the CPU memory and cache. Together, these two optimizations increase the cache hit rate and help speed up the search process. One caveat of this approach is that it introduces additional memory consumption, because two neighbor lists may share the same vertex as a common neighbor. It is therefore may require more memory consumption than the original approach. To avoid increasing the memory consumption, Speed-ANN takes a hierarchical approach by regrouping only a subset of vertices. In particular, Speed-ANN divides a graph to a two-level index as shown in Figure 11, where only the top-level vertices have their neighbors flattened and stored in consecutive memory, and the bottom-level index stores other vertices using the standard structure. In this work, we explore two strategies to graph division: Degree-centric, which puts high in-degree nodes to the top-level of the indices. The intuition is that high in-degree nodes are more frequently accessed, and therefore improving their locality would benefit the most for the overall search efficiency. Frequency-centric, which exploits query distribution to figure out which nodes are more frequently accessed and puts those frequently accessed nodes into an optimized index. Section 5 evaluates both strategies and shows that Speed-ANN 's neighbor grouping strategy brings 10% performance improvements with selecting only 0.1% vertices as the top level for a dataset with 100M vertices.

EVALUATION
This evaluation proves that Speed-ANN can significantly reduce the ANN search latency with the proposed effective parallel optimizations.
Evaluation Objectives. This evaluation targets five specific evaluation objectives: (1) latency-demonstrating that Speed-ANN outperforms existing ANN search algorithms (NSG [22], HNSW [52], and a parallel version of NSG) by up to 76.6× speedup in terms of the latency without any precision compromise; (2) scalability-confirming that Speed-ANN scales well on modern multi-core CPU architectures with up to 64-cores; (3) optimization effectsstudying the performance effect of our key optimizations (parallel neighbor expansion, staged search, redundant-expansion aware synchronization, and cache friendly neighbor grouping) on overall latency, distance computations, synchronization overhead, etc; (4) portability-proving Speed-ANN has good portability by evaluating it on other multi-core CPU architectures; (5) practicabilityshowing that Speed-ANN is practical, applicable to extremely large datasets (e.g., bigann) with billions of points and outperforming an existing GPU implementation (i.e. Faiss) by up to 6.0× speedup with 32 CPU cores.

Implementation.
A natural question is if our implementations can leverage any existing graph libraries (e.g., Ligra [63]); however, it turns out this is very difficult due to multiple reasons: First, ANN algorithms do not pass messages between vertices. The computation only happens between a vertex and the query point. Second, ANN algorithms need to do computation with vector values. Third, ANN algorithms need to keep output results sorted. This requires extra efforts to maintain the results especially after synchronization between workers. Fourth, existing libraries' optimization techniques for general graph processing are usually not suitable for ANN algorithms. For example, Ligra [63] can switch between push and pull modes according to the number of active vertices. However, in ANN algorithms, the number of active vertices is capped by the expected output number of nearest neighbors, making the switching never happen. Besides, Speed-ANN runs in a semi-synchronous pattern with delayed synchronization among workers, which is different from the BSP model [68] with strict synchronization after every parallel step. Therefore, we have our high-performance implementation of those algorithms without using existing graph processing libraries. Our proposed ANN algorithms are written in C++ compiled by Intel C++ Compiler 2021.4.0 with "-O3" option. We use OpenMP 5.0 to handle the intra-query parallelism.
Platform and Settings. Unless otherwise specified, all major experiments are conducted on Intel Xeon Phi 7210 (1.30 GHz) with 64 cores and 109 GB DRAM (KNL for short). Speed-ANN sets the average update position ratio as 0.8 for SIFT1M, GIST1M, and SIFT100M, and 0.9 for DEEP10M and DEEP100M.
Datasets. This evaluation uses five datasets that are characterized in Table 3. SIFT1M and GIST1M are from the datasets 1 introduced by Jégou et al. [36]; SIFT100M is sampled from the SIFT1B (bigann) introduced by Jégou et al. [37]; DEEP10M and DEEP100M are sampled from DEEP1B 2 which is released by Babenko and Lempitsky [9]. These are common datasets for ANN algorithms evaluation [22].
Baselines. Speed-ANN is compared with two state-of-the-art sequential ANN search implementations, NSG 3 [22] and HNSW 4 [52]. NSG employs a search algorithm called Best-First Search, and HNSW uses its own best-first search algorithm corresponding to its hierarchical index. The hyperparameters used for building their indices are set as default values as long as the authors provided them. Otherwise, several values are tested and the best performance is reported.
For NSG, we use its optimized version of searching for SIFT1M, GIST1M, and DEEP10M, and its normal version for SIFT100M and DEEP100M because of memory limit. We also implement a Naïve Parallel NSG that parallelizes neighbor visiting during expansion.   Figure 12 compares the latency of Speed-ANN , NSG, and HNSW. Speed-ANN uses 32 threads while NSG and HNSW are sequential approaches. The query latency is the average latency of all queries, i.e., it equals the total searching time divided by the number of queries. All methods search the 100 nearest neighbors for every query (i.e.

Search Latency Results
= 100). The measure Recall@100 is calculated according to Formula 1 with = 100, which means the ratio of ground-truth nearest neighbors in searching results for each query. The value of Recall@100 is the average of all queries. All recalls mentioned in this section are Recall@100 if not specified. Figure 12 shows that Speed-ANN outperforms NSG and HNSW on all five datasets. Speed-ANN 's latency advantage increases with the growth of recall requirement, and it performs significantly better for high recall cases (e.g., from 0.995 to 0.999). For the cases of Recall@100 (R@100) being 0.9, 0.99, and 0.999, on all five datasets, Speed-ANN achieves 2.1×, 5.2×, and 13.0× geometric mean speedup over NSG, and 2.1×, 6.7×, and 17.8× over HNSW, respectively. As the recall becomes 0.999, Speed-ANN achieves up to 37.7× speedup over NSG on DEEP100M, and up to 76.6× speedup over HNSW on GIST1M. Speed-ANN achieves significantly better performance for high recall situations mainly because of two reasons. First, Speed-ANN 's parallel neighbor expansion effectively reduces convergence steps (comparing with NSG) because it is not easily trapped at a local optimum and can explore a local region more quickly than a sequential search. This is particularly critical for a large graph (e.g., DEEP100M) to achieve high recall, where a query can more easily get stuck at a local optimum. Second, Speed-ANN has better data locality from using aggregated L1/L2 cache provided by multiple threads, in contrast to sequential search where only private cache can be used. Further profiling results are provided in Section 5.3.
Impact on Tail Latency. For online inference, tail latency is as important, if not more, as the mean latency. To see if Speed-ANN provides steady speed-ups, we collect the 90th percentile (90%tile), Speed-ANN uses 32 threads. 95th percentile (95%tile), and 99th percentile (99%tile) latency from running NSG and Speed-ANN on SIFT100M and DEEP100M in Figure 13. The results show that while NSG's 99%tile increases significantly by 154% and 91% for SIFT100M and DEEP100M, respectively, the Speed-ANN 's 99%tile increases only by 31% and 19% over its average for SIFT100M and DEEP100M, respectively. Speed-ANN leads to a relatively smaller increase in tail latency presumably because intra-query parallel search is particularly effective in reducing latency on long queries.

Scalability Results
Scaling with An Increasing Number of Threads. Figure 14 reports the speedup of 1-to 64-thread Speed-ANN over 1-thread on three datasets for three selected recall (0.99, 0.995, and 0.999), respectively. It shows that this scalability increases as the target recall grows because of the increased distance computations that offers more parallelism opportunities. The geometric mean speedup of all datasets for the highest recall (0.999) is 9.6×, 11.1×, and 9.2× for 16-, 32-, and 64-thread, respectively. Speed-ANN only scales to 16 threads for SIFT1M because SIFT1M is too small without enough workload for more threads. Speed-ANN demonstrates superlinear speedup (up to 16 threads) for 0.999 recall on GIST1M and DEEP100M. This phenomenon will be further analyzed in Section 5.3. Speed-ANN does not scale well for 64 threads due to various reasons. For datasets with high dimensional vectors (e.g. GIST1M), 32-thread Speed-ANN has saturated memory bandwidth already. For others (e.g., SIFT1M, DEEP10M, and DEEP100M), extra distance computations of too many unnecessary expansions gradually dominate overall execution.
Scaling with An Increase of the Graph Sizes. Our experiments also evaluate the scalability with varied dataset sizes (DEEP1M, DEEP10M, and DEEP100M) for Speed-ANN , NSG, and HNSW, respectively. Figure 15 reports the latency results of Speed-ANN , NSG, and HNSW for the recall of 0.9, 0.99, and 0.999, in which Speed-ANN uses 32 threads. Speed-ANN constantly outperforms NSG and HNSW, and the heavier workload, the better performance Speed-ANN shows. More specifically, with the growth of dataset size, the speedup of Speed-ANN over NSG and HNSW increases. For example, when the recall is 0.999, the speedup of Speed-ANN over NSG grows from 5.9 to 27.8 when the dataset size changes from 1M to 100M. This trend becomes increasingly obvious with the growth of the recall. The results reflect that Speed-ANN is particularly effective and offers more speedups than existing search methods for larger graphs.

Analysis Results
This This config uses an exhaustive search to preprocess the dataset and obtain the proper synchronization settings. It should have the best latency performance, although requiring more than ten hours of tuning for the given dataset. (v) Speed-ANN -Adaptive: This is the configuration described in Section 4, which adopts redundantexpansion aware synchronization. For this comparison, we report results on DEEP100M dataset with 32 threads in Figure 16. Other datasets and threads show the same trend, thus we omit them due to the space constraint.
Effects on Latency. Figure 16a first reports the latency results of all five versions when we change recall from 0.90 to 1.00. Compared with NSG-32T, Speed-ANN -NoStaged has 4.9× speedup on average for all recall cases, because of the convergence iterations reduction from parallel neighbor expansion. Speed-ANN -Exhaust has an extra 1.5× speedup over Speed-ANN -NoStaged mainly due to its reduction in synchronization optimization. Speed-ANN -Exhaust achieves slightly better performance than Speed-ANN -Adaptive (e.g., 1.1× speedup). However, Speed-ANN -Adaptive does not require the expensive offline tuning process as Speed-ANN -Exhaust.
Effects on Convergence Iterations. Figure 16b profiles the convergence steps of the five parallel methods. Each point is averaged from all queries. NSG-32T results in the most steps of convergence; while Speed-ANN -NoStaged results in the fewest. All three versions of Speed-ANN result in comparable convergence steps to Speed-ANN -NoStaged that are much less than NSG-32T. This is Compt. Figure  18: Speed-ANN 's L1 misses, speedup over 1-thread, and distance computation w/ recall 0.999 on DEEP100M.

L1 Misses Speedup
because Speed-ANN -NoStaged employs a fixed and relatively large number of multiple paths throughout the searching, resulting in the most aggressive exploring. Speed-ANN -Adaptive and Speed-ANN -Exhaust adopt staged search, which slightly increases the convergence steps but significantly reduces distance computations. Meanwhile, Speed-ANN -NoSync suffers more divergence compared to Speed-ANN -Adaptive and Speed-ANN -Exhaust.
Effects on Distance Computation. Figure 16c profiles the number of distance computations for those five methods. Speed-ANN -NoStaged with a fixed value of = 32 leads to more distance computations than NSG-32T, Speed-ANN -Exhaust, and Speed-ANN -Adaptive to achieve the same recall (especially for low recall cases). While completely removing synchronization, Speed-ANN -NoSync has the most distance computations than others. However, as shown in Figure 16a, it still achieves lower latency than Speed-ANN -NoStaged because synchronization overhead can dominate the total search time when the number of parallel workers is large.
Effects on Synchronization Overhead. Figure 16d reports the execution time breakdown of our four approaches. It splits the whole execution time into three parts: Expanding part (Expand), Merging part (Merge), and Sequential part (Seq). Expand denotes the parallel phase of a query that workers expand their unchecked candidates. It consists of computing distances and inserting visited neighbors into their queues. Merge denotes the phase that workers merge their local queues into a global queue after they complete expanding. It reflects the major synchronization overhead. Other sequential execution of a search is included in Seq. All results are for recall 0.999. Figure 16d shows that redundant-expansion aware synchronization strategy effectively mitigates the synchronization overhead, allowing Speed-ANN -Adaptive to achieve a similar portion of synchronization overhead as Speed-ANN -Exhaust.
Effects of Neighbor Grouping. Our fully optimized Speed-ANN -32T also includes another optimization, i.e. neighbor grouping. Figure 17 shows that our two proposed strategies (degree-centric and frequency-centric) outperform no-grouping by up to 1.22× and 1.21× speedup, respectively, when we change the thread numbers from 1 to 64. This speedup mainly comes from the reduction of the last-level cache miss and TLB (translation lookaside buffer) cache miss. This profiling result is omitted due to the space constraint.
Super-linear Speedup Observation. Section 5.2 shows that Speed-ANN results in an interesting super-linear speedup (up to 16 threads) for 0.999 recall on GIST1M and DEEP100M. Figure 18 reports three profiling results, distance computations, L1 cache misses, and performance speedup for DEEP100M when changing the thread numbers from 1 to 64. The left x-axis shows the first two profiling   results while the right x-axis shows the last one. It shows that as we increase the number of threads, the L1 cache misses and distance computations first decrease and then increase. This causes the super-linear speedup for the cases whose thread numbers are less than 16. Distance computation shows this trend because: on the one hand, parallel neighbor expansion helps avoid the search from being trapped by local minimal candidates and quickly pick up promising searching paths for more nearest neighbors; on the other hand, too many exploring threads cause unnecessary expansion of non-promising candidates, increasing distance computations. L1 cache miss shows this trend because multi-threads increase the total size of L1 cache.

Portability Evaluation
To evaluate the portability, Speed-ANN is also tested on Intel Skylake architecture, Xeon Gold 6138 (2.0 GHz) with 20 cores and 187 GB DRAM (Skylake for short). For the sake of space saving, only results on DEEP100M are presented as other datasets show the same trend. Figure 19a compares the latency of Speed-ANN , NSG, and HNSW, in which, Speed-ANN uses 16 threads. It shows a similar trend as previous, i.e., Speed-ANN outperforms NSG and HNSW for all recall. For 0.9, 0.99, and 0.999 cases, Speed-ANN achieves 1.7×, 4.5×, and 12.9× speedup over NSG, and 1.3×, 5.3×, and 9.7× over HNSW, respectively. Figure 19b evaluates Speed-ANN 's scalability. Similarly, target recall 0.999 can achieve the best speedup over 1 thread, and speedup for 0.999 is 4.9× and 6.3× for 8 threads and 16 threads, respectively.

Practicality Evaluation
This section evaluates Speed-ANN 's practicality with two case studies: 1) evaluating it on very large datasets, SIFT1B (bigann) and DEEP1B that contain over 1 billion data vectors; 2) comparing it with a state-of-the-art GPU implementation.
Billion-Scale Datasets. This experiment is conducted on a particular machine with Xeon Gold 6254 (3.10 GHz) 72 cores and 1.5 TB memory because of the large memory requirement. Figure 20 compares the latency of Speed-ANN and NSG. Speed-ANN uses up to 64 threads, and the recall target is 0.9. When using 64 threads, Speed-ANN outperforms NSG with 11.5× and 16.0× speedup for SIFT1B and DEEP1B, respectively. As we increase the number of threads, Speed-ANN shows sub-linear speedup because of the wellknown NUMA effect (this machine has 4 NUMA domains). These results indicate the effectiveness of our method in speeding up the search process on billion-scale datasets.
Compare with a GPU Implementation. We also compare Speed-ANN with a GPU-based large-scale ANN search algorithm [39] in Faiss library [1]. The GPU experiments are conducted on an NVIDIA Tesla P100 with CUDA 10.2. Faiss is set to have one query in every batch, because we focus on reducing the online query latency to meet stringent latency requirement. Table 4 shows the latency comparison results on five datasets. Speed-ANN uses 32 threads on KNL. For the SIFT100M and DEEP100M, Faiss-GPU complains of out-of-memory errors. For other datasets, Speed-ANN outperforms Faiss-GPU with 1.4× to 6.0× speedup and much better recall, which indicates that Speed-ANN can effectively achieve faster search speed than GPU-based search algorithms on CPUs, which are often much cheaper than GPUs.

RELATED WORK
This section describes prior efforts closely related to our work.
Graph-based ANN. Navigating Spreading-out Graph (NSG) [22] is one of the state-of-the-art graph-based indexing methods. It is a close approximation of Monotonic Relative Neighborhood Graph (MRNG) that ensures a close-logarithmic search complexity with limited construction time. NSG (and many other graph-based methods [6,18,26,29,38,51,52], e.g., FANNG [29], NSW [51], and HNSW [52]) rely on best-first search to process queries. Other graph-based methods include [10, 11, 19, 34, 45-47, 60, 77]. In contrast to these efforts that mostly focus on indexing building, our work for the first time unveils the real bottleneck of intra-query graph search, and significantly reduces search latency (particularly for billion-scale graphs) with multiple advanced architecture-aware parallel techniques.
Non-Graph based ANN Methods. Hashing-based methods [2,3,17,33] map data points into multiple buckets with a certain hash function such that the collision probability of nearby points is higher than the probability of others. Quantization-based methods [23,35,70,72,73] (e.g., IVF [36], and IMI [8]) compress vectors into short codes to reduce the number of bits needed to store and compute vectors. Faiss [39] is implemented by Facebook with produce quantization (PQ) methods. Tree-based methods (e.g., KDtree [64] and R* tree [12]) hierarchically split the data space into lots of regions that correspond to the leaves of a tree structure, and only search a limited number of promising regions. Flann [55] is a library based on KD-tree. Graph-based methods have been proved to outperform these non-graph-based methods by checking fewer data points to achieve the same recall [7,20,22,46]. Another line of work that is closely related to Speed-ANN is to accelerate ANN search by varied accelerators, e.g., FPGA [75] and GPU [39].
Parallel Graph Systems. Many graph engines and frameworks have been developed in the past decade. Some of them are sharedmemory, focusing on processing in-memory datasets within a computation node, e.g., Galois [57], Ligra [63], Polymer [76], Graph-Grind [67], GraphIt [78], and Graptor [69]. Some are distributed systems, e.g., Pregel [50], GraphLab [48], and PowerGraph [25]. Some efforts focus on out-of-core designs (e.g., GraphChi [42] and X-Stream [61]) and process large graphs with disk support. Many graph frameworks are also on GPUs, such as CuSha [40], Gunrock [71], GraphReduce [62], and Graphie [28]. These graph systems are either based on a vertex-centric model [50] or its variants (e.g., edge-centric [61]). These models are in the strict BSP model [68]. Different from them (and other asynchronous graph traversal efforts [27,28]), Speed-ANN uses delayed synchronization that is in the spirit of stale synchronization [30] where workers are running in an asynchronous fashion before synchronization, which makes it possible to retain high parallelism and also a low amount of distance computations. Moreover, as aforementioned in the implementation, due to the uniqueness of ANN, it is challenging to migrate many of these system designs to Speed-ANN directly.
Generic Search Schemes. Many efforts aim to parallelize various search schemes (e.g., BFS [63], DFS [56], and Beam search [53]). Although Speed-ANN 's parallel neighbor expansion design is inspired by prior parallel search algorithms on graphs, our work has a very different focus and aims to: 1) identify that ANN's convergence bottleneck comes from the fact that ANN requires to find many targets that may be (or not be) present in the graph-a search scenario that is very different from many previous graph search problems; 2) several optimizations specifically tailored for reducing the number of distance computations and synchronization overhead from parallel neighbor expansion, such as staged search and redundant-expansion aware synchronization.

CONCLUSION
This work looks into the problem of accelerating graph-based ANN search on multi-core systems, performing comprehensive studies to reveal multiple challenges and opportunities to exploit intra-query parallelism for speeding up ANN search. Based on the detailed performance characterization, we propose Speed-ANN , a similarity search algorithm that takes advantage of multi-core CPUs to significantly accelerate search speed without comprising search accuracy. Speed-ANN consists of a set of advanced parallel designs, including parallel neighbor expansion, staged search, redundantexpansion aware synchronization, loosely synchronized visit map, and cache friendly neighbor grouping, systematically addressing all the identified challenges. Evaluation results show that Speed-ANN outperforms two state-of-the-art methods NSG and HNSW by up to 37.7× and 76.6× on a wide range of real-world datasets ranging from million to billion data points.