Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality

• p. 5 Fact 1

  Γ(1 + n/p)

• p. 5 Fact 1

  V^d_p(r) = (2Γ(1+1/p))^d / Γ(1+n/p) r^d

• p. 5 Fact 1

  V_p^d(r) = (2Γ(1+1/p))^d / Γ(1+n/p) r^d

Judge's note: The page 5 image shows Γ(1+n/p). With d in place of n the formula reduces for p=2 to π^{d/2}/Γ(1+d/2) = 2π^{d/2}/(dΓ(d/2)), which is the companion formula printed next to it. With n it does not, and the volume would depend on the data-set size. Check with d=1, p=2: the correct value is 2r, while n=3 gives about 1.333r.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 9 Proof of Lemma 1, case 2(c)

  For any p ∈ P − S_i, d(p, a) ≥ r. Since q ∈ B(a, r_k), we have d(q, a) ≤ r_k = r/(1+ε) ≤ d(p,q)/(1+ε).

Only the authors can say what is right here.

Judge's note: Read on p9 and reworked. The triangle inequality gives only d(p,q) ≥ d(p,a) − d(q,a) ≥ r − r/(1+ε) = rε/(1+ε). Checked counterexample on the line with r=1, ε=1/2, so r_k = 2/3: A_i = {a} with a = 0. The cover condition |P∩B(a,r)| ≤ b|A_i| < 2 forces S_i = {a}, which is consistent. Query q = 2/3, so q ∈ B(a,r_k) and branch (c) applies. Take p = 1.01 ∈ P − S_i, with d(p,a) = 1.01 ≥ r. Then d(p,q) ≈ 0.343, so r/(1+ε) ≈ 0.667 is not ≤ d(p,q)/(1+ε) ≈ 0.229. Search(q,S_i) returns a at distance 0.667, a ratio of about 1.94 > 1+ε to the true nearest point. The step is false as printed for ε < 1, which leaves Lemma 1 (correctness of Search) without a valid proof in that range. Severity S1 under the derivation rule.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 10 Section 4, first paragraph

  Facts 2 and 4 (Appendix A)

• p. 10 Section 4, first paragraph

  by Fact 3 (Appendix A)

• p. 20 Appendix B heading

  B Auxiliary facts

• p. 10 Section 4, first paragraph

  Also, by Fact 3 (Appendix A), we can reduce

Judge's note: p10 shows both pointers to Appendix A. p18 shows Appendix A is 'The Dimension Reduction Technique' (Definition 8 onward). p20 shows Fact 3 (Johnson-Schechtman) and Fact 4 (Linial, London, and Rabinovich) under 'B Auxiliary facts'. Fact 2 is stated on p10 just above Section 4.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 20 Fact 3

  For any 1 ≤ p < 2 and ε > 0

• p. 10 Section 4, first paragraph

  to l_1^{O(d)} for any p ∈ [1, 2]

• p. 10 Section 4, first paragraph

  by exploiting Facts 2 and 4 (Appendix A)

• p. 10 End of Section 3.2

  Fact 2 For any PLEB instance (C,r) generated by a ring-cover tree

Judge's note: The page 10 image shows Fact 2 printed just above Section 4, and the two pointers that both say "(Appendix A)". The page 20 image shows Facts 3 and 4 under the heading "B Auxiliary facts". In the layout text, line 204 refers to "Section A of the Appendix" for the random-projection material, so Appendix A is a different section. The pointer should read Appendix B (and Section 3 for Fact 2). A secondary point is also visible on the page: Fact 3 is stated "For any 1 ≤ p < 2", while Section 4 uses it to reduce l_p^d to l_1^{O(d)} "for any p ∈ [1, 2]", which includes p = 2. This is a minor range mismatch the authors could clarify; whether p = 2 follows from other known embedding results rests on outside knowledge, and the paper does not cite any for it.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 18 Reference [63]

  Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 1993

• p. 15 Reference [3]

  Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 1993

Only the authors can say what is right here.

Judge's note: Pages 15 and 18 images. The list is inconsistent with itself: [3] makes 1993 the Fourth SODA, and [5] and [24] make 1994 the Fifth, so a 1993 meeting cannot also be the Second. Rests on outside knowledge: whether the ordinal or the year in [63] is the error (Yianilos's paper is believed to be in SODA 1993, the Fourth).

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 18 Reference [53]

  Journal of the ACM 31(1983), pp. 852-865

• p. 16 Reference [34]

  Journal of the ACM, 31(1984):538–544

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: that a J. ACM volume falls within a single year, and that Megiddo's paper is in J. ACM 30 (1983). Inside the files, page 16 [34] and page 18 [53] give volume 31 two different years. Only the authors can say which volume or year is right.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 4 Overview, paragraph on Section 4

  with preprocessing cost only linear in d and sublinear in n

• p. 4 Proposition 1

  Õ(n^{1+1/(1+ε)} + dn) preprocessing

• p. 11 Theorem 5

  uses O(dn+n^{1+ρ}) space and O(n^ρ) evaluations

• p. 11 Theorem 4

  O(dn + n^{1+ρ}) space and O(n^ρ) evaluations

Judge's note: The page 4 image shows the sentence and Proposition 1. The page 11 image shows Theorem 5's O(dn+n^{1+ρ}) space and O(n^ρ) query evaluations. The preprocessing is superlinear in n; only the query cost is sublinear. The sentence attributes sublinearity to the wrong quantity.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 7 Proof of Theorem 2, fourth claim

  r ≤ γΔ(S)/((1+γ) log_b n)

• p. 7 Proof of Theorem 2, fourth bullet

  r ≤ γΔ(S)/((1+γ) log_b n) — Since Δ(A) ≤ Δ(S) + r log_b n = (1+γ)Δ(S).

• p. 7 Algorithm Cover, first line

  r ← γΔ(S)/log_b n

• p. 6 Definition 6

  there exists an r ≥ dΔ(A)

Only the authors can say what is right here.

Judge's note: Page 7 image (algorithm and claims) and page 6 image (Definition 6: 'there exists an r ≥ dΔ(A)'). r divided by the claimed bound equals 1+γ > 1, so the printed inequality is false for every γ>0. The justification after the dash (Δ(A) ≤ (1+γ)Δ(S)) would give r ≥ γΔ(A)/((1+γ)log_b n). Both the direction of the inequality and the use of S in place of A are wrong as printed. The intended claim is recoverable, subject to C013.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 7 Proof of Theorem 2, fourth claim

  Since Δ(A) ≤ Δ(S) + r log_b n = Δ(S) + γΔ(S)

• p. 7 Proof of Theorem 2, fourth bullet

  Since Δ(A) ≤ Δ(S) + r log_b n = (1+γ)Δ(S).

• p. 7 Theorem 2 statement

  constituting a (b, δ, γ/((1+γ) log_b n))-cover for S

• p. 7 Corollary 1, property 2

  d = 1/((2β+1) log_b n)

Only the authors can say what is right here.

Judge's note: Page 7 image. My reworking: for a ∈ A_j and a' ∈ A_j', d(a,a') ≤ d(a,p_j)+d(p_j,p_j')+d(p_j',a') ≤ 2r log_b n + Δ(S). I checked the reviewer's example: two depth-4 binary trees with unit edges, roots 11.909 apart, n=62, b=2, γ=δ=1/2. It is a (γ,δ)-cluster (31 ≤ 31 points in each radius-5.954 ball). The algorithm's r is 1 and its inner loop grows 1→3→7→15→31, so each A_j is a whole tree. Then Δ(A)=19.909 > Δ(S)+r log_b n = 17.863, so the printed step is false. However, Definition 6 only requires that some r ≥ dΔ(A) exists, and in this example r = 1.115 also satisfies the cover conditions. So the theorem statement is not refuted here; only the step, and the constants carried into Theorem 2 and Corollary 1, are unjustified as printed.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 7 Proof sketch of Theorem 1, first paragraph

  It follows that there must exist a choice of r (say r_p) such that f^∞_p(r_p) = f^0_p(r_p).

Only the authors can say what is right here.

Judge's note: Page 7 and page 6 images. A monotone increasing and a monotone decreasing integer step function can cross without ever being equal. I checked the counterexample: p plus 4 points at distance 1 from p (pairwise distance 2), n=5, β=2. Then (f^0,f^∞) = (1,4) for r<0.5, (1,0) for 0.5≤r<1, and (5,0) for r≥1, so they are never equal. With α=0.4, no ring separator exists at p or at the other points, so the hypothesis that (1) fails is met. The proof needs only a radius where both counts are ≤ αn, which exists in this example, but the printed step is false and the proof does not establish the repaired version. The theorem's validity is not refuted.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 8 Section 3.1, Case 2

  r_k = γΔ(A)/(log_b n(1+ε)) = r/(1+ε)

• p. 7 Algorithm Cover

  r ← γΔ(S)/log_b n

• p. 8 Section 3.1, Case 2

  Notice that r_k = γΔ(A)/(log_b n(1+ε)) = r/(1+ε).

• p. 8

  t r i r i for i f k g where k log log b n Notice that r k

Only the authors can say what is right here.

Judge's note: Reworked from p7 and p8. r_0 = (1+1/ε)Δ(A) and (1+ε)^k = (1+ε)(1+1/ε)log_b n/γ, so r_k = γΔ(A)/((1+ε)log_b n); the first equality holds. The cover radius built by Algorithm Cover on p7 is r = γΔ(S)/log_b n. Since S ⊂ A, Δ(A) ≥ Δ(S), and by the p7 bullet Δ(A) ≤ (1+γ)Δ(S). So r_k = (Δ(A)/Δ(S))·r/(1+ε) ≥ r/(1+ε), with equality only when Δ(A) = Δ(S). As printed, the second equality does not hold for the cover the paper constructs. Lemma 1 case 2(c) uses r_k = r/(1+ε). The step can be repaired by defining r_0 from Δ(S) or from r, so the stated asymptotic results are not affected; hence S3. The repeated 'log' flagged by a text rule is the k = log_{1+ε}(...log_b n...) expression, not a duplicated word.

Second check: another model agreed, code check

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 8 Section 3.1, Case 2

  and S_0 = S − A

• p. 9 Procedure Search, step 2(a)/(b)

  Search(q, P − A)

• p. 8 Case 2

  S_0 = S − A

• p. 9 Procedure Search 2(a)

  compute p = Search(q, P − A)

Judge's note: Viewed p8 (Case 2), p9 (Search 2(a),(b)), p7 (Algorithm Cover and the claim S ⊂ A = ∪_j A_j) and p6 (Definition 6, which requires S ⊂ A). S − A is therefore empty, while the search procedure and the space recurrence on p9 (S(n − |A|)) both use P − A. This is a notational error with an evident fix.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 11 Section 4.2, first paragraph

  YES if P ∩ B(q, r2) ≠ ∅ and NO otherwise

Only the authors can say what is right here.

Judge's note: p11 image confirms the wording. Property 1, the proof of Theorem 5 and Definition 7 involve r1 and guarantee YES only for p* ∈ B(q,r1), and NO only when no point of B(q,r2) is hit. As printed, the definition omits the gap between r1 and r2 and misdescribes the problem Theorem 5 solves.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 12 Proposition 4

  h_i((b_1, . . . b_d)) = b_i, i = 1 . . . n

• p. 12 Proposition 4

  i = 1 . . . n

• p. 12 Proposition 4

  H = {h_i : h_i((b_1,…b_d)) = b_i, i = 1…n}

Judge's note: p12 image confirms 'i = 1 . . . n'. Points of H^d have d coordinates, and the sensitivities 1 − r/d and 1 − r(1+ε)/d assume a uniform choice among d coordinates.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send

• p. 18 Definition 8

  (1 − ε)d(p, q) < d′(f(p), f(q)) < (1 + ε)d(p, q)

• p. 18 Appendix A, Definition 8

  We call c the distortion of the embedding; if c = 1, we call the embedding isometric.

Judge's note: Page 18 image confirms that the defining inequality has only ε and that c is never related to it. Page 19 then uses '(1+ε)-embedding', which suggests c = 1+ε was meant. Even read that way, the strict inequalities make c = 1 (ε = 0) impossible for p ≠ q, since d < d′ < d cannot hold. The definition needs c written into the condition, with non-strict bounds for the isometric case.

Second check: another model agreed

Report a problem with this finding

This finding is

wrong right unclear or overstated already corrected (erratum, later version)

I am an author of this paper Send