Hardness Of Approximate Nearest Neighbor Search Under L-infinity | Awesome Similarity Search Papers

Hardness Of Approximate Nearest Neighbor Search Under L-infinity

We show conditional hardness of Approximate Nearest Neighbor Search (ANN) under the (\ell_\infty) norm with two simple reductions. Our first reduction shows that hardness of a special case of the Shortest Vector Problem (SVP), which captures many provably hard instances of SVP, implies a lower bound for ANN with polynomial preprocessing time under the same norm. Combined with a recent quantitative hardness result on SVP under (\ell_\infty) (Bennett et al., FOCS 2017), our reduction implies that finding a ((1+\epsilon))-approximate nearest neighbor under (\ell_\infty) with polynomial preprocessing requires near-linear query time, unless the Strong Exponential Time Hypothesis (SETH) is false. This complements the results of Rubinstein (STOC 2018), who showed hardness of ANN under (\ell_1), (ℓ₂), and edit distance. Further improving the approximation factor for hardness, we show that, assuming SETH, near-linear query time is required for any approximation factor less than (3) under (\ell_\infty). This shows a conditional separation between ANN under the (\ell_1/ ℓ₂) norm and the (\ell_\infty) norm since there are sublinear time algorithms achieving better than (3)-approximation for the (\ell_1) and (ℓ₂) norm. Lastly, we show that the approximation factor of (3) is a barrier for any naive gadget reduction from the Orthogonal Vectors problem.

Explore more on:
ANN Search
Similar Work
Loading…