覆盖树

作者 zhan-bin 日期 2018-12-07
覆盖树

一种用于最近邻搜索的数据结构-覆盖树

覆盖树是计算机里的一种数据结构,Beygelzimer A , Kakade S , Langford J在 [1] 提出。是专门用于最近邻搜索的一种数据结构,可以提高最近邻搜索的效率、减少计算量。
覆盖树具有显式的和隐式两种表示方式,隐式表示的覆盖树一个节点可能在树中出现多次,但它在一层中至多出现一次。显式表示的覆盖树则是将隐式表示的覆盖树的孩子节点只有自己的节点合并,每一个显式表示的覆盖树都有一个非己的父节点。相对来说显式表示的覆盖树节省了存储空间。
覆盖树中每一层Ci都遵循如下三个重要的特性:

  • 嵌套(Nesting): Ci⊆Ci+1
  • 覆盖(Covering):对于∀p∈Ci-1 , ∃q∈Ci,使得d(p,q)≦2i,且q是p的父节点。
  • 分隔(Separation):∀p、q∈Ci ,有d(p,q)≧2i

覆盖树除叶子节点的所有节点包含自己,中间某一层没有在范围2i到2i+1的距离的点的时候,我们只保留和上一层一样的节点在这一层,继续往下搜索。

引用:[1] Beygelzimer A , Kakade S , Langford J . Cover trees for nearest neighbor[J]. 2006.

最近邻搜索

覆盖树最近邻搜索算法如下所示

算法 1:

覆盖树的插入(Insert)

覆盖树的插入算法如下所示

算法 2:

覆盖树的构建

覆盖树构建过程:

  • 1、计算所有点的距离
  • 2、将所有计算出来的距离按照从大到小排序。
  • 3、按照距离从大到小将点插入到覆盖树中,相距最远的两个点选其中一个先开始插入覆盖树作为根结点,随后依次按顺序将所有点插入树中(插入过程即上述的“算法2”,这里不再阐述)。

节点删除

覆盖树的节点删除算法如下所示

算法 3: