Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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).

strength_and_weaknesses: Pros:

1) 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.

2) 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.

3) 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.

Cons:

1) 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.

2) 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.

3) 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.

clarity,_quality,_novelty_and_reproducibility: The organization and clarity of the paper is excellent. The authors build their case carefully, showing why and how dynamic search cannot be accommodated by existing frameworks designed around static ANN search. However, the proposed framework can be regarded as a relatively straightforward extension of static benchmarking platforms. Although the paper does not give the full details of the implementation, the authors have stated their intention to make it freely accessible to practitioners.



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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.  
strength_and_weaknesses: Strengths:

1. 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. 

2. 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.

3. The paper is well-written and easy to read.

Weaknesses:

1. 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.

2. 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. 

3. 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.

4. 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?

5. For the last experiment (Figure 5), can you explain why the five ANN methods fail to exploit mutual information between consecutive search batches?
clarity,_quality,_novelty_and_reproducibility: Overall, this is a well-written paper with a good framework that looks well-motivated. However, considering this paper's strengths and weaknesses, the quality and novelty do not seem very strong to me.

For the reproducibility concern, as they declare they will make the code available, the reproducibility should be somewhat assured. 
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Strengths:
1) The paper addressed the much-needed benchmark space for the ANN algorithms. 
2) 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.

Comments:
1) I might have missed it, but the details about the datasets need to be clarified. 
2) 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.
3) Are there any similar benchmarks for dynamic search problems?
4) 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. 

*Learning sublinear-time indexing for nearest neighbor search. arXiv preprint, arXiv:1901.08544, 2019. URL http://arxiv.org/ abs/1901.08544.

*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.


clarity,_quality,_novelty_and_reproducibility: The paper is written well and clear. The efforts made in this direction of benchmarking is needed. Code is provided.
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strengths:
1. Authors list various parameters of importance to dynamic setting.
2. Authors identify the lack of comparison for dynamic indices as a major missing piece on ANN literature. The research is timely.
3. Authors identify that its possible to get substantial speed up over 

Weaknesses:
1. The authors miss an opportunity to present clear and comprehensive experiments. A few examples of points important for dynamic indices but missed here:
- How do batch-build vs streaming-build indices compare in quality? 
- 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?
2. 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.
  - Proximity Graph Maintenance for Fast Online Nearest Neighbor Search [Zhaozhuo Xu, Weijie Zhao, Shulong Tan, Zhixin Zhou, Ping Li]
  - FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search [Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, Harsha Vardhan Simhadri]
  - Parallel Nearest Neighbors in Low Dimensions with Batch Updates [Magdalen Dobson, Guy Blelloch]
3. 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.



clarity,_quality,_novelty_and_reproducibility: Suggestions for improving paper:

**Clarity**
1. The settings "online feature learning" and "online data collection" need to be explained more clearly. What does it mean for the ANN index? Presumably "online data collection" just means that new points are inserted into the index? Does online feature learning mean that the underlying model is being trained and this 
2. More clarity needed on temporally dependent events -- what are the sources of these data and how are the points correlated?
3. IVFPQ and SCANN: Is the quantization changed over time? How is the initial quantization computed when zero points are provided? Does the initial quantization generalize over time? Same question for clustering in IVF. 


**Quality**
1. The main parameter varied in Fig 4 is inserts:search ratio. Isn't it clear that dynamic ANN indices can outperform bruteforce? I feel there are other experiments that merit more attention than this plot. See the remaining points:
2. What is the total pool size of points from which the experiments sample data? You could use the 1B scale datasets released at big-ann-benchmarks.com and explore various permutations of insertions and resultant effects.
3. Lack of parallelism. Support for parallelism is an important feature of algorithms and should be measured. In practice, a single dynamic index would be deployed on a multicore machine and could be supporting changes and searches at the same time.
4. The conclusion could be more specific and focused on the learnings from the experiments as opposed to general comments on the ANN space.
5. It unclear that FAISS IVFPQ as used in this paper has been tuned well. There are recent discussions on how FAISS IVFPQ can compete with SCANN: See https://medium.com/@kumon/similarity-search-scann-and-4-bit-pq-ab98766b32bd and https://github.com/facebookresearch/faiss/wiki/Fast-accumulation-of-PQ-and-AQ-codes-(FastScan)
6. Please consider taking the best 2 or 3 algos for each dataset in ann-benchmarks.com to ground the choice of algorithms you benchmark.

**Novelty**
1. The authors don't propose novel algorithms but describe an evaluation framework, which is OK. Given the lack of evaluation for dynamic ANN, this work is a good first step.

**Reproducibility**
1. Consider organizing the paper and code around (A) APIs a new algo must support to  be measured in your framework, and (b) use cases and datasets that that the eval framework considers important. These eval code should describe and support these two orthogonally.
2. What are the datasets used in this paper and their source? 
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: (a) Explains the issues involved in comparing algorithms for finding approximate nearest neighbors, and provides benchmarking code that measures numerous metrics.

(b) Thorough and sensible work.

(c) Only tangentially relevant to ICLR. Experiments are on small datasets not of clear practical relevance. Reviewers do not see new insights.

Comments by the AC: It would be good to include methods for finding exact nearest neighbors, since these can be sophisticated and effective. See for example "A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy" (2020) and "Fast nearest neighbor retrieval for bregman divergences" (2008). (Neither the AC nor any reviewer is an author of these papers.)

Although the datasets are dynamic, the experiments are static, i.e., offline from whatever the application would be. The authors would have more scope for novel insights if they provided an online tuning method. In other words, given one or more nearest neighbor algorithms, how  to optimize their performance adaptively as time goes by in the application? This adaptation could use bandit methods, Bayesian optimization, and/or more.

Every real-world applications is different and it is unclear which of several static benchmarks is most relevant. Therefore, and online tuning method would be more useful for applications.
justification_for_why_not_higher_score: Limited relevance to ICLR and limited novel insights.
justification_for_why_not_lower_score: Good quality work.
Decision: Reject