- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes to accelerate nearest-neighbour (NN) search by changing the metric of the data before the search. The proposition is to map the original dissimilarity on the data to a canonical -metric projection of Segarra et al. By doing so the authors obtain a new distance where the length of a path is the norm of its edge weights. A VP-tree is then built in the projected space and searched with pruning rules adapted to the -triangle inequality.
Critical strengths
- Changing the metric structure of the data so that tree pruning and thus, NN-search becomes easier is an interesting direction.
- Build time and memory are reported along with queriers per second. The appendix includes additional experiments that openly show the behavior of the method over several dissimilarities and at large .
Critical weaknesses
Theory
Theorem 1 does not apply to the proposed method
Theorem 1 is correct as stated: if one ultrametric distance on is used both to build and to search the tree, the search finds a nearest neighbour. The problem is that the proposed method, does not have in general has such an ultrametric distance. The proof of this theorem, which goes through Proposition 4, relies on the strong triangular inequality. For a triangle , the side comes from the tree, through the radius . The other two sides, and , are the query distances used during the search. In the methods of Sections 2.4 and 3.1, these two distances come from two different projections:
- the tree distance is built by setting
- the query is compared through , the projection of the graph that also contains (Section 3.1, Prop. 1).
Adding to the graph adds all paths that go through the query: for
The two projections therefore disagree when the query lies between two groups of points. For such a pair, . The inequality used in the proof then fails, and the rule (∞-CI) can discard the branch that contains the NN.
Proof of Theorem 2 is incomplete
The appendix proof (App. E.1) which is called "Existence and uniqueness" proves only existence. Equation (45) requires that satisfies the -triangle inequality which doesn't appears obvious to me.
The axiomatic justification is weak.
Axioms (A1)–(A2) implies that only one map satisfies them. They are not related strongly to what matters for search: recall, tree balance, number of ties, etc. Those axioms also ruled out other ultrametric fits without being tested at least experimentally to compare the performances.
Minor
The second inequality in (63) is false in general: it compares a path to with the shortest path to . The statement itself is true, since any path from has a first edge and, for , any additional edge makes it strictly longer.
Novelty with respect to prior work
The canonical -projection given in Algorithm 5 is the minimax path distance, i.e. the subdominant ultrametric or the single-linkage cophenetic distance. It can be computed in through a minimum spanning tree (Gower & Ross, 1969), compared with for the Floyd–Warshall approach of Algorithm 5. Neither other recent methods of the litterature on ultrametric fitting (Cohen-Addad et al, 2020) or space partitioning for NN-search are compared (e.g.(Dasgupta et al, 2013) or (Dong et al, 2020)).
Algorithms
- For vantage points, Algorithm 1 picks a vantage point at random. The Remark 2 below acknwoledge the fact that the the choice "may have a significant effect in practive" and mentions an heuristic to choose it. The paper never says which rule the experiments use, and there is no ablation.
- Algorithm 1 takes the median over all , which includes , unlike eq. (10). Also, does not exclude . For this gives and , so the recursion never terminates.
Presentation
The paper is very hard to read.
- Assertions in place of arguments: "(very justifiable) Axioms" (l.68); "the data is what the data is" (l.59–60) etc. Those should be detailed or deleted if bringing nothing to the paper.
- Numbering and cross-references. I give here only a sample of examples. "Theorem 1" appears twice in the appendix with different content. Proposition 5 repeats Proposition 1. Proposition 12 (l.1726) reference to Proposition 1. Proposition 4 refers to "(4)" for the strong triangle inequality, which is eq. (3), and its proof uses "(∞-CI)" where (∞-CO) is meant (l.904).
- Typos: "bearest", "neioghbor", "tims", "lmited", "REULTS", "ouperformed" etc.
- The conclusion and the related work are both in the appendix.
Questions for authors
- In the exact-projection experiments is the tree built on and searched with ? Or is it rebuilt for each query on ?
- How are vantage points chosen in the reported experiments: at random, as in Algorithm 1, or with a spread heuristic? How sensitive are the quality metrics to this choice?
- What are the end-to-end build times, including the projection on the training subset, the kNN graph and MLP training? What is the QPS when the query embedding is included?
- Why does increase during training in Fig. 23? What happens if is trained with the contrastive loss only?
- How large is on the real datasets that you choose?
5 comments
Tree Construction and Tree Search
The reviewer asks if the tree is reconstructed for every query in the exact-projection investigations (Figure 14). The answer is yes. We do rebuild the tree for every query in these experiments.
Notice that these experiments are intended to showcase theoretical soundness. They are separate from our benchmark search results that construct the VP tree only once.
Selection of the vantage points
The reviewer asks for more detail on the selection of vantage points during construction of the VP tree.
During construction of the VP tree, we select the vantage point that maximizes the threshold . This is motivated by the fact that accuracy of the tree depends on whether the generalization of the learned map falls below the minimum threshold (Figure 4).
We compare the use of this technique to random choice of vantage points and maximum threshold variance choice of vantage points:
Table 1. We construct the VPTree with different vantage point selection rules and report the Recall@1.
| Rule | SIFT | Deep1B | GIST | Kosarak |
|---|---|---|---|---|
| Random election | 0.909 | 0.906 | 0.902 | 0.893 |
| Maximum variance | 0.911 | 0.908 | 0.913 | 0.893 |
| Maximum threshold (ours) | 0.917 | 0.903 | 0.921 | 0.900 |
We see that proper choice of vantage points has a small effect on recall.
Training and Index Building Times
The reviewer requests that we report times for computing q-metric projections, for training the estimator of q-metric distances and for building the VP tree. Times in seconds for the 4 large-scale examples are reported in the table below:
Table 2a. We report the building times of Projection, Training and Building phases in seconds.
| SIFT | Deep1B | GIST | Kosarak | |
|---|---|---|---|---|
| Projection | 33 | 43 | 87 | 34 |
| Training | 43 | 40 | 36 | 50 |
| Tree build | 8 | 10 | 17 | 2 |
| Total | 84 | 93 | 140 | 86 |
These costs are incurred only once per dataset. It is incorrect to assign their cost to individual queries. This is just a function of how many queries are conducted. In practice, preprocessing costs are amortized over a very large number of queries.
An important observation is that if we add points to the dataset, we recompute the VP tree but do not necessarily recompute the projection and learned estimator of q-metric distances. In fact, in all of the four datasets in the above table we compute the projection and train the distance estimator on a random subset of the entire dataset containing less than 10% of all points. We observe that this is enough to learn a distance estimator that generalizes well to the entire dataset (see Figure 4). These estimated distances are the ones used to build the VP tree.
Tension between Contrastive Loss and
The reviewer is concerned about the increase of the loss reported while training the approximate projection of the SIFT dataset.
We train the distance estimator with a loss that is the sum of two different terms. Each of these terms may increase during training as long as the total loss (their sum) decreases.
The reviewer also asks for an ablation experiment where the approximate projection is trained by using only the contrastive loss. Results are reported below:
Table 3. We train an approximate projection with only a contrastive loss , and report the Recall@1 achieved by the index.
| Model | SIFT | Deep1B | GIST | Kosarak |
|---|---|---|---|---|
| Original | 0.9 | 0.9 | 0.9 | 0.9 |
| 0.4 | 0.6 | 0.3 | 0.7 |
Because the contrastive loss only accounts for relative neighbour ordering but does not encourage q-metric structure, it does not induce sufficient structure for effective search.
Minimum Projected Distance
The reviewer asks us to report the minimum distance produced by the canonical projection when .
Proposition 1 states that this distance is the same as the minimum distance of the original dataset. I.e., that minimum distances are preserved under projection. This is a direct consequence of Axioms 1 and 2. The following table confirms this statement:
Table 4. We perform the canonical projection with and report its minimum distance.
| SIFT | Deep1B | GIST | Kosarak | |
|---|---|---|---|---|
| Min E_\infty | 0.54 | 0.88 | 0.83 | 0.33 |
| Min original d | 0.54 | 0.88 | 0.83 | 0.33 |
Theorem 1 My concern was specific: the tree is built from on , while the query is compared through on , where paths through can shorten distances. The strong triangle inequality used in Prop. 4 then fails across the two. Also it would be useful for the reader to state explicitely that the bound of Thm. 1 doesn't carry over the proposed experimental pipeline. It would also be good to report how often the pruning rule discards the branch containing the true nearest neighbor and how this fraction may vary with tree level.
Novelty My point was not that these papers propose the same ultrametric. Dasgupta and Sinha and Dong et al. are partition-based NN search methods, which solve the same problem as your VP-tree, and Cohen-Addad et al. fit ultrametrics in another way.
The Axioms Do Not Relate to Search First of all, I agree that other properties are implied or incompatible once uniqueness holds. You're reply states that Axiom 2 implies the preservation of the recall is a bit contradictory with what is noted in Appendix F.2 (line 1553). Please state those limitations directly in the main body. An experiment comparing the canonical projection with another ultrametric fit would also benefit the paper.
Incomplete Proof of Theorem 2 Thank you for adding the uniqueness proof. Please also fix the justification of (45) as I pointed out in my review.
We thank the reviewer for his time, effort and valuable comments.
Theorem 1 Does Not Apply to the Proposed Method
The reviewer is correct that Theorem 1 considers cases in which ultrametric distances are available. In most practical situations, this is not the case and we propose the use of a learning parametrization to estimate ultrametric distances (or q-metric distances in general).
Concluding from these facts that “Theorem 1 does not apply to the proposed method” is, however, an overstatement. Theorem 1 motivates our approach. This is analogous to, for example, the relationship between HNSW and Small World Graphs (SWGs). In general, data does not follow an exact Small World Graph, however an approximate SWG constructed by HNSW is efficient for search. I.e., SWGs motivate HNSW in more or less the same way in which Theorem 1 motivates our proposed approach.
The Axioms Do Not Relate to Search
Axiom 1 establishes that the q-metric structure is preserved by the projection. This implies that if the data is already efficiently searchable, we do not alter the structure of the data.
Axiom 2 does not increase distances. This implies the preservation of nearest neighbor information, thus the preservation of recall.
To the extent that preserving efficiency and recall matter for nearest-neighbor search, the axioms are well justified. Other axioms may be imposed, but the uniqueness result dictates that other properties will be either implied by Axioms 1 and 2 or result in the nonexistence of a projection operator. We will clarify these connections in the revised manuscript.
Novelty
We are not sure what the reviewer means by “novelty with respect to prior work.” Our novelty is proposing the use of q-metric projections for search. We do not claim that the method for constructing q-metric projections is novel. In particular, the reviewer is right that MST is a more efficient method for constructing the ultrametric (but not q-metrics), but this is not the point of the manuscript.
The other three contributions mentioned by the reviewer do not overlap with our paper. Cohen-Addad et al. (2020) does not use our ultrametric space and Dasgupta and Sinha (2013) and Dong et al. (2020) do not propose an ultrametric. We do not see much overlap with either of these papers. We will clarify this in the revised version of the paper.
We do not understand which comparisons you would like us to add relative to these contributions. Our paper already includes comparisons with state of the art search methods.
Algorithm 1 is Wrong
Algorithm 1 is correct as stated: Line 3 reads, “choose a vantage point” from X, which is in general agreed to mean that we remove the vantage point from X.
We will nevertheless update Line 4 in the revised paper to write MEDIAN_X \ {v} instead of MEDIAN_X to make this convention more explicit.
Incomplete Proof of Theorem 2
The reviewer states that the proof of Theorem 2 establishes existence but not uniqueness. This is correct. We will add the proof of uniqueness to the revised manuscript.
Notice that this theorem and its proof are originally from Segarra el al (2019) and are included here for completeness. Thus, this is a simple problem to fix. We do accept that not including this proof was an oversight in preparing the manuscript. Please accept our apologies.
The Paper is Very Hard to Read
The reviewer points out some typos and opinions. Typos will be corrected and opinions will be removed.