Near Neighbor Problem (a-NN) metric space (X,dist) query x∈X database access y=(y1,y2,,yn)∈Xm data structure radiusλ preprocessing NIL -NN:answer“yes'if 3yithat is人-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入 7 preprocessing NIL 22 27
Approximate Near Neighbor database y = (y1, y2,...,yn) 2 Xn data structure query x 2 X (ANN) access x radius λ metric space (X,dist) preprocessing
Approximate Near Neighbor (ANN) metric space (X,dist) query x∈X database access y=(y1,2,.·,yn)∈Xn data structure radius入 preprocessing approx ratio y≥l (y,A)-ANN:answer "yes"if 3yi that is A-close tox “no”if all yiare y-faraway from x 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 approx 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,2,·,yn)∈Xn data structure radius入 preprocessing 7 NIL approx ratio y≥l Hamming space={0,1) dist(x,z)=llx-zl1 Hamming distance
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 preprocessing radius λ approx ratio γ≥1
Approximate Near Neighbor (ANN) metric space (X,dist) query x∈X database access y=(y1,2,,yn)∈Xn data structure radius入 preprocessing 7 approx ratio y≥l Hamming spaceX ={0,1)d dist(x,2)=-z1 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 λ approx ratio γ≥1