20160907-Flann
| layout | title | categories | tags | date | description | ||
|---|---|---|---|---|---|---|---|
|
post
|
近邻查询近似算法库FLANN
|
|
|
2016-09-07 02:25:24 -0700
|
近似近邻查询，作为大数据搜索方面的算法层出不穷，其中有基于树和基于hash的最为多见。
|
引言
近似近邻算法在大型应用中是解决搜索的关键技术。而近似近邻算法的研究中，一部分是基于树结构实现的，一部分是基于hash算法。今FLANN是一个开源库，opencv中已经集成了该module.
红黑树
https://blog.csdn.net/weewqrer/article/details/51866488
用途
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。对于查找、插入、删除、最大、最小等动态操作的时间复杂度为O(lgn).常见的用途有以下几种：
- STL（标准模板库）中在set map是基于红黑树实现的。
- Java中在TreeMap使用的也是红黑树。
- epoll在内核中的实现，用红黑树管理事件块。
- linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块
红黑树 VS AVL树
常见的平衡树有红黑树和AVL平衡树，为什么STL和linux都使用红黑树作为平衡树的实现？大概有以下几个原因：
从实现细节上来讲，如果插入一个结点引起了树的不平衡，AVL树和红黑树都最多需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度
从两种平衡树对平衡的要求来讲，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
总体来说，RB-tree的统计性能是高于AVL的
FLANN概述
首先阐述了近似结果查询的重要性，通过实验结果分析了最有效的近似nn算法中，随机KD森林是最有效的，另外提出了一个新的方法：优先查找k-means树，尤其是针对视觉任务中常用的二进制特征，提出了多层聚类树。为了应用于大数据环境下，还有分布式环境下nn查找框架。
相关名词定义
- KNN(K-nearest neighbor search)：说白了，就是从数据集合了找K个最接近的
- RNN(radius nearest neighbor search)：就是返回一定半径范围内的所有数据。当然这个半径有很多不同的定义。