ML NNS

[junxnone]

Nearest Neighbor Search 最近邻搜索

Reference

• NNS - Wikipedia
• A Survey on Nearest Neighbor Search Methods
• Survey of Nearest Neighbor Techniques
• NNS Benchmark
• 最近邻搜索 (Nearest Neighbor Search)
• 最近邻检索（Nearest Neighbor Search）的简单综述

Brief

• NNS - Nearest Neighbor Search
• 问题 : M 空间内的点集 S 和点 q，查找 S 中离 q 最近的点
  • 1973 post-office problem 分配一个地址到最近的邮局
• 精确搜索
  • 线性搜索 - 遍历数据集
  • 空间分割 - KDTree
• 近似搜索 - ANN

精确搜索 vs 近似搜索

Method	Description	Algos	应用
精确搜索	- 低维度数据 d < 20 - 穷举搜索数据距离，列出最小距离数据 - 数据量大时，搜索效率低	KD-Tree/R-Tree/M-Tree	3D点云配准
近似搜索 ANN	- 高维度	聚类/LSH/PQ	CBIR/翻译

应用

• KNN - 预测数据分类
• 文档/网页 检索
• 位置检索
• CBIR

Trend

History