Similarity Search in High Dimensions via Hashing

• p. 2 Introduction, right column

  in some cases even by several orders of magnitude

• p. 10 Section 4.3

  which is one to two orders of magnitude larger

• p. 10 Section 4.3, right column

  being up to an order of magnitude faster

• p. 10 Sec 4.3

  one to two orders larger

Only the authors can say what is right here.

Judge's note: Page 2 (right column) has the 'several orders of magnitude' wording. Page 10 Sec. 4.3 says SR-tree used 1310 blocks at n=200,000, 'one to two orders of magnitude larger' than LSH. In Fig. 9(b) on p.11 LSH is about 35–40 blocks at 200k, roughly a factor of 33. Against the sampled SR-tree the text says 'up to an order of magnitude'. The colour-histogram figures (Figs 5 and 7) show gaps under 10x. No reported result reaches 'several' orders of magnitude, so the introduction claims more than the results show. This is a wording issue.

Second check: another model agreed

• p. 3 Section 3, assumption 2

  all coordinates of points in P are positive integers.

• p. 7 Data Sets paragraph

  All coordinates are clearly non-negative

Judge's note: Page 3 assumption 2 says 'positive integers', and Fact 1 uses the set {1...C}. Page 7 (bottom left to top right) says 'non-negative integers, as assumed in Section 3'. Histogram counts can be zero. The unary embedding also works for 0, so nothing in the method breaks. Still, the cross-reference claims an assumption that differs from the one printed. This is a minor consistency point.

Second check: another model agreed

• p. 4 Section 3.1, query processing

  until we either encounter at least c · l points

• p. 5 Property P2

  containing only points from P′ is less than cl.

Only the authors can say what is right here.

Judge's note: Page 4: 'until we either encounter at least c·l points (for c specified later) or use all l indices'. Page 5: P2 is stated in blocks, and the Markov argument bounds the far-only blocks by 4l. With buckets of up to B>1 points, fewer than cl far-only blocks can still hold more than cl far points. A rule that counts points could then stop before reaching the bucket of p*, so the analysis and the stated procedure use different units. Only the authors can say which unit was intended.

Second check: another model agreed

• p. 6 Fact 3 statement and proof

  < 1/(1 + ε) − ln(1 − 1/ln n)

• p. 5 Section 3.2, last paragraph

  we show that ρ ≤ 1/(1+ε) assuming that

Only the authors can say what is right here.

Judge's note: I reworked the proof on page 6. Each step is valid: U/L < 1/(1+ε) − ln(1−r/d′)/(1+ε) < 1/(1+ε) − ln(1−1/ln n), using d′/r > ln n. But −ln(1−1/ln n) > 0, so the bound obtained is strictly weaker than the stated ρ ≤ 1/(1+ε), and only the asymptotic n^ρ = O(n^{1/(1+ε)}) follows. The stated inequality is true by a different argument: f(t)=ln(1−t) is concave with f(0)=0, so f(t)/t is decreasing, which gives ln(1−(1+ε)x)/(1+ε) ≤ ln(1−x), i.e. ρ ≤ 1/(1+ε). The result stands, but the printed proof does not establish the exact statement.

Second check: another model agreed

• p. 8 Section 4.2, Dependence on Data Size

  it requires 3 accesses more for a data set 19 times larger

• p. 9 Figure 5(a), LSH error=.02 curve

  LSH, error=.02

• p. 8 Section 4.2, Dependence on Data Size, right column

  requires 3 accesses more for a data set 19 times larger

• p. 9 Figure 5(a), LSH error=.02 curve

  Approximate 1-NNS

Only the authors can say what is right here.

Judge's note: In Fig. 5(a) on page 9 (crop C014-b) the error=.02 markers sit at about 5, 6, 6, 8 and 9 for n = 0.1, 0.2, 0.5, 1 and 1.9 ×10^4. The last marker is clearly at 9, between the 5 and 10 gridlines and just below 10. Fig. 7(a) at d=64 also shows 9 for error=.02. So the figure shows an increase of 4, not 3. Values were read from the plot, so the authors should confirm.

Second check: another model agreed

• p. 8 Section 4.2, last paragraph

  the miss ratios are quite high (10%) for small n

• p. 9 Figure 6(a), Error=.05 curve

  Error=.05

• p. 8 Section 4.2, last paragraph, right column

  ratios are quite high (10%) for small n, but decrease

• p. 9 Section 4.2 continuation, left column

  to around 1% for n = 19,000

Only the authors can say what is right here.

Judge's note: Crop C015-b and page 9 show the Error=.05 curve in Fig. 6(a) at about 0.165 (n=1000), 0.068 (2000), 0.052 (5000), 0.024 (10000) and 0.018 (19000). No small-n point is near 10%: the smallest n is about 16%. The end value is nearer 2% than 1%. The quoted figures describe the plot only loosely, so the authors should check them.

Second check: another model agreed

• p. 9 Section 4.3

  which resulted in error from 50% to 15%

• p. 11 Figure 9(a), LSH curve

  Performance vs error

• p. 9 Section 4.3, right column

  which resulted in error from 50% to 15% (see Fig-

Only the authors can say what is right here.

Judge's note: Page 11 image, Fig. 9(a): the LSH points sit at about 13.5, 15, 17, 21, 24, 32 and 43% error. The rightmost LSH point is between the 40 and 45 ticks. The 50% end point given in the text (page 9) is not shown in the figure. A point off the plotted range, or loose rounding, could explain it, so only the authors can resolve this.

Second check: another model agreed

• p. 9 Figure 5(b) at n=1.9×10^4

  alpha = 2, 10−NNS

• p. 10 Figure 7(b) at d=64 and Figure 8 at 10 nearest neighbours

  alpha=2, n=19000, d=64

Judge's note: Read from the page 9 and 10 images. Fig. 8 (y-axis 0–15) clearly shows the Error=.1 square at 6 for 10 neighbours, whereas the Fig. 7(b) error=.1 diamond at d=64 sits at 5. The Fig. 5(b) error=.05 star at 1.9 is ≈7, against ≈8 in Figs 7(b) and 8. The paper does not say whether the figures come from separate randomized runs, and readings from low-resolution plots are approximate, so this is recorded as an observation.

Second check: another model agreed

• p. 9 Section 4.2, Dependence on Dimension

  increases the number of indices only by 2

• p. 10 Figure 7(b), LSH error=.05

  (b) Approximate 10-NNS

• p. 10 Figure 8, Error=.1 at 10 neighbours

  Number of nearest neighbors

• p. 10 Figure 7(b), d=64, error=.1

  Approximate 10-NNS

Only the authors can say what is right here.

Judge's note: Page 10 image: in Fig. 7(a) the error=.05 stars sit at 3 (d=8), 3 (d=27) and 5 (d=64). In Fig. 7(b) they sit at ≈3, ≈6 and ≈8. The text on page 9 introduces both the 1-NNS and the 10-NNS comparisons and does not qualify the claim. The reviewer's second note (cross-figure differences) is handled under C018.

Second check: another model agreed

• p. 3 Definition 2

  is the distance of q to the its closest point

• p. 3 Definition 2

  is the distance of q to the its closest point in P

Judge's note: The page 3 image shows 'to the its closest point' in Definition 2. This is a real typo, not an extraction artefact.

Second check: none (judge only)

• p. 5 Proof of Theorem 1

  The probability that g(p′) = g(q) for p ∈ P − B(q,r2)

Judge's note: The page 5 image shows 'g(p′) = g(q) for p ∈ P − B(q,r2)'. The next sentence uses p′ ∉ B(q,r2). The variable name is a notational slip, and the meaning is clear from context.

Second check: none (judge only)

• p. 6 Implementation paragraph, second-level hash function

  a1 · v1 + · · · + ad · vk mod M

• p. 6 Implementation, hash function h

  h(v_1,...,v_k) = a_1 · v_1 + ··· + a_d · v_k mod M

Judge's note: The page 6 image (right column, Implementation) shows 'a_d · v_k'. The next line defines 'a_1,...,a_k', and the stated cost of 2k−1 operations matches k terms. The index is a slip.

Second check: none (judge only)

• p. 6 Section 4, first paragraph

  large large aerial photographs

• p. 6 Section 4, first paragraph

  blocks of large large aerial photographs

• p. 6

  re information of blo c ks of large large aerial photographs

Judge's note: The page 6 image and crop C009-a show 'large large' across a line start in the right column. The same phrase appears once, correctly, on pages 2 and 7.

Second check: code check

• p. 7 Data Sets, texture description

  are used to constructed the feature vec-

• p. 7 Data Sets, texture data set

  are used to constructed the feature vector

Judge's note: Crop C013-a and the page 7 image show 'used to constructed the feature vec-tor'.

Second check: none (judge only)

• p. 10 Section 4.3, end, right column

  this case the LSH algorithm offers considerably out-

Judge's note: Page 10 image, right column, end of Section 4.3: the sentence reads 'the LSH algorithm offers considerably out-performs SR-trees, being up to an order of magnitude faster.' Grammatical error.

Second check: none (judge only)

• p. 11 Reference [5]

  E. Cohen. M. Datar, S. Fujiwara, A. Gionis, P. Indyk, R. Motwani, J. D. Ullman. C. Yang.

Judge's note: Page 11 image, reference [5]: periods after 'Cohen' and 'Ullman', commas elsewhere in the list. Punctuation inconsistency.

Second check: none (judge only)

• p. 12 Reference [30]

  Fonctions aleastoires de second ordere

• p. 12 Reference [30]

  Fonctions aleatoires de second ordere

Judge's note: Page 12 image, reference [30], reads 'M. Loéve. Fonctions aleastoires de second ordere.' 'aleastoires' and 'ordere' are not French words, so they are evident misspellings of 'aléatoires' and 'ordre'. The exact original title wording (de/du) and the accent on Loève rest on outside knowledge and are not judged here.

Second check: none (judge only)

• p. 12 Reference [44]

  G. Wyszecki and W.S. Styles

Only the authors can say what is right here.

Judge's note: Rests on outside knowledge: the co-author of 'Color Science: Concepts and Methods, Quantitative Data and Formulae' is W.S. Stiles. The page 12 image confirms that the paper prints 'W.S. Styles'.

Second check: none (judge only)

• p. 12 Reference [22]

  27 (1933). pp. 417–441.

• p. 12 Reference [25]

  166 – 176

Judge's note: Page 12 image confirms both. The reference list is inconsistent in several places (e.g. [19] '53–94', [41] '13–15' without 'pp.'), so this is a minor style point.

Second check: none (judge only)