Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presents a formal analysis for the impact of graph reordering (i.e., ordering the in-memory storage sequence of graph node embeddings) on the cache efficiency of near neighbour searches using near neighbour graphs. The connection of the graph ordering (i.e., memory layout of the graph nodes) and the cache complexity is formulated, based on which the cache complexity of the Gorder (Wei et al., 2016) is analysed and two other graph ordering (Corder and Porder) are proposed. Experimental results on large real datasets confirm the effectiveness of the analysis and the importance of graph reordering for near neighbour search efficiency. 
strengths_and_weaknesses: Strengths:
1. The paper has presented a solid analysis for the impact of graph reordering (i.e., ordering the in-memory storage sequence of graph node embeddings) on the cache efficiency of near neighbour searches using near neighbour graphs. 

2. Experimental results on large real datasets are presented, with an interesting discussion on the results. 

3. Source code of the paper is available. 

Weaknesses:
1. The proposed method Corder is ineffective as discussed in the experimental results. Perhaps this method can be dropped to make room for adding more details on the experimental settings to the main content of the paper. 

2. The other proposed method Porder is only somewhat better than the existing method Gorder (Table 5).

3. A lot of contents have been included as supplementary material, which makes the paper somewhat difficult to follow. 

Typo: "degree-based groupingFaldu et al. (2019)"; "Studies show that Studies show that"
questions: A lot of experimental results focused on Gorder (Wei et al., 2016). How will the results look like when Porder is also included in those experiments (Figures. 3&4, Tables 1&3)?
limitations: The paper included an interesting discussion on the results and limitations.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies practical performance of different methods for rearranging the node layout in the memory for graph-based approximate nearest neighbor search algorithms (HNSW specifically). It also proposes a simple modification of the existing methods based on query profiling. The paper claims to have up to 30-50% improvement in query latency on 100M datasets and is accompanied by code (though not clear if it is going to be released).
strengths_and_weaknesses: Strengths:
- Simple change that is very likely to be agnostic to the type of the graph algorithm used.
- Sizable gains from the algorithm on large datasets.
- Source-code (hopefully will be released with the publication - not clear from the text).
- Long discussions of the results.

Weaknesses:
- The paper does not have a clear description of the methods (no pseudocode or even text description of step-by-step actions). I guess the readers are suggested to follow the cited papers, but IMO there should be at least a sketch of the best solution.
- The source of 1000 queries for POrder not discussed in the paper. Were they used from the train set or the test set?
- There is no implementation of POrder in the code, which is confusing. The code also has bugs (e.g. nonexistent “-openmp” flag), it does not compile without fixing the dependencies (could had been fixed if you provide Dockerfile) and there are errors in its description.
- Judging the code, the construction is done in a single thread. If index construction time provided in the paper is for this regime (which is not clear from the paper, but seems to be the case), it should be redone in the multi-threaded regime.

questions: I would recommend improving the code presentation and completeness. The approach is focused on hardware optimization, so having an exact working code seems to be essential for the further research from other teams.

It would be nice to check some of the assumptions of the paper, like that the speedup is from the hardware prefetcher. E.g. turning the hardware prefetcher off and/or experimenting with the size of the vectors. 

Misc: “Studies show that Studies show that” typo
Please use “nearest neighbor search index” or similar instead of "near neighbor index". "near neighbor index" is used in other contexts, and I was able to find the public version of this paper in google top results just by searching for "near neighbor index" .

limitations: I do not think there is any negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes to use graph reordering to improve the cache locality of graph-based nearest neighbor search algorithms. An analysis is conducted to show why graph reordering works and the experiments show that graph reordering significantly improves performance.
strengths_and_weaknesses: Strength

1.	Graph-based nearest neighbor search algorithms are very popular and graph reordering improves the performance of graph-based nearest neighbor search algorithms.

2.	Although the conditions are restricted, the analysis explains why graph reordering improves performance.

3.	The profiling-based ordering scheme makes sense.

Weakness

1.	The authors should dig deeper to show why recording improves performance. Currently, the explanations are vague (e.g., due to software prefetcher and auxiliary functions). The authors may want to make them more specific by explaining how software prefetcher works or conduct some experiments to show where the reduction comes from. 

2.	I believe that graph reorder works for graph-based algorithms in general. But it helps to show by experiments that graph reorder improves the performance for algorithms other than HNSW (e.g., NSG or NGT).

3.	The legends in the figures are too small to read.


questions: See weakness.
limitations: Yes
review_title: null

Meta-review: metareview: This paper studies how to order in-memory sequences for graph embedding. There was a positive consensus that the studied problem is interesting and results are sufficiently discussed. There were some concerns on missing results, which were addressed during rebuttals.
confidence: Certain
Decision: Accept