{'fraction_non_alphanumeric': 0.03423063300106259, 'fraction_numerical': 0.005262358953600162, 'mean_word_length': 4.624217416050086, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Similarity search on neighbor's graphs with automatic Pareto optimal performance and minimum expected quality setups based on hyperparameter optimization

This manuscript introduces an autotuned algorithm for searching nearest neighbors based on neighbor graphs and optimization metaheuristics to produce Pareto-optimal searches for quality and search speed automatically; the same strategy is also used to produce indexes that achieve a minimum quality. Our approach is described and benchmarked with other state-of-the-art similarity search methods, showing convenience and competitiveness.


Introduction
The proximity search problem can be described in terms of metric spaces which have a solid theoretic base. This abstraction allows the problem to be applied to a wide variety of fields like Statistics, data mining, pattern recognition, multimedia information retrieval, machine learning, bioinformatics, and others [1]. The problem definition is succinct, given a metric space (U, d) and a subset S = {s 1 , . . . , s n } of U , called the database, the problem of similarity search is how to preprocess S to find objects close to a query q for every possible q ∈ U under metric d. The objects close to a query q can be defined by B r (q) = {x ∈ S | d(x, q) ≤ r} if r is given or knn(q) which contains the k nearest neighbors of q in S, if the number k is given. In this work, we focus on the latter.
Finding the knn can be solved by brute force by simply evaluating the entire dataset looking for the nearest neighbors. When the database is so extensive, this naive solution takes too much time to be useful. In many problems, it is reasonable to sacrifice the exactness of the search in order to boost its speed.
In these scenarios, the recall is often used to measure the quality of the search.
The data structure produced by preprocessing the database is called the index. It is possible to create an index that enables searches with high recall scores for a simple database. The complexity of a database can be measured by its intrinsic dimension which can be observed as a high-concentration around the mean of all paired distances [2]. It is well known that the higher the intrinsic dimension, the harder it is to build an index that will produce searches with high recalls. This phenomenon is known as the curse of dimensionality.

Related work
Locality Sensitive Hashing (LSH) is among the most well-known techniques for approximate similarity search. It was introduced in [3], with many follow up work as in [4,5,6]. An LSH method defines a set of ad-hoc hashing functions that partition the database with the property that close elements of S are mapped (with high probability) to the same bucket and far away elements are mapped (again, with high probability) to different buckets. In this way, the search can be done only on the most promising buckets avoiding unnecessary comparisons.
A different approach is made by methods that use a small collection of elements of the metric space (often called references) to project each element of the database to an alternative space. In particular, a family of methods based on the rank of references as perceived by objects has been proved to be of use in high dimensional datasets [7]. The approach can also be applied to large datasets if each object focuses on the k nearest references since an inverted index or a trie can accelerate the searches. Some examples of this method are CNAPP [8], PP-Index [9], MIF [10], and the quantized permutations [11]. The structural similarity was systematically explored in [12], adding several indexes to the list. Also, a detailed exploration on the choice of the references is on [13].
A popular approach for finding the elements of a database that produce the higher inner product to the query is the quantization method [14]. These methods use two main strategies. On the first hand, they partition the space to reduce the computational cost of solving queries. The partition is usually in buckets, such that the algorithm that solves a query can discard most buckets, and only a few promising buckets need to be evaluated. The second technique quantizes the data to produce faster (and not exact) product comparisons. The quantized data is more compact, improving the computation times due to the memory hierarchy.
On [15] the authors presented SCANN, a new method based on optimizing a loss function for quantization methods that takes into account the dot product of the elements. Points with higher dot products with the query set are preferred when minimizing the loss function. In the experiments, the authors showed that the proposed loss achieves better recall and inner product value estimation when compared with losses that focus only on minimizing the reconstruction error, as other product quantization methods do.

Neighbor graphs
When the database is transformed into a graph, where edges reflect metric space's distances, the search can be done by navigating the nodes using the edges such that the distance to the query gets reduced on each step. The most popular algorithm for navigation is the greedy search, where the next path is the immediately most promising. On [16], Fu et al. used this search algorithm on an approximation of the graph presented in Spatial Approximation Tree (SAT) [17]. The approximation is made with a starting nearest neighbor graph produced by methods like NNdescent (see below), and then it improves it by taking the new neighbors using the graph from SAT. Using this graph, they created the NSG index, where they found empirically that the search time is close to O(log n).
The DISK-ANN [18] is an index designed to be stored in an SSD, which means that the number of accesses is minimal (like a dozen). The authors used a graph-based index for doing the searches. They created the graph to find the nearest neighbor using the greedy search algorithm. They used a similar idea of the Spatial Approximation Tree (SAT) [17]; the algorithm was modified to discard space's regions in the form of hyperbolas instead of hyperplanes. The DISK-ANN is built on SSD's clusters, where each element in the database is assigned to the closest clusters. The distance comparisons are approximated using quantization techniques [14].
In [19], Iwasaki presented the case where an NNG (Nearest Neighbor Graph) with more edges is going to be bigger, and the searches are going to be slower.
That is why they developed a method to prune some of the edges. First, they showed how to get a bidirectional graph from a directed one. They add the edges in the other direction, and if the number of edges surpasses a limit, they remove the longest edges. That is because, the author said, long edges do not contribute to finding the actual nearest neighbors. This strategy is used over an approximate NNG to create NGT-PANNG where all the searches start at the same initial node. Latter, in [20] Iwasaki et al. paid attention to both the indegree and the outdegree of the nodes in the graph since they found out that, given an NNG, if the edges on the nodes with an outdegree of 40 are reversed, the query time is reduced. The authors presented a method to adjust the indegree and the outdegree for each node. Also, they presented a path adjustment where they removed shortcuts if there is an alternative path of two nodes and these two nodes are shorter than the edge in question. In addition, they showed how to dynamically adjust the indegree and outdegree during search time to let the user decide the trade-off between precision and speed.
In [21], Dong et al. presented NNdescent, a new heuristic for constructing an approximated NNG based on the observation that a neighbor of a neighbor is also likely to be a neighbor. This principle applies to metric spaces that are growth restricted, that is, there should exist a constant c such that |B 2r (x)| ≤ c|B r (x)| for all x ∈ S. The heuristic to find the nearest neighbors is as follows. First, a coarse approximation of the nearest neighbors for every x, B(x) is created from k random elements. The next steps are going to produce better approximations to B(x) by exploring the neighbors of every y ∈ B(x) (including the reverse neighbors). The growth-restricted property, together with independence assumptions, guarantee that the radios of every B(x) will be reduced by half on each iteration. This process ends when convergence. In the end, the NNG is going to be a list of all the approximations B(x) of the real neighbors for every x ∈ S.
An alternative approach is made by the Navigable Small World (NSW) index [22]. The core idea is to create a graph of k approximate nearest neighbors and use it to search. The search procedure greedily navigates the graph following those nodes that minimize the radius of the result set populated as the algorithm navigates the graph. The graph is constructed with the search algorithm since inserting the ith element implies searching nearest neighbors in the previously indexed i − 1 elements. The rest of this section reviews the algorithm and some variants used here.
The NSW construction requires a distance function dist and a database S = u 1 , u 2 , · · · , u n , S ⊂ U . The core idea is to create the search graph (S, N ), where vertices are the objects of the dataset and the transition function N represents the set of edges. That is, N u is the adjacency list of u. The construction is incremental using the following rules: • The graph is empty, ({}, {}) and adds u 1 : the graph is updated as ({u 1 }, {u 1 → ∅}) • The graph (S (i−1) , N (i−1) ) is not empty and adds u i (the ith element): the graph is then updated to (S (i) , N (i) ) where S (i) = S (i−1) ∪{u i }. To update the neighborhood function, we firstly compute the approximate nearest neighbors knn(u i , S (i−1) ) using the search algorithm on (S (i−1) , N (i−1) ).
The new N (i) is defined as {u i → knn(u i , S (i−1) )}∪N (i−1) but also adding u i as neighbor to all N (i−1) v for v ∈ knn(u i , S (i−1) ), i.e., adds u i as reverse neighbor into the adjacent list of its nearest neighbors. The number of neighbors k is a construction parameter.
• Neighborhood reduction: In [23] the set of nearest neighbors knn(u i , S (i−1) ) is also reduced using a Spatial Approximation Tree (SAT) step [17], i.e., let X = knn(u i , S (i−1) ) so X = (x 1 , . . . , x |X| ) are the ordered neighbors of u i , the SAT reduced set X SAT centered in u i is constructed incrementally as X SAT = {x 1 } and then, for j = 2 to |X|, x j ∈ X SAT if there is no other object in the current X SAT that is nearest to the center object u i , i.e., This produces smaller neighborhoods that are shaped by the data's distribution (the X SAT will stop growing when the centered object is covered an there is no other object that can be inserted into it) instead of a given parameter.
• Neighborhood size k: instead of specifying a fixed number, as in the NSW and HNSW [24], we use the variable strategy presented in [23], where a logarithmic neighborhood size is used, i.e., k = log b (n) . In this approach, the logarithmic base b > 1 is used, and it is intended to control the memory of the index. In particular, we search for logarithmic neighborhoods (1 < b ≤ 2) and then apply SAT reductions to obtain competitive indexes regarding memory, search time, and quality.
Please note that the construction algorithm is tightly coupled with the search algorithm. The nearest neighbor query knn(q, S) is solved by a search algorithm.
In particular, the NSW is an iterative procedure starting at a random point u and greedily navigating the graph using its neighborhood to reduce the radius of the kth approximate nearest neighbor until it is impossible to improve. The procedure is repeated several times to improve the result set, i.e., the number of repetitions is a hyper-parameter. The HSNW [24] improves the algorithm introducing a hierarchical structure to navigate the graph more efficiently, in contrast, the construction and searching algorithms becomes more complex.
Our previous work [23] uses a Beam Search (BS) variant for searching. The BS is a one-pass population-based algorithm where its main hyper-parameter is the size of the population bsize; the population is called the beam. Another hyperparameter used in the same work is the initial population size ssize, typically larger than the size of the bsize. The algorithm navigates the graph tracking best known bsize items; these elements are refined while revising each note and are also used to guide the navigation. The result set is refined during the whole process; Section §3 details the algorithm along with our new proposals.

Overview
This section describes the similarity search problem and surveys the related literature. The rest of the manuscript is organized as follows. Section 2 describes our methodology and benchmarks. Section 3 revisits the similarity search index based on the Beam Search metaheuristic; it covers both our searching and construction contributions based on automatic tuning of hyperparameters. The parameter space used for our automatic tuning is described in detail in Section 4.1; this section also covers our three error functions used in the optimization. Section 5 characterizes and compares experimentally our contribution and state-of-the-art alternatives. Finally, our manuscript is summarized, and a list of future research lines is also discussed in Section 6.

Our contribution
This manuscript introduces several improvements to the BS algorithm: a new search hyper-parameter ∆ that can be used effectively to trade speed and quality of the searches, automatically determine search hyper-parameters using meta-heuristics, in particular, we use the same Beam Search algorithm used for searching and a genetic-based algorithm to perform this hyper-parameter optimization task. Using this framework, we propose three different optimization strategies: Pareto-recall, Pareto-radius, and Min-recall. The first two aim to find the best trade between quality and search speed, and the second one is the best trade ensuring a given minimum quality. Finally, the construction algorithm is also modified to take advantage of these strategies and keep the number of hyper-parameters low without compromising speed or quality.

Methodology
Our auto-tuned algorithms are motivated by experimental observations, and therefore, we will describe and characterize our algorithms using experimental evidence. We also compare our approach with state-of-the-art methods using a similar methodology. Table 1 lists the set of benchmarks and their characteristics such that they contextualize our experimental results.
Our cost-measuring methodology consists of various benchmarks that compare search and quality of the result set, measured as recall, the time costs in seconds for the construction and the search time, 1 and finally, we also report along with the manuscript, we present recall scores as the macro-recall of all queries in a benchmark, i.e., the mean of all recall values per query. We fixed k = 32 for all our experiments, and our gold standard was computed using an exhaustive evaluation.
We index a dataset (train partition of size n) and measure the performance in a set of queries (test partition of size m). Please ignore the abuse of train and test terminology, but it helps clarify our methodology. We never touch the test partition during the indexing phase and also never touch the test while optimizing hyper-parameters.
We selected our benchmarks to be public and its measures used in both real applications and research works. We use the last seven datasets of the table to characterize our methods; these datasets range from close to 300K (Lastfm-300K) objects to close to 10M objects (DeepImage-10M). The query sets range from one thousand objects (GIST-1M) to 50K queries (Lastfm-300K).
Our benchmarks are vector datasets using different dimensions, ranging from 65 (Lastfm-300K) to 960 (GIST-1M). While our methods are general enough to work with other representations and distance functions, we use benchmarks that work under L 2 and cos distances. Among the seven characterization datasets, two of them (Twitter-2M and WIT-300K) were introduced by us. 2 Our methods never touch test partitions during the indexing procedure, but we also show that the empirical observations of algorithms and meta-heuristics still apply on two samples of 1 and 100 million datasets of the so-called BigANN dataset, see Table 1. These datasets are not observed during the characterization process. They are used as an experimental verification that our methods apply for other datasets with at least an order of magnitude larger than the rest of our benchmarks.

Revisiting beam search algorithm over neighbor graphs
We use the Beam Search (BS) algorithm as the basis for our contribution; see our previous work [23]. Alg. 1 details our new approach, which is a simplification of the previous algorithm and also provides support for the new parameter ∆.
The BS algorithm starts populating a priority queue R, which will be the final approximation of the k nearest neighbors when the algorithm finalizes. Line Require: The distance function dist, the search graph G = (S, N (S)), the query q, the number of neighbors k, and the hyper-parameters: the beam size bsize, the expansion factor ∆, and the number of maximum visits maxvisits. Require: Define objective function as fitness(u) = dist(q, u) for the similarity search task. Ensure: The result set R containing k approximate nearest neighbors of q. initialize B and R as priority min-queues of size bsize and k, respectively.
Alg. 1 presents several changes with respect to that found in [23]. Firstly, it was simplified and now we use a fitness function instead of dist evaluations.
Secondly, it uses the ∆ factor that controls the population of the beam B; ∆ = 1 is equivalent to the original algorithm. Thirdly, we introduced the maxvisits parameter that provides a mechanism for early stopping the search, a property needed for fast exploration of hyper-parameter spaces; maxvisits = |S| reproduces to the original behavior.
Our algorithm has several requirements, more detailed: • The fitness : U → R + function to be minimized.
• fitness(u) = dist(q, u) for finding nearest neighbors of q, both q and u are valid object.
• The N u set containing the neighborhood of u (linked vertices in the graph).
• An initialization process for the result set (line 4), our similarity search procedure uses a static sample of objects of S; the sample is updated on exponential steps while inserting elements with the construction process.
• Priority queues of maximum length k (p-queue for short) store pairs R + × U .
One main piece of our algorithmic design is the p-queue, a min-max priority queue that limits its maximum size. Proper implementation and analysis are beyond the scope of this manuscript. However, the p-queue R has the following operations and properties: • The min(R) and max(R) functions defined as the minimum and maximum fitness values in R.
• The argmin(R) function is defined as the object associated with the minimum fitness in R.
• The popmin(R) and popmax(R) functions remove the pair associated respectively with the minimum and maximum fitness values in R, both return the removed object.
• It accepts adding pairs (fitness(u), u) if fitness(u) ≤ max(R) or |R| < k, for k being the maximum size of R.
• If a pair (fitness(u), u) is accepted for insertion and |R| = k the queue's size must remain |R| = k after the operation, e.g., applying popmax(R) before the actual insertion.
Our implementation consist of two arrays sorted by priority, i.e., solves min, max, argmin in O(1) time. We also use a floating pointer for tracking minimum value (popmin and popmax in O(1) time). The insertion algorithm is simple, a key-value fast insertion-sort-based algorithm for adding accepted pairs. Nonetheless, it takes advantage of the expected fitness values distributions, i.e., new fitness values will not achieve insertions since new probes will likely not improve the result set. The p-queue allows describing our search algorithm in simple terms.

Construction algorithm
This manuscript modifies the searching algorithm to support new hyperparameters and modifies the construction algorithm to reduce user intervention in the tuning process. Here we revisited the construction algorithm, using as starting point the algorithm and modifications listed in §1.2. For this matter, we report the following improvements: • An automatic hyper-parameter tuning based on the beam search algorithm, we define a search space and three ad-hoc error functions.
• A strategy to adjust hyper-parameters that supports incremental construction.
• A parallelized construction algorithm that takes advantage of modern multi-core architectures.
These modifications are compared with state-of-the-art indexes in the experimental section.

Hyperparameter optimization
Our search algorithm introduces the ∆ parameter, which allows controlling the graph's exploration. We also kept the bsize, limiting the population's size in the queue that the search process will visit. These hyperparameters must be adjusted to take advantage of the algorithm for a given task. This problem is common to any search index, and it is a barrier that limits the broad usage of efficient algorithms. We propose an online model selection procedure that optimizes the hyper-parameters by reducing a given error function. The optimization is performed in the same terms as our search graph; we use the beam search algorithm on a specially defined graph over a space of configurations (bsize, ∆) pairs. The error function to be minimized is the objective of any search algorithm: speed and recall. The model selection procedure is detailed in §4.1, where the configuration space is explained, and the error functions are also introduced.

Maintaining hyper-parameters
The incremental construction of the search graph allows the index to solve queries at any time. However, the hyper-parameters selection is made before the index's construction, and its effectiveness is tested after the build. Thus, the requirements at any construction stage could be quite different, and setting hyper-parameters that will work on large datasets may result in higher construction times. In this sense, we run a hyper-parameter optimization log b n for a dataset of n objects, in particular, we adjust parameters when log b i + 1 = log b (i + 1) . Moreover, we use the same policy for computing the initial approximation of the result set for the beam search, see line 4 of Alg. 1. Instead of our previous approach, i.e., initializing the result set with a random sample, here we select a set of objects where for each pair of elements u, v on it we ensure that N u ∩ N v = ∅. We use a logarithmic sample size, log b i , to simplify the selection of parameters. The cost of these logarithmic adjusts, and the computation of the initial approximations is amortized effectively with the entire construction cost. The number of tuning processes is also enough to impact the results. We verified these claims experimentally in §5.

Taking advantage of multi-threading architectures
We use a parallel algorithm to reduce construction times. We preserved the incremental construction since it can be of interest on many applications domains to have a fully functional index at any construction stage. We tackled the parallelism using block processing; that is, we select at most block_size items that are inserted at a time. The algorithm is quite similar to the original one, see §1, yet we add some requirements: • If the graph is empty or contains less than block_size elements, then a sequential insertion is made.
• Given the graph (S (i) , N (i) ) and a block of block_size elements. For each u in the block, we search knn(S (i) , u), searches are performed in parallel.
The neighborhood N u is created; please recall that the SAT algorithm is also applied to reduce the set of approximate nearest neighbors. Note that the computations made for u can be performed using the same thread.
Once all searches and direct neighborhoods are computed, the reverse connections are then performed in another block of threads to avoid possible data races when searching. In this sense, we also lock N v , v ∈ S (i) , since each v can be in more than one set of nearest neighbors in the block. The new graph is then defined, including all items in the block.
We tested the parallel block size and found that it is enough to select it several times larger than the number of available threads. Small block sizes are less effective than larger ones until it converges when block sizes are set to several thousand elements. Nevertheless, if the block size is too large, then the effect of ignoring elements in the same block may be noticed. We fix the block size to 1024 since our experiments indicate that this value is good enough to avoid a noticeable quality's impact and also being after the faster growth rate in the Nonetheless, all experimental results presented in the rest of this document argue its viability. We calibrated block_size using the Glove-400K dataset in our

Hyperparameter optimization with the Beam Search
It is well-known that there is a trade-off in metric search algorithms and their associated indexes; it is hard to obtain high-quality, high-speed searches and also keep low memory requirements. Fine-tuning search algorithms for real datasets is a computationally expensive task, not to mention the time and the stepped learning curve required by the people doing the job.    It is worth mentioning the hyperbolic shape in Figure 1 curves; please recall that points closer to the origin are search configurations that produce faster searches with high-quality results. Points closer to the vertical axis are also of particular interest since they may produce acceptable configurations for those applications needing high-quality results, even when they may not be as fast as other setups.
Space's parameter exploration is necessary to achieve affordable computational costs with acceptable quality. Nonetheless, the exploration requires the evaluation of hundreds of configurations and proficiency in the particular algorithms that impose a barrier for using these methods.

Genetic-based exploration of the configuration space
Here we introduce a method for automatically tuning search hyper-parameters of our BS algorithm for similarity search. Our goal is to reduce the complexity of using our similarity search algorithm to almost a unique decision: selecting the memory of the index (the parameter b used for constructing the index). The procedure explores BS's bsize and ∆ parameter space to achieve competitive speeds and qualities. Please note that the exploration itself has several parameters, as discussed in this section. However, its final description is quite generic and does not need to be adjusted for typical workloads, as experimentally shown in §5.
A noticeable property of our approach is the usage of the beam search itself to tune hyper-parameters, see Alg. 1. As explained in §3, beam search is a population-based algorithm that iteratively tries to reduce a cost function visiting nodes in a graph of neighbors. The main idea is to explore neighborhoods while keeping a small set (beam) of promissory vertices to be explored.
In contrast with the similarity search task, the hyper-parameter search graph N ) is not explicitly stored; it is defined as follows: C = N × R + which is the domain of bsize and ∆; in this sense N : C → C where C is a subset of C of size . Therefore, the task becomes bounding C, the precise N definition, and a properly fitness function to drive the navigation.

Bounding the parameter space C
As commented, each c ∈ C is a tuple with instances of hyper-parameters (bsize, ∆) also called configurations. Please recall that bsize is the beam size that limits the maximum number of elements that are kept at any stage of the search, see §3; then, it is an unbounded positive integer, but its useful range is relatively small. We limit bsize to be between 2 and 512. Figure 1  This heuristic is not a rule since the graph is not a partition, and we cannot precompute a precise limiting radius. Figure 1 show that restricting ∆ to a less wide range, 0.9 ≤ ∆ ≤ 1.2, it is possible to trade effectively search speed and quality, i.e., reach close to perfect recall in all benchmarks and can also obtain high-speed searches.

Neighborhood N
The neighborhood function connects each configuration with other configurations that ideally are similar in some sense. While the precise similarity notion is not relevant for our approach, we will define how to construct neighborhoods. We are now able to define the initialization procedure for BS (Alg. 1, line 4) as a random sample of C, using rand(C). Moreover, N (c) is defined as {mutate(c)} γ ; we also include δ configurations computed with crossover over two configurations randomly selected from the beam. The latter adds some diversity to the neighborhood, trying to avoid local optima points, i.e., similar to long links mentioned in [22].

Pareto optimal fitness functions and the minimum quality fitness function
A central component of our approach is the fitness function that will be used to navigate the (C, N ) graph. As commented, we have identified two desirable behaviors: configurations that optimize both search speed and quality, having the best of both scores without compromising the other, and also configurations that achieve a minimum quality.
The best configuration that takes care of these two objectives and that cannot improve in one without decay in the other is called Pareto optimal. This optimal point depends on the precise characteristics of the workload, that is, the dataset, measure distance, and the query set used to probe.
For this matter, it is important to remark that these functions work under a determined context: • They work on a non-empty index using the a given set of parameters. We should measure costs and performances to create a metric.
• We work under the reasonable assumption that the test set (queries) will follow the dataset's distribution. Therefore, we use a small subset Q of objects from the current indexed ones to compute the objective function, i.e., each fitness evaluation solves |Q| k-nearest neighbors queries.
• The number of retrieved neighbors for Q is the same as the test set.
• Recall-based objective functions compute a gold-standard result set on Q with an exhaustive evaluation.
• We fix maxvisits to O( log 3 n ) for stopping any similarity search procedure that surpasses this cost. 4 The cubic logarithmic cost is suggested in [25] as the expected cost of the NSW.
The design of fitness functions is quite flexible since BS optimization algorithms do not need a gradient computation. In particular, we propose three fitness functions: Pareto-recall. Bi-objective optimization that searches for configurations that optimize search speed and recall. It is defined as: Pareto-recall((bsize, ∆)) = visits maxvisits where visits is the average number of distance evaluations performed to solve a set of queries using a search graph with bsize and ∆ as hyper-parameters.
Pareto-radius. This is a bi-objective optimization that searches for configurations that improve search speed and minimizes the average radius of the result set. The optimization procedure is faster than Pareto-recall since it does not require computing a gold standard. It is defined as: Pareto-radius((bsize, ∆)) = visits maxvisits + avg. radius max. radius , where avg. radius is the covering radius of the query set Q. The maximum covering radius must be estimated to avoid the computation of a gold standard, in particular, we use the first Pareto-radius evaluation in an optimization procedure to estimate it.
Min-recall. Optimizes an index to achieve a minimum quality, min-recall, in a training gold-standard; once the restriction is achieved, it looks for the faster configuration. This fitness function is defined as follows: The min-recall is a specified parameter while recall and visits are computed using a search graph with the given configuration.
Please note that our bi-objective functions require that both objectives remain on a similar scale.
Finally, please recall that k nearest neighbor searches are represented as a minimization procedure using fitness q (u) = dist(q, u) for some q ∈ U and some u ∈ S ⊆ U while the fitness function for evaluating hyper-parameters use a working index and a small set of queries.

Experimental results
In this section, we describe the results of the experiments using Auto-tuning on the BS (ABS). We start on the build time and the memory needed for storing the index, and then we describe the performance of different combinations of fitness functions on each of the datasets, In Table 3, we show, for every dataset and each of the three different fitness functions, the amount of memory the index needs and the time are taken to build each index. Note that Pareto-radius produces the smaller indices since the covering radius of each query is minimized, which can promote retrieving fewer items than needed. Please recall that our construction algorithm is based on searches. This size reduction is hardly noticed because the dataset dominates the required memory. Regarding the building time, we can see a significant impact of the Pareto-radius; for example, on DeepImage, the building time is 67% that of Min-recall and only 35% compared to Pareto-recall. These gains can be seen over the other datasets. The Min-recall improves those Pareto-recall's construction costs on DeepImage, Lastfm, and WIT. We now present the results for ABS on each of the datasets except Bi-gANN. We used combinations of the Pareto-recall, Pareto-radius, and Min-recall We found that recall scores for the test query set are pretty similar to those expected ones. Note that optimization procedures (construction and previous to search) never saw the test set. These performances show the convenience of our automatic hyper-parameter tuning.
Nonetheless, we must comment on the Lastfm-300k because it shows a different behavior than the rest of the datasets where we can see a smooth Pareto front. We found a sharp curve, and therefore, it is hard to have suitable configurations for Pareto since the area where a configuration excels at both is small.
The optimization fails since it has to generalize from a sample in the training partition to the complete test set. Nonetheless, please look at the red, green, and purple right-facing triangles. These three optimizations appear very close to the origin, not just on Lastfm but on all our benchmarks.
In Table 4

Comparison with other indices
In this section, we show a comparison of our ABS with other state-of-theart indexes in the categories of build time, memory, search speed, and recall.
We tested the NNdescent implementation from PyNNDescent, the HNSW from the FAISS library, and SCANN from its official git repository. Each of these indexes was configured following the recommendations from their developers. In particular, for the NNdescent we fixed divprob = 1.0 and prun = 1.5, we vary the number of neighbors N . In the case of the HNSW, we used fixed values of The constructions for all the indexes used 64-threads, but the searches were made using a single thread. The ABS was constructed with Pareto-recall and then optimized for searching using Min-recall; a single index per dataset was created. We use a single index for other datasets with their search parameters vary, with the exception of NNdescent that we need to create several indexes.  The first dataset appearing is the BigANN with 100 million elements. Here, the HNSW is quicker but has the worst recalls. The ABS and the SCANN have similar recalls at comparable speed. Note, for example, that the ABS can reach like 0.97 on recall with faster searches than the SCANN. This dataset Min-recall before searching. The penultimate plot in Figure 3 is that of the is, we ask for them.

Optimized parameters
The ABS optimizes bsize and ∆ parameters during the construction and previous to searching. Table 6 shows the final bsize and ∆ used for searching.  datasets; the bsize and ∆ are similar despite the 100 times difference in size.
Glove and Twitter benchmarks are all word embeddings with similar sizes; they all have differences in the hyperparameters. Please note that these values are independent of the dataset size and dependent on the dataset distribution and complexity. This tuning complexity is tackled automatically with our approach.
On the other hand, note that the average number of visits increases with r (the queries per second decrease since they are inversely proportional to visits).
In general, we observe that optimization time is short and proportional to r except for BigANN-100M, where the large size could explain this divergence. Table 6 also shows that the recall test closely follows the value of the recall train, and it is also pretty similar to the optimized r. The optimization for r = 0.8 gives the bigger differences between the train and test recalls. This difference might indicate overfitting over the training data. Please remember that Pareto optimal points are around this value; therefore, slight movement in the configuration space may produce significant performance changes in an index. Again, the Lastfm benchmark is distinctive since train recall scores are similar to r, but this is not reproduced in the test. In general, it achieves extreme bad or good results.

Conclusions
This manuscript introduces a graph-based similarity search index that efficiently uses the Beam Search algorithm to solve k nearest neighbor queries. We modified the existing algorithms and structures from our previous work. We added a new expansion hyperparameter called ∆ that allowed trading search speed and accuracy, and introduced an automatic hyperparameter optimization based on the Beam Search. This optimization metaheuristic allows fast constructions with an expected performance of the index. We provide two kinds of optimizations, bi-objective Pareto optimality setups for search speed and quality; we also produce setups for achieving fast queries with a minimum expected quality. We aim to simplify similarity search indexes while obtaining fast and accurate indexes. We provide an opensource implementation under the MIT license for the Julia language.
We provide extensive experimental evidence that characterizes and compares our contribution in various benchmarks corresponding to vision, language, and vision & language tasks. More detailed, we compare our approach with three state-of-the-art methods on nine real-world datasets achieving competitive results in construction cost, memory, search time, and recall.
It is worth mentioning that our approach achieves convenient tradeoffs in almost all our benchmarks, but not in one, Lastfm. We had observed a sharped curve in the configuration space that makes it hard to tune automatically. Another issue we are aware of is the overfitting effect found in several datasets.
While this issue is expected since we use objects in the train set to adjust hyperparameters, the approach needs more work on regularization methods.
Finally, we also observed skewed distributions of neighborhood sizes, some of