Benchmarking Approximate k-Nearest Neighbour Search for Big High Dimensional Dynamic Data
Authors: Ben Harwood
Amir Dezfouli
Iadine Chades
Venue: Submitted to ICLR 2023 (2023)
Keywords: Nearest Neighbour Search
Similarity Search
Indexing
Knowledge retrieval
Knowledge discovery
High Dimensional Data
Big Data
Large Scale
Hashing
Graph Traversal
Product Quantisation
Online Learning
Representation Learning
Metric Learning
Robotic Vision

Abstract: Approximate k-Nearest Neighbour (ANN) methods are commonly used for mining information from big high-dimensional datasets. For each application the high-level dataset properties and run-time requirements determine which method will provide the most suitable tradeoffs. However, due to a significant lack of comprehensive benchmarking, judicious method selection is not currently possible for ANN applications that involve frequent online changes to datasets. Here we address this issue by building upon existing benchmarks for static search problems to provide a new benchmarking framework for big high dimensional dynamic data. We apply our framework to dynamic scenarios modelled after common real world applications. In all cases we are able to identify a suitable recall-runtime tradeoff to improve upon a worst-case exhaustive search. Our framework provides a flexible solution to accelerate future ANN research and enable researchers in other online data-rich domains to find suitable methods for handling their ANN searches.

Under review as a conference paper at ICLR 2023
BENCHMARKING APPROXIMATE K-NEAREST NEIGHBOUR SEARCH FOR BIG HIGH DIMENSIONAL DYNAMIC DATA
Anonymous authors Paper under double-blind review
ABSTRACT
Approximate k-Nearest Neighbour (ANN) methods are commonly used for min- ing information from big high-dimensional datasets. For each application the high-level dataset properties and run-time requirements determine which method will provide the most suitable tradeoffs. However. due to a significant lack of comprehensive benchmarking, judicious method selection is not currently possi- ble for ANN applications that involve frequent online changes to datasets. Here we address this issue by building upon existing benchmarks for static search prob- lems to provide a new benchmarking framework for big high dimensional dynamic data. We apply our framework to dynamic scenarios modelled after common real world applications. In all cases we are able to identify suitable recall-runtime tradeoff to improve upon worst-case exhaustive search. Our framework pro- vides flexible solution accelerate future ANN research and enable researchers in other online data-rich domains to find suitable methods for handling their ANN searches !
INTRODUCTION
Approximate k-Nearest Neighbour (ANN) search is a widely applicable technique for tractably com- puting local statistics over large datasets of high dimensional discrete samples (Beyer et al. 1999). ANN methods achieve sub-linear search times by trading off search accuracy and runtime. ANN methods are applied in many domains such as image retrieval, robotic localisation, cross-modal search and other semantic searches (Prokhorenkova & Shekhovtsov 2020). ANN search is well suited to applications where an index structure can be precomputed over a static dataset to then provide suitable recall-runtime tradeoff.
Achieving an optimal tradeoff for specific dataset properties and application requirements relies on hyperparameter tuning for each suitable ANN method. For instance, graph based indexes can be tuned to achieve high search accuracy while quantisation methods are better suited to perform faster searches with less exact results. In practice, when given new dataset, there is significant com- putational cost to evaluate and select the best performing ANN method. Several ANN benchmarks have been established to guide the selection and parameter tuning required for achieving tractable searches (Aumüller et al. 2017]: Matsui 2020). However, current ANN benchmarks focus on static search problems and cannot be used to inform any ANN methods are suitable for tackling dynamic search problems where the indexed dataset changes over time.
We observe that current ANN benchmarks do not generalise to dynamic search problems because they perform index construction as an offline process that optimises for search performance fixed dataset (Figure [b). This fails to address the requirements of growing fields such as Ma- chine Learning (ML) where there is strong need for tractable k-nearest neighbour search large dynamic sets of high dimensional samples (Prokhorenkova & Shekhovtsov (020).. For example, local statistics can be extracted by computing neighbourhoods in embedding space of learning process, but computing these neighbourhoods requires frequent evaluation of sample locations in the highly dynamic embedding. Due the lack of suitable ANN benchmarks, achieving tractable
"oode submitted in supplementary materials and will be available publicly on publication

---

Under review as a conference paper at ICLR 2023
a)
Data Collection
Feature Learning
Index Construction
b)
Offline
Data Collection
A
Feature Learning
Index Construction
Offline
Online
Online
Closed loop leature learning
Search
Search
Closed loop data collection
Figure I: a) Existing ANN benchmarks evaluate performance using a single batch of searches per- formed on static index. b) Our framework generalises to dynamic search problems where batches of index updates occur between batches of searches. Our benchmarks provide an improved model for optimising ANN usage in online data collection and online feature learning.
search performance currently requires extensive evaluation and tuning on the already computation- ally expensive and highly parameterised systems that could utilise dynamic ANN search. Here, we address this gap and present novel ANN benchmarking framework for dynamic search problems. Unlike existing benchmarking of ANN search we include the computational costs of constructing and maintaining index structure throughout dynamic process.
The main contributions of our work are as follows:
We present novel characterisation of the complexity and dynamic variations for ANN search on big high dimensional (~~ 100 dimensions) dynamic datasets (Section 2). From this, we generate benchmarks that model domain specific applications in two key categories of dynamic search problems: online data collection and online feature learning (Figure [p))
We establish the bascline performance of five promising ANN methods using extended hyper- parameter sets to better address the requirements of dynamic search problems (Section 5 We discover that ANN methods such as ScaNN (Guo al. 2020 and HNSW (Malkov Yashunin 2018) can outperform exhaustive search despite online index overheads.
We show that our benchmarking framework can successfully identify which ANN method is best suited for a given dynamic search problem. Our framework generates the key tradeoffs for select- ing a suitable ANN method and can be extended to additional dynamic search problems and for future ANN research.
PROPOSED CATEGORISATION OF DYNAMIC SEARCH PROBLEMS
In this section, we identify two key categories of dynamic search problems based on their require- ments: online data collection and online feature learning. We also identify key measures that char- acterise specific instances of both static and dynamic search problems.
ANN search with online data collection or online feature learning requires online index construction (Figure [p). A major practical advantage of online index construction is that it allows for search information to be fed back in a closed loop fashion. To categorise dynamic search problems, we consider their requirements for online data collection online feature learning. Autonomous navi- gation, live internet services and generative learning methods are common examples of online data collection that generate an increasing number of samples over time. An increase in the number of indexed samples will directly increase the computational cost of performing searches. Within many machine learning processes, the training of embedding space is example of online feature learning. Updating model parameters during the learning process will update the embedded repre- sentation of indexed samples. This update can affect local and global index structures and degrade the performance of subsequent searches.
From a database perspective, we match online data collection and online feature learning with the operations of adding new samples and updating existing samples respectively. Our benchmarks are designed around each of these two operations in order to model the range of dynamic search prob- lems we are interested in. The removal of samples is another fundamental database operation which often heuristically applied to maintain sample diversity while limiting the total sample count. Re- therefore be viewed heuristic that is providing tractability tradeoff. In
moving samples this research we omit the remove operator to focus on benchmarking the baseline tractability from ANN methods alone.
2

---

Under review as a conference paper at ICLR 2023
In addition to categorising the types of dynamic search problems, also identify key measures that characterise specific instances of dynamic search problems. Table ! provides an overview of these measures. Each measure either needs to be specified when defining a benchmark can be used to evaluate the performance of ANN methods on that benchmark. We identify six measures available static benchmarking problems. Sample count and sample dimensionality are enough to specify most static benchmarks and search accuracy and search runtime are the most common performance evaluation measures. Initialisation time and memory footprint are less commonly used for performance evaluation (Aumüller et al., 2017
Matsui 2020p.
Table 1: Key measures of high dimensional search problem characteristics that can be used for specifying benchmarks and evaluating the performance of ANN methods. Dynamic search problems require additional benchmark and evaluation measures that are not present in static search problems.
Specified by Benchmark
ANN Method Static Search Dynamic Search Problems
Measure
Dependant
Problems
Sample count
Sample dimensionality
Initialisation time
Memory footprint
X
Event type
X
Event processing time
X
x
Event frequency
XXX
X
Event batching
Search accuracy
Search runtime
Search frequency
Search batching
We identify additional six measures that apply to dynamic search problems, but not to static ones. To specify a benchmark we include event type to select between add events in our online data collection benchmarks and update events in our online feature learning benchmarks. To fully specify the characteristics of dynamic benchmark we propose the use of frequency and batching measures for both events and searches. Event batching and search batching define the number of events or searches that will be executed in continuous block, then followed by a block of the other. Event frequency and search frequency define how much time is available before another block of events or searches will be available. Lastly, event processing time is an additional performance evaluation measure where we capture the runtime cost of online index construction and updates.
The frequency of events and searches has direct impact the tradeoff between search accuracy and search runtime. Given a fixed amount of computational resources we have a hard limit on the maximum number of operations that can be performed in any period of time. Examples of these changes include increasing the sensor speed on an autonomous vehicle and increasing the batch gradient decent batch size of closed loop learning pipeline. To avoid latency, the fixed budget of compute operations must be divided between each of the events and searches processed during the available time period. Increasing the frequency will then result in reduced amount of compute for processing the events and the searches. For dynamic search problems, we expect that less compute per event will eventually degrade the index quality. Degraded index quality and less compute per search will both ultimately result in lower search accuracy.
The batching of events and searches can also impact the search accuracy-runting tradeoff in a less direct way. For a fixed amount of compute in a given period of time, we now consider a fixed number of events and searches that will processed. At each extreme of batching we could have events and searches alternating one after another or we could have a large chunk of events clumped together followed by large chunk of the searches. Examples here are an autonomous vehicle capturing and querying for each location as it travels and closed loop learning pipeline completing full forward pass to then feeding back neighbourhood information about an entire dataset. Theoretically, larger batches of events can provide a total amount of compute that is capable of applying global changes to an index structure, while small batches would be limited to more localised changes. We expect that an index limited to localised changes will degrade in quality, thus reducing search accuracy.
3

---

Under review as a conference paper at ICLR 2023
This assertion is supported by the frequent use of dynamic programming and hierarchical structures used in offline index construction for static search problems. Additionally, search batches are always assumed be mutually independent when benchmarking static search problems. However batching can provide small efficiency gains by increasing the utilisation of parallel hardware. In the context of dynamic search problems also investigate the performance of ANN methods when consecutive searches do share mutual information.
3 FRAMEWORK STRUCTURE AND MODULES
We have designed a flexible, extensible and open access framework to specify and evaluate ANN benchmarks for dynamic search problems. In the previous section we identified twelve important measures for specifying and evaluating dynamic search problems. In this section we detail the three main modules of our framework and how they address these measures. We highlight other novel additions that extend the protocols of existing ANN benchmarks (Aumüller et al. (018)) Matsuij (2000) and discuss the key challenges of benchmarking dynamic search problems. Importantly, describe each the frontend components that users of our framework will likely need to interact with (shown in green in Figure 2).
Groundtruth Data
Core Executable
Index Update
Legend
Code Block
Groundtruth Computation
Benchmark Results
Dynamic Data
Index Initialisation
ANN
Markup bocument
Data Loader
Plot Generation
Dala Store
Backend
Frontend
Raw Samples
Data Config
Benchmark Formulation
Search Config
Index Contig
Flow of
Config
Method
Dynamic data module
Evaluation
Search module
module
Our framework is built to address the requirements of benchmarking high dimensional dynamic search problems. The three main modules of our framework manage datasets (left), ANN methods (right) and evaluation (middle). Using our framework involves interacting with the frontend components shown in green.
Figure 2:
3.1 EVALUATION MODULE
Evaluation of dynamic search problems is itself a substantial challenge with each measure on each ANN method at each point in time creating additional outputs that need be searched and filtered to identify the top performing configurations. A configuration file (Plot Config) is used to specify which datasets, ANN methods and performance measures to be executed. The performance measures listed in Table [ can be plotted against each other or individual measures can be plotted over time. The time series plots provide novel perspective that does not exist for static search problems. Each ANN method can be plotted to evaluate its full set of hyperparameter options, or the Pareto frontiers of multiple ANN methods can be plotted to compare their relative performance. Figures in Section and Appendix showcase some of these plots.
3.2 DYNAMIC DATA MODULE
Defining dynamic search problem our framework requires three components: configuration file (Data Config), data blob (Raw Samples) and block of Python code (Benchmark Formula- tion). Data Config specifies any hyperparameters for initialising the dataset or augmenting it over time, including the seven benchmark measures from Table Raw Samples contains samples for
4

---

Under review as a conference paper at ICLR 2023
initialising the dataset and for growing augmenting it time, alternatively this can be gen- erated programmatically in the code block. Lastly, Benchmark Formulation makes use of helper functions to execute dynamic events, ANN searches and outputting results. In the backend of this module, the groundtruth results, baseline compute times and baseline memory usage are generated by running each newly defined dynamic benchmark using bruteforce nearest neighbour method. Together this module provides a flexible system for defining and evaluating dynamic benchmarks that are parameterised to model the key properties of specific dynamic search problems.
3.3 SEARCH MODULE
Defining dynamic search problem in our framework requires three components: a search configu- ration file (Search Config), an indexing configuration file (Index Config) and block of Python code (ANN Method). The configuration files specify the full hyperparameter ranges for index construc- tion, handling dynamic events and performing ANN searches. The code file provides an interface between the framework and specific ANN method which includes functions for index construc- tion, handling dynamic events and performing ANN searches. Common ANN methods are currently designed, parameterised and tuned using static search problems. Therefore we expect that the recom- mended hyperparameter ranges will not align with the optimal range for dynamic search problems. The frequency and batching (of events and searches) is handled within the backend components, this includes the ability to bypass particularly slow event handling achieve tractable evaluation trade- offs. Further discussion of hyperparameter tuning and slow event handling is provided in Appendix A
APPROXIMATE NEAREST NEIGHBOUR SEARCH METHODS
Approximate k-Nearest Neighbour (ANN) methods are designed to provide favourable tradeoffs between search performance and computational resources (Beyer et al.] 1999 PProkhornkova & Shekhovtsov 2020). Many viable methods exist and we can differentiate them by the index struc- tures that facilitate the efficient searches. These index structures determine each of the six measur- able performance indicators listed in Table I Deeper consideration can also be given to underlying factors such as the impact of memory bandwidth and partial index updates for determining the event processing time of method. In this section we provide an overview of the methods we have evaluated. Our selection criteria is focus on methods with an optimised, publicly available imple- mentation that can be interfaced with Python code. Table 2 summarises the type of index structure used by each method, it is an exact search, whether samples can be added without rebuilding the index (incremental construction for online data collection) and whether sample values can be up- dated without rebuilding the index (for online feature learning). Methods that do not support these functions will have additional construction overheads as the entire index is rebuilt each time dy- namic event is processed. Rebuilding an index will often result in large event processing time that is then partially mitigated by the slow event handling discussed in Appendix A
Table 2: ANN methods in current and common usage for static search problems. We extend and evaluate each method with our dynamic search problem benchmarks.
Exact Search
Incremental Construction
Update Samples
Index Type
ANN Method
None
Bruteforce
Quantisation
IVFPQ (Johnson et al.
2019
X
x
X
ScaNN (uuo el al. 2020)
X
X
Tree
Annoy
Bernhardsson 2013
X
X
k-d Tree (Pedregosa al. 2011
X
X
Graph
HNSW MMlkov & Yashunin 2018
X
The baseline approach to nearest neighbour search exhaustively computes distances between each query and each sample in dataset while maintaining of the k-nearest samples for each query. This bruteforce method can be accelerated with parallel computation of partial distances, full dis- tances and simultaneous queries. A linear recall-runtime tradeoff can be achieved by only computing
5

---

Under review as a conference paper at ICLR 2023
distances to subset of samples (reported Baseline in Section 5). Importantly, there are ad- ditional overheads for constructing or maintaining an index over the samples. Currently there is no consensus which ANN methods, if any, most suitable to replace bruteforce search in dynamic search problems. Recent papers include examples of using bruteforce search (Komorowski [202]] Vidanapathirana al.) (02T), k-d trees (Kim & Kimi 2018, Xu et al.] [202T) and graphs (An al.
10019SScubber et al. 1021) to address similar dynamic search problems.
Quantisation methods (Johnson et al. 2019 Guo et al.) 2020) cluster dataset into local neigh- bourhoods where efficient residual distances are used. Quantisation methods are related to hashing methods with their regular partition of high dimensional space. However, quantisation methods achieve this partition by grouping samples around cluster centers rather than cutting up the space with hyperplanes. Clustered samples are then mapped to a codebook using a reduced dimensional space within each cluster. Cluster centers are learned from the intrinsic structure of a dataset and this provides a significant improvement to recall performance, but at the expense of a larger index construction time.
Tree methods (Bernhardsson 2013 Bentley 1975 Pedregosa et al. 2011) connect dataset samples into a traversable index structure with single source and no cycles. Tree methods are frequently used for their fast index construction and searches. Compared to quantisation methods, tree meth- ods have additional memory cost of storing the edge information that enables the search paths. Traversing a tree involves many local decisions that utilise an increasingly smaller subset of the global information as sample dimensionality increases. As such, higher recall can only be achieved with a significant amount of backtracking on a single tree or by searching in parallel over a forest of semi-redundant trees. Despite these limitations, standard k-d tree implementations continue be applied to high dimensional search problems (Kim & Kim 2018: Xu et al. 202T).
Graph methods (Arya & Mount 1993] Harwood & Drummond 2016 Malkov & Yashunin 2018) generalise tree methods by allowing any set of directed edges that connect all dataset samples. Graph methods are some of the most recent and promising methods due to favourable recall-runtime tradeoffs in existing ANN benchmarks. Like tree methods they require the additional storage of edge information. Graph methods are better suited for indexing big high dimensional data due to their lack of an explicit hierarchical structure which ensures that all local regions are well connected to other areas of the graph. However, the selection of an appropriate set of edges is computationally intensive, leading to large index construction times. Hierarchical navigable small world graphs (HNSW) (Malkov& & Yashunin| 2018) avoid this cost by semi semi-randomll selecting a set of edges with desirable statistical properties.
5 BENCHMARKING EXPERIMENTS
We evaluate the ANN methods of interest across our proposed benchmarks and report the key find- ings. We present the Pareto frontier of recall-runtime performance for each method. Runtime results reported on logarithmic scale ratio against the full bruteforce runtime (speedup over brute- force combines total event processing time and search runtime). We limit all methods to run on a single AMD EPYC 7543 CPU thread (3.7 GHz turbo, 256MB cache) with up to 10GB RAM. This firstly aims to provide results that are more analogous to theoretical complexity analysis. Compar- ing the theoretical complexity of different ANN algorithms is otherwise impractical due to algorithm performance being dependant on dataset properties. And secondly, a single thread mitigates perfor- mance biases that can occur at particular parallelisation thresholds. However, algorithms are not re- stricted from performing thread level parallelisation by taking advantage of hardware specific SIMD instructions for I/O and arithmetic. Recall results are reported as an average, where each search returns the top 50 nearest neighbours for query and is scored against the ground truth top 50. All neighbours are weighted equally for scoring. This choice of neighbourhood size and weighting is selected to be realistic for the real-world applications being modelled. In practice, these moder- ately large neighbourhood sets are sized to accommodate inherent noisiness in the samples and a secondary metric would be used to re- re-weight these shortlisted samples for downstream usage.
Within our benchmarking framework we have implemented two datasets targeted towards broad ap- plication areas. Firstly, our online data collection dataset is modelled around real-time applications where each subsequent query is appended as a new sample to the dataset. We use various subsets of the 128 dimensional sift M datase(Jegou al. 2008 with add events growing each dataset to

---

Under review as a conference paper at ICLR 2023
Online data collection
Online feature learning
b)
103
10
Speedup over bruteforce
Speedup over bruteforce
10a
100
k-d Thee
10
k-d Tree
Annoy
INNSW
Annoy
10-1
HNSW
ScaNN
ScaNN
Baseline
100
IVFPQ
Baseline
10
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Average top 50 recall
Average top 50 recall
Figure 3: Recall runtime performance against bruteforce baseline using extended hyper- parameters and tuning for dynamic search problems. a) An online data collection benchmark with 100k samples, 128 dimensions, 100k added events, event and search batch size 1. b) An online feature learning benchmark with 5k samples, 96 dimensions, 100k update events, event and search batch size 200.
double its initial size and additional hyperparameter to adjust mutual information by interpolat- ing consecutive queries. This allow us to explore applications where either each query is assumed to be independent of any other, where consecutive queries are assumed to have some degree of commonality. Initial samples are expected to be representative of the total sample pool, altering this is expected to degrade the performance of some methods. Secondly, our online feature learn- ing dataset provides a generalised but flexible model for machine learning applications. It applies update events to model dataset where samples are converging across incremental updates. We use various subsets of the 96 dimensional deepI dataset Babenko & Lempitsky (2016), with additional hyperparameters to simulate training epochs, batch size, convergence rate, clustering coefficient and if groundtruth is measured after each batch or each epoch. This allows users to explore various machine learning applications and can be further extended to suit more specific goals.
Our results in Figure 3 show that existing ANN methods can achieve useful performance by ex- ceeding bruteforce baseline on our two applications. For the online data collection benchmark in Figure 3h. k-d tree (green circle) is the only method that does not outperform the bruteforce baseline. This validates that k-d trees are not suitable in these dynamic high dimensional search problems, but also that other methods are indeed capable of providing desirable recall-runtime tradcoff. HNSW (Malkov & Yashunin 2018) (purple triangle) is the only algorithm outperforming bruteforce above 70% recall, while ScaNN (Guo et al., 2020) (red diamond) is the fastest algorithm below 70% recall. The benchmarks produced by our framework succeed in identifying crossover points, such as this one between HNSW and ScaNN, which are critical knowledge when selecting an ANN method for a given application. Comparing to the online feature learning benchmark in Figure 3p, all methods perform considerably worse compared the baseline. This is in part due to the update events (discussed in Section 2 affecting all samples in an index, while the add events have more local impact. For the online teature learning benchmark, no method is faster than bruteforce beyond 78% recall, more than 5x faster beyond 20%. K-d trees perform well below the baseline and we are unable to produce results for the current IVFPQ implementation. Further discussion on time series performance, hyperparameter tuning and dataset scale is provided in the Appendix [A]
We verify the importance of the novel characteristics defined in Table Section2]by varying the benchmark specified hyperparameters that have been added for dynamic search problems. Specifi- cally these hyperparameters are the frequency and batching of both events and searches. The impact of each hyperparameter the ANN search performance indicates if that parameter is important consideration when creating benchmarks for real-world dynamic search problems. In Figure 4a we that increasing the event frequency increases the difficulty of the dynamic search problem. The
7

---

Under review as a conference paper at ICLR 2023
Speedup over bruteforce
Speedup over bruteforce
100
100
search freq
2x scarch froq
1x search froq
1x event freg
2x froq
tx event frog
10-1
10-1
0.75
0.8
0.85
0.9
0.95
0.4
0.6
0.8
Average top 50 recall
Average top 50 recall
d)
10a
10a
Specdup over bruteforce
Speedup over bruteforce
event batch batch
1x event/scarch batch
event/vearch
Ix event/search batch
10"
10²
10-1
100
0.2
0.4
0.6
0.8
0.25
0.3
0.35
0.4
0.45
Average top 50 recall
Average top 50 recall
Figure 4: Recall vs runtime performance when varying the frequency and batching of both events and searches. Shown for online feature learning benchmark with 5k samples, 96 dimensions, 100k update events, event and search batch size 200, HNSW method (Malkov & Yashunin, 2018). Increasing event frequency with fixed search frequency. Fixed event frequency with increasing search frequency. c) Increasing event batching with fixed search batch size. d) Increasing event and search batch size together.
10
Speedup over bruteforce
10a
Independent Interpolated
10
0.2
0.4
0.6
Average top 50 recall
Figure 5: Recall runtime performance for temporally dependant events. Shown for an online data collection benchmark with 100k samples, 128 dimensions. 100k added events, event and search batch size HNSW method (Malkov & Yashunin, 2018). 10% interpolation.
recall- -rantim tradeoff moves towards the origin until saturates. Figure 4p demonstrates similar behaviour for increases in search frequency. Figure 4e and Figure 4d shows that significant perfor- mance differences can also be induced by varying the event batching. Collectively from the results in Figure 4 it is evident that each of the benchmark hyperparameters have defined are important
8

---

Under review as a conference paper at ICLR 2023
considerations when characterising dynamic search problem for benchmarking. Further discussion on the relationship to time series performance is provided in the Appendix A
Lastly, we consider the role of mutual information that exists between consecutive search batches due to temporal consistency in dynamic search problems. In the context of ANN search, this tem- poral consistency creates higher overlap between groundtruth neighbourhood sets in consecutive search batches. We model temporally consistent events by augmenting our datasets to interpolate between samples over time. In Figure 5 dataset against performance of the non-interpolated dataset. From our results we conclude that the ANN methods we evaluate fail to exploit mutual information between consecutive search batches. These methods do not attempt to update their internal parameters or search strategies based on recent queries. Ideally, an ANN method designed specifically for dynamic search problems would utilise information from recent queries to generate considerably improved recall-runtime performance for the interpolated dataset.
we plot the ANN search performance of the interpolated
CONCLUSIONS AND FUTURE WORKS
We present novel benchmarking framework to address the significant gap utilising ANN meth- ods for dynamic search problem. ANN methods sceing increasing use in domains such as ma- chine learning where there is a need to distill local statistics from large amount of high dimensional data. However the dynamic nature of this data is at odds with the static search problems that are used when designing and benchmarking current ANN methods. Our framework directly addresses define new benchmarks that give first indication of how current ANN
this issue by allowing methods will actually perform in dynamic contexts.
Our generalised approach to dynamic search problems has enabled to categorise and implement benchmarks that model a number of real-world problems. Specifically we focus on the dynamic search problems that feature online data collection and online feature learning. Within these two categories we have also explored the effects of dynamic search problem characteristics and temporal dependence between consecutive samples. Our extensible framework allows for future work add new categories of dynamic search problems, build upon the current ones or replay real-world data captures. In particular, our work does not currently extend to include the fundamental database operation of removing samples. Removing samples becomes an important consideration when the pruning of old or low saliency samples is needed for bounding memory consumption.
Our benchmarks show that judicious selection of ANN methods is critical for efficient performance on dynamic search problems. We find that a standard implementation of k-d trees performs signifi- cantly worse than an exhaustive search. This is despite continued usage in dynamic high dimensional data contexts (Kim & Kim 2018 Xu et al, 2021). In contrast, HNSW (Malkov & Yashumin 2018) and ScaNN (Guo al.] (0200) perform very favourably on our dynamic search problems. Again the extensibility of our framework supports the inclusion of additional ANN methods as well as the evaluation of or altered methods. We hope the performance benchmarks established in this paper will be a launchpad that is quickly exceeded by further research.
We have demonstrated that additional hyperparameters and hyperparameter tuning can adapt exist- ing ANN methods from static to dynamic search problems. However, there are still large research gaps in designing ANN methods that are specifically tailored for exploiting the full information available in dynamic search problems. ANN methods with slow index construction benefit greatly from reducing the frequency of event and batching them into larger index updates. Some ANÑ methods have been designed to exploit mutual information from application specific temporal re- lationships (Garg& & Milford 2021). Extending general ANN methods in this way could provide a large performance gain these dynamic search problems.
Dynamic search problems are not going away, they are instead becoming more wide spread due to increasing demands for fast and realtime processing of big and rich data streams. This means there is lots to be gained from a deep and thorough exploration of which dynamic search problems are common place, and which ANN methods best suited to address their specific demands. Our benchmarking framework is well positioned as a launching point for others who are interested in exploring and contributing to the many open problems that exist in this area.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Shan An, Guangfu Che, Fangru Zhou, Xianglong Liu, Xin Ma, and Yu Chen. Fast and incremental loop closure detection using proximity graphs. In 2019 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 378-385. IEEE, 2019.
Sunil Arya and David M Mount. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms (SODA), volume 93, pp. 271-280, 1993.
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. In International conference on similarity search and applications, pp. 34-49. Springer, 2017.
Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull.
Ann- Ann-benchmarks.
hetps:
//github.co com hatpbeerr//aambbbbncaaarrr///// 2018.
Artem Babenko and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep descrip- tors. In Proceedings of the IEEE Conference on Computer Vision and Putlern Recognition, pp- 2055-2063, 2016.
Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communi- cations of the ACM, 18(9):50--517) 1975.
Erik Bernhardsson. Annoy. ht /ttppp/s//gtthho...c/a/ppptttttp
2013.
Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. When is "nearest neighbor" meaningful? In International conference on database theory, pp. 217-235. Springer, 1999.
Sourav Garg and Michael Milford. Segnet: Learning descriptors for sequence-based hierarchical place recognition. IEEE Robotics and Automation Letters, 6(3):4305 4312, 2021.
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Ku- mar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pp. 3887-3896. PMLR, 2020.
Ben Harwood and Tom Drummond. Fanng: Fast approximate nearest neighbour graphs. In Pro- ceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5713-5722, 2016.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Hamming embedding and weak geometric consistency for large scale image search. In European conference on computer vision, pp. 304- 317. Springer, 2008
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions Big Data, 7(3):535-547, 2019.
Giseop Kim and Ayoung Kim. Scan context: Egocentric spatial descriptor for place recognition within 3d point cloud map. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4802-4809. IEEE, 2018.
Jacek Komorowski. Minkloc3d: Point cloud based large-scale place recognition. In Proceedings of the IEEE/CVF Winter Conference Applications of Computer Vision, pp. 1790-1799, 2021.
Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824-836. 2018 2018.
Yusuke Matsui. annbench.
2020.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Coumapeau, M. Brucher, M. Perrot. and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2834 2011.
10

---

Under review as a conference paper at ICLR 2023
Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighbor search: From practice to theory. In Interaational Conference on Machine Learning, pp. 7803-7813. PMLR, 2020.
Stefan Schubert, Peer Neuhert, and Peter Protzel. Beyond ann: Exploiting structural knowledge for efficient place recognition. In 202/ IEEE International Conference on Robotics and Automation (ICRA), pp. 5861-5867. IEEE, 2021.
Kavisha Vidanapathirana, Peyman Moghadam, Ben Harwood, Muming Zhao, Sridha Sridharan, and Clinton Fookes. Locus: Aidar-based place recognition using spatiotemporal higher-order pooling. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 5075-5081. IEEE, 2021.
Xuecheng Xu, Huan Yin, Zexi Chen, Yuehua Li, Yue Wang. and Rong Xiong. Disco: Differentiable scan context with orientation. JEEE Robotics and Automation Letters, 6(2):2791-2798, 2021.
A APPENDIX
Each datapoint from the figures in Section an average over a series of events and searches that define that benchmark as a particular dynamii search problem. We can further analyse the performance of each ANN algorithm by considering the time series of how performance measures (as defines in Table vary throughout benchmarking. for the search performance measure, We compare each ANN method using the hyperparameter set identified at the harmonic mean of that methods Pareto frontier. For analysing and optimising individual ANN methods, time series results across hyperparameter sweeps of that method can be compared instead.
these temporal variations
In Figure we see that recall performance of all methods is relatively consistent across this bench- mark. Because this is an online data collection benchmark might expect to see a decrease in recall as the dataset grows from 100k to 200k samples, and similarly, from degradation as the index is continuously expanded and rebuilt. However, Annoy is the only method with a slight down- wards trend in its recall performance. For all other methods, the recall remains flat over time and would need consider the time series of other performance measures confirm if the cost of processing a larger dataset is being paid elsewhere. For both the k-d Tree and ScaNN methods we can see periodic oscillations in the recall. These oscillations are caused by the slow event handling in the backend of our search module (introduced in Section 3). Reducing the regularity of index updates important for reducing average runtime, however it results decreasing recall until the next index update is performed. In practice, we find that slow searches create downstream latency for systems using the outputted ANN results, while slow event handling can instead be absorbed by the recall-runtime tradeoff. As such, maintaining consistent search frequency is more important than prioritising event handling. Our framework incorporates this behaviour by extending all ANN methods with an optional hyperparameter that delays index updates for a specified number of events. This delay artificially lowers the event frequency and increases the event batching (as discussed in Section 2 and Figure 4).
Figure presents additional plots to illustrate the role of hyperparameter tuning and sample count, on the two dynamic search problems we have analysed. Comparing Figure 7 to 7p and Figure 7 7 shows the importance of additional hyperparameters and hyperparameter tuning for dynamic search problems. Figures 7/ and 7 contain results when using recommended hyperparameter sets that have been tuned on static search problems. Whereas, Figures 7p and 7 replicate the dynamic search problem results from F Our tailored approach to hyperparameter tuning results in im- proved performance for all ANN methods. This comparison highlights the critical importance of our benchmarking framework the best practice approaches for static search problems do not translate directly to dynamic search problems. To address the requirements of dynamic search problems extend the hyperparameter ranges of each method in directions that result in higher computational efficiency. This efficiency will typically be gained at the expense of recall. Additionally, we add an additional hyperparameter for optional management of slow event handling. Again we find that a reduction in recall is typical when the slow event handling is applied.
Lastly, in Figures 7c and 7 we illustrate the relationship between sample count and runtime, on log-log plots for the two dynamic search problems we have analysed. For each ANN method,
11

---

Under review as a conference paper at ICLR 2023
Average top 50 recall
k-d Tree
0.8
Annoy
HNSW
ScaNN
IVFPQ
0.6
0.4
0.2
0.4
0.6
0.8
Events processed
-105
Figure 6: Events processed vs recall performance for the harmonic mean of the Pareto frontiers. Shown for online data collection benchmark with 100k samples, 128 dimensions, 100k added events, event and search batch size 1.
plot the best runtime performance that achieves at least 50% recall for dataset of given sample count. At 50% recall the baseline bruteforce method can choose to ignore half of the dataset, the baseline cutoff is shown at 2. Here consistent with what has previously been found for static search problems. This trend shows that ANN methods increasingly improve their performance sample count increases. Extending our prior analysis of Figure 3 we identify the crossing points for the online feature learning benchmark where each ANN method becomes more efficient than the baseline. These crossing points are of similar interest to the crossing points of ANN methods with each other, as this information needed guide for a given application. Additionally by comparing Figures 7c and 7 we verify that update events introduced in Section 2) count is taken into consideration. For the same sample count and ANN method, we consistently see lower performance on the online feature learning benchmarks than the online data collection benchmarks. Further analysis of each individual ANN method will be required to identify the root cause of this performance difference between event types, and potentially to then further improve ANN search performance for online feature learning.
trend for the dynamic search problems that
baseline bruteforce search as
towards the most suitable ANN method
do result in worse performance than the add events, even when sample
12

---

Under review as a conference paper at ICLR 2023
Online data collection
Online feature learning
103
10
Speedup over bruteforee
Speedup over bruteforce
10a
100
k-d Tree
Annoy
k-d Tree
HNSW
10a
Annoy
ScaNN
HNSW
Baseline
k-d Tree Annoy ScaNN
10-1
ScaNN
IVFPQ
10"
Baseline
Annoy
V
10-2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Average top 50 recall
Average top 50 recall
b)
103
10
Speedup over bruteforce
Speedup over bruteforce
10a
100
k-d Tree
10
k.d Tree
Anmoy
HNSW
Annoy
10-1
INNSW
ScaNN
100
IVFPQ
ScaNN
Baeline
Baseline
10-2
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Average top 50 recall
Average top 50 recall
103
102
Speedup over bruteforce
k-d Tree
Speedup over bruteforce
k-d Tree
Annoy HNSW
Annoy
HNSW
10a
ScaNN
ScaNN
IVFPQ
Baseline
Bascline
10
10a
k-d Tree
10a
k-d Tree
10"
103
104
105
103
104
10
Sample count
Sample count
Figure 7: Recall performance against bruteforce baseline. a, c) An online data collection bench- mark with 100k samples, 128 dimensions, 100k added events, event and search batch size 1. d, f) An online feature learning benchmark with samples, 96 dimensions, 100k update events, event and search batch size 200. Top Recall runtime with hyperparameter tuning taken from statie search problems. Middle Recall vs runtime with our extended hyperparameters and tuning for dynamic search problems. Bottom Runtime sample count with datasets ranging from 10k to 500k samples and events evaluated at 50% recall.
13


Reviews:
[{"review_id": "vA5Y3YbdedF", "reviewer": "Reviewer_nVSk", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is concerned with the problem of evaluating approximate nearest neighbor (ANN) search strategies for use in high-dimensional and highly-dynamic settings, such as in deep learning, where features must be learned from sample neighbors in embedding spaces.  The authors propose and discuss a characterization of dynamic search problems in terms of 12 measures such as search accuracy, runtime, initialization time, etc.  Based on their characterization, a framework is proposed for specifying, evaluating, and performance-tuning ANN methods on dynamic search problems.  They then demonstrate their framework by providing an experimental evaluation of 5 representative ANN methods on 2 dynamic search benchmark data sets (1 data collection benchmark, and 1 online feature learning benchmark).\n", "summary_of_the_review": "Although the work targets a practical need in ML/DL, it is doubtful whether existing non-trivial ANN methods can meet practical time budgets even after parameter tuning. The work is not specific to learning, and many might regard this topic as only incidental to the interests of the ICLR community.\n\n", "strength_and_weaknesses": "Pros:\n\n1) A thorough and compelling motivation is given for the work, in light of the severe computational and resource implications of dynamic search, particularly as regards the context of deep learning. The categorization provided for dynamic search is well-argued, and a good case is made for the need of a benchmarking framework for parameter tuning of ANN methods in dynamic settings.\n\n2) The experimental evaluation does show that certain classes of ANN methods (in particular, graph-based methods) have greater prospects for handling high-dimensional and highly-dynamic data search problems, such as those that typically arrive in feature learning in ML/DL contexts.\n\n3) The work seems ready for deployment in ML/DL development. The authors intend to make their framework openly accessible to practitioners wishing to automate the runtime automation of parameter-tuning for ANN search.\n\nCons:\n\n1) Although the authors are careful to show a connection to ML/DL practice, the proposed framework is entirely generic as to the application - there are no unique issues that arise in learning contexts that require special treatment within the framework. As such, the topic is far from central to the interests of the ICLR community, and might be better suited to a different publication venue.\n\n2) The authors do not demonstrate their framework on dynamic data sets of the same scale as is commonly encountered in learning.  In their experimentation, they consider only two datasets: one having 100,000 samples in 128 dimensions, with 100,000 added events, and the other having 5000 samples in 96 dimensions with 100,000 update events.\n\n3) From the experiments, it is not clear whether `successful' parameter tuning is even capable of reducing the computational costs of ANN search methods enough to allow them to be used directly in deep learning. Practitioners and researchers often use fast heuristic methods such as minibatch sampling followed by brute-force search. Although the proposed framework can accommodate such heuristics, it is not clear that any of the more sophisticated ANN search methods would meet the time budgets available in practice, even when properly optimized.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "goHv1vcidJL", "reviewer": "Reviewer_brtU", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an evaluation framework for approximate nearest nearest neighbor search algorithms in a dynamic setting (index set changes over time). It measures various algorithms in this space and concludes that is possible to tune the algorithms so that they are far better than bruteforce search for high dimensional data.", "summary_of_the_review": "While a greatly welcome first step in the direction of benchmarking dynamic ANNS indices, the work falls short on several fronts -- metrics, evaluation set up, choice of operations, quality of tuning, description and coverage of use cases. Therefore, it does not rise to the quality necessary to be a useful reference in this area.", "strength_and_weaknesses": "Strengths:\n1. Authors list various parameters of importance to dynamic setting.\n2. Authors identify the lack of comparison for dynamic indices as a major missing piece on ANN literature. The research is timely.\n3. Authors identify that its possible to get substantial speed up over \n\nWeaknesses:\n1. The authors miss an opportunity to present clear and comprehensive experiments. A few examples of points important for dynamic indices but missed here:\n- How do batch-build vs streaming-build indices compare in quality? \n- No measurement of indexing effort vs search quality. There is a direct trade off between index construction complexity and \"search complexity vs recall\", the latter being the property studied in all plots. This is especially so for graph indices. A study of dynamic indices for graph indices could measure this trade off?\n2. Delete operation is ignored. This is important in practice, as a lack of delete operation forces a (expensive) rebuil of the indexafter substantial modification. While most indices measured in this paper do not support delete operation, there is recent work on deletes that this paper does not cite.  These papers also include algorithms at least as good as the ones studied in the paper for inserts.\n  - Proximity Graph Maintenance for Fast Online Nearest Neighbor Search [Zhaozhuo Xu, Weijie Zhao, Shulong Tan, Zhixin Zhou, Ping Li]\n  - FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search [Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, Harsha Vardhan Simhadri]\n  - Parallel Nearest Neighbors in Low Dimensions with Batch Updates [Magdalen Dobson, Guy Blelloch]\n3. Do these indices generalize as dataset changes or increases in size? How do we quantify this? I am especially concerned about the quantization and clustering schemes and how they are bootstrapped and maintained over time. These details are missing in the paper.\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ObI6xv1BB1v", "reviewer": "Reviewer_GRS7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper looks at the Approximate Nearest Neighbor (ANN) search problem for high-dimensional dynamic data. The authors propose a new benchmarking framework to fill the gap in selecting the satisfied ANN method for dynamic ANN search. They focus on two requirements: online data collection and online feature learning, and identify six additional measures for the dynamic search problem. Finally, they evaluate five ANN methods and show that the proposed benchmarking framework can determine which ANN method is most satisfactory for a given dynamic search problem.  ", "summary_of_the_review": "In summary, I think this paper is well-written and has a clear motivation, but currently, I feel the technical depth is limited, and I have some concerns about the experiments. Thus, I initially provided a borderline reject.", "strength_and_weaknesses": "Strengths:\n\n1. The motivation is clear. Even though there exist a few benchmarking frameworks for ANN search, they are designed for static search problem that assumes the dataset is fixed. It seems that this work is the first to consider the dynamic search problem. \n\n2. The authors identify many measures for the dynamic search problem and use experiments to confirm that these measures are valid for the benchmarking framework they proposed.\n\n3. The paper is well-written and easy to read.\n\nWeaknesses:\n\n1. My primary concern is that the technical depth seems somehow limited. I appreciate the six new measures they proposed and the experiments for the five ANN methods they conducted, but most of the measures are straightforward, and all five ANN methods are open-sourced. The framework will be more promising if they can build a cost/analytical model to analyze the relationships of different measures.\n\n2. In the 2nd paragraph of Section 2, they provide many examples of online data collection and online feature collection. It would be more convincing if they could add references for support. \n\n3. In the experiments, what are the datasets they used for online data collection and online feature learning? They provide the dataset statistics, but I cannot find what datasets they used.\n\n4. The experiments only report the curves of speedup and recall. Can they also report the results for other measures, such as the event processing time, initialization time, and memory footprint?\n\n5. For the last experiment (Figure 5), can you explain why the five ANN methods fail to exploit mutual information between consecutive search batches?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4wqcIbYmJC2", "reviewer": "Reviewer_vEWF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper identifies the key measures of high-dimensional search problems and utilizes them to benchmark the ANN methods for dynamic search. The paper benchmarks state-of-the-art ANN algorithms - HNSW, SCANN, k-d Tree, IVFPQ, and Annoy on speedup against the brute-force near neighbor. The online data collection (adding items online) and online feature learning (updating item features online) aspects are covered for the dynamic search. ", "summary_of_the_review": "The paper is written well and addresses the need for benchmarking on dynamic search. Some additional experiments and clarity will make it an excellent paper. ", "strength_and_weaknesses": "Strengths:\n1) The paper addressed the much-needed benchmark space for the ANN algorithms. \n2) The benchmarks are provided for the additional metrics for dynamic search, i.e., Event type, event processing time, event frequency, event batching, Search frequency, and search batching.\n\nComments:\n1) I might have missed it, but the details about the datasets need to be clarified. \n2) More ANN algorithms: The authors have done a great job including many well-known ANN algorithms in the benchmark. They have included Quantization based, Tree-based, and Graph-based algorithms. Including pure partitioning-based methods like IVFFLAT, LSH table, or learned indices like Neural LSH (Dong et al., 2019) and BLISS (Gupta et al., 2022) will be great.\n3) Are there any similar benchmarks for dynamic search problems?\n4) It will be great to have a table like Table 1 with different methods listed with their performance against the given measures. The performances can be depicted by ranks or markers like ++ , + , - - etc. \n\n*Learning sublinear-time indexing for nearest neighbor search. arXiv preprint, arXiv:1901.08544, 2019. URL http://arxiv.org/ abs/1901.08544.\n\n*A billion scale index using iterative re-partitioning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD ’22, pp. 486495, 2022.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject