Rectangle Inequalities for Data structure lower Bounds Yitong Yin Nanjing University Nexus of Information and Computation Theories Fundamental Inequalities and Lower Bounds Theme Institut Henri Poincare
Rectangle Inequalities for Data Structure Lower Bounds Yitong Yin Nanjing University Nexus of Information and Computation Theories Fundamental Inequalities and Lower Bounds Theme @ Institut Henri Poincaré
Online Note "Yitong Yin:Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities." http://arxiv.org/abs/1602.05391
Online Note http://arxiv.org/abs/1602.05391 “Yitong Yin: Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities
Nearest Neighbor Search (NNS) metric space (,dist)
Nearest Neighbor Search metric space (X,dist) (NNS)
Nearest Neighbor Search (NNS) metric space (X,dist) database y=(y1,y2,.,yn)∈Xn
Nearest Neighbor Search metric space (X,dist) database y = (y1, y2,...,yn) 2 Xn (NNS)
Nearest Neighbor Search (NNS) metric space (X,dist) database y=(y1,y2,·,yn)∈Xn data structure 3 7 preprocessing 122
Nearest Neighbor Search metric space (X,dist) database y = (y1, y2,...,yn) 2 Xn preprocessing data structure (NNS)
Nearest Neighbor Search (NNS) metric space (X,dist) query x∈X database y=(y1,y2,·,yn)∈Xn data structure 3 7 preprocessing 22
Nearest Neighbor Search metric space (X,dist) database y = (y1, y2,...,yn) 2 Xn preprocessing data structure query x 2 X (NNS) x
Nearest Neighbor Search (NNS) metric space (X,dist) query x∈X database access y=(y1,y2,.,yn)∈Xn data structure preprocessing output:database point yi closest to the query point x
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 x
Nearest Neighbor Search (NNS) metric space (X,dist) query x∈X database access y=(y1,y2,…,yn)∈Xn data structure preprocessing 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 (2-NN) metric space (X,dist) query x∈X database access y=(y1,y2,·,yn)∈Xn data structure 3 7 preprocessing NIE 122
Near Neighbor Problem database y = (y1, y2,...,yn) 2 Xn data structure query x 2 X (λ-NN) access x metric space (X,dist) preprocessing
Near Neighbor Problem (2-NN) metric space (X,dist) query x∈X database access y=(y1,y2,,yn)∈Xn data structure radius入 3 7 preprocessing 122 27
Near Neighbor Problem database y = (y1, y2,...,yn) 2 Xn data structure query x 2 X (λ-NN) access x radius λ metric space (X,dist) preprocessing
