机遇 research之路其修远兮,我将上下而求索

近邻查询近似算法库FLANN

2016-09-07
cwlseu

引言

近似近邻算法在大型应用中是解决搜索的关键技术。而近似近邻算法的研究中,一部分是基于树结构实现的,一部分是基于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查找框架。

相关名词定义

  1. KNN(K-nearest neighbor search):说白了,就是从数据集合了找K个最接近的
  2. RNN(radius nearest neighbor search):就是返回一定半径范围内的所有数据。当然这个半径有很多不同的定义。

参考文献

  1. K-D Tree
  2. R 树简介
  3. 从B树、B+树、B*树谈到R 树
  4. 线段树
  5. 红黑树

|版权声明:本文为博主原创文章,未经博主允许不得转载。


下一篇 开发:GDB debug

欢迎评论

Content