Simple Average-case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities Yitong Yin Nanjing University
Simple Average-case Lower Bounds for Approximate Near-Neighbor fom Isoperimetric Inequalities Yitong Yin Nanjing University
Nearest Neighbor Search (NNS) metric space (X,dist) query x∈X database access y=(y1,y2,,yn)∈Xn data structure preprocessing NIL NIL NIL NIL output:database point yi closest to the query point x applications:database,pattern matching,machine learning
Nearest Neighbor Search metric space (X,dist) database y = (y1, y2,...,yn) 2 Xn preprocessing data structure query x 2 X output: database point yi closest to the query point x (NNS) access applications: database, pattern matching, machine learning, ... x
Near Neighbor Problem (a-NN) metric space (X,dist) query x∈X database access y=(y1,y2,,yn)∈Xn data structure radiusλ preprocessing 2 NIL NIL NIL 27 NIL NIL NIL -NN:answer“yes”if 3yi that is≤l-close tox “no”if all yiare>人-faraway fromx
Near Neighbor Problem database y = (y1, y2,...,yn) 2 Xn data structure query x 2 X (λ-NN) access x radius λ “no” if all yi are >λ-faraway from x λ-NN: answer “yes” if ∃yi that is ≤λ-close to x metric space (X,dist) preprocessing
Approximate Near Neighbor (ANN) metric space (X,dist) query x∈X database access y=(y1,y2,,yn)∈Xm data structure radiusλ preprocessing NIL NIL NIL approximation ratio NIL NIL NIL (y,)-ANN:answer“yes”if yithat is≤λ-close tox "no"if all yiare >y-faraway fromx arbitrary if otherwise
Approximate Near Neighbor database y = (y1, y2,...,yn) 2 Xn data structure query x 2 X (ANN) access x radius λ “no” if all yi are >γλ-faraway from x approximation ratio γ≥1 arbitrary if otherwise (γ, λ)-ANN: answer “yes” if ∃yi that is ≤λ-close to x metric space (X,dist) preprocessing
Approximate Near Neighbor (ANN) metric space (X,dist) query x∈X database access y=(y1,y2,,yn)∈Xn data structure radius入 preprocessing NIL NIL approximation ratio l NIL NIL NIL NIL NIL Hamming space={0,1}d dist(x,z）=x-z1 100logn<d≤no(1) Hamming distance Curse of dimensionality!
Approximate Near Neighbor database y = (y1, y2,...,yn) 2 Xn data structure query x 2 X (ANN) access x Hamming space X = {0, 1}d metric space (X,dist) dist(x, z) = kx zk1 Hamming distance Curse of dimensionality! preprocessing radius λ approximation ratio γ≥1 100 log n<d<no(1)