高维检索树

K-dimentional Tree

Kd树：循环遍历各维度，按该维度取值二分数据

• 对高维数据进行快速搜索二叉树

  • 超平面都垂直于轴的BSPTree

• Kd树对样本点的组织表示对k维空间的划分

  • 每个节点对应k维空间中超矩形区域
  • 构造kd树相当于用垂直于坐标轴超平面不断划分k维空间， 得到一系列超矩形区域

• Kd树构建目标

  • 树应该尽量平衡，即分割应尽量均匀
  • 最大化邻域搜索的剪枝

建树

• 输入：数据点$X_i, i=1,2,\cdots,N$

• 确定划分维度（轴）
  • 选择方差最大的轴，使得数据尽量分散
  • 按次序循环遍历所有轴：方便查找时定位轴
• 选择该维度上数值中位数作为划分点
  • 中位数查找方法
    • 各维度统一全体排序、记录
    • 抽样，使用样本中位数
  • 小于中位数的数据点划分至左子树，否则划分至右子树
• 递归建立左、右子树直至无法继续划分
  • 节点中包含数据项数量小于阈值

查找K近邻

• 输入：Kd树、目标点x

• 在Kd树中找出包含目标点x的叶节点，以之为近邻点

  • 从根节点出发，与节点比较对应坐标值，递归访问至叶节点 为止
  • 目标点在训练样本中不存在，必然能够访问到叶节点

• 沿树回溯，检查节点是否距离目标点更近，尝试更新

• 检查该节点另一子区域是否可能具有更近距离的点

  • 即考察以目标点为圆心、当前近邻距离为半径圆，同划分轴 是否相交
  • 则只需比较目标点同相应切分平面距离、近邻距离

• 若目标点同该对应切分平面距离小于近邻距离

  • 则将目标节点视为属于该子区域中的点
  • 从节点未访问子树开始重复以上步骤，进行近邻搜索

• 否则继续回退

• 退回到根节点时，搜索结束，近邻点

• 回溯过程中需要盘对子域是否访问过，可以通过标记、比较相应 轴坐标等方式判断
• k>1的情况类似，不过检测时使用最远近邻，新近邻需要和所有 原近邻依次比较

其他操作

插入新节点

• 从根节点出发，根据待插入节点、当前节点在对应维度取值确定 插入左、右子树
• 遍历直至叶子节点，插入

删除节点

• 简单方法：将待删除节点子节点组成新集合，对其重新构建， 将新子树挂载在原被删节点位置

• 分类讨论：设删除节点T对应划分维度为D

  • 节点无子树：直接删除
  • 节点有右子树
    • 在右子树寻找维度D取值最小节点P，替换被删除节点T
    • 在右子树递归处理删除节点P
  • 节点无右子树有左子树
    • 在左子树寻找维度D取值最小节点P，替换被删除节点T
    • 将T的左子树作为P的右子树
    • 在右子树递归处理删除节点P

查找维度D最小点

• 若当前结点切分维度为D：只需查找左子树
• 否则需要对左、右子树分别递归搜索

Vantage Point Tree

VP树：任选样本点，按照数据点与该点距离二分数据

• 对高维数据进行快速搜索二叉树

• VP树对样本点的组织表示对k维空间的划分

  • 每个节点对应k维空间中一个球形划分
  • 构造kd树相当于用以给定样本点为球心不断划分k维空间， 得到一系列球内、球外区域

建树

• 输入：数据$X_i, i=1,2,\cdots,n$

• 选择某数据点$X_v$作为划分球心
• 计算其他数据点距离$D_i = d(X_i, X_v)$
• 求出$D_i$中位数$M$
  • 与$X_v$距离$D_i \leq M$的数据点$D_i$划分至左子树
  • 与$X_v$距离$D_i \gt M$的数据点$D_i$划分至右子树

Rectangle Tree

R树：将空间划分为有重叠的

• B树高维推广
  • 类似B树将一维区间划分为多个不重叠的子区间
  • 同样是平衡树，所有叶子位于同一层上

• R树退化至1维有分割区间重叠问题，效果不如B树

性质

• $M$：节点中最大键数量
• $m \leq \frac M 2$：节点中条目最小数量

• 非根叶节点包含$m-M$索引记录：$I$表示可在空间中完全覆盖 节点中条目点的MBR

• 非根、非叶节点包含$m-m$个子节点：$I$表示可在空间中完全 覆盖节点中条目矩形的MBR

• 根节点条目数$[2, m]$，除非为叶子节点

• minimal bounding rectangle：MBR，最小边界矩形

节点结构

• 叶子节点结构：$(I, tuple-ids)$

  

  • $I((s_1, e_1), (s_2, e_2), \cdots, (s_n, e_n))$： n维空间中矩形
  • $tuple-ids$：节点包含的记录

• 非叶节点：$(I, child-pointer)$

操作

建树

矩形搜索

SearchRect(T, S, ret):
	// 利用R树搜索矩形范围中包含的记录点
	// 输入：R树根节点T、待搜索矩形S
	// 输出：矩形S覆盖的条目

	if T.I join S == NULL:
		return

	// 若T不是叶子节点，检查其每个条目E
	if not T.is_leaf():
		for E in T.entries:
			// 对与S相交E.I对应条目E，递归调用搜索
			if T.I join S != NULL:
				SearchRect(E, S, ret)

	// 若T是叶子节点且T.I与S相交，检查其每个记录点
	elif T.I join S != NULL:
		for E in T.entries:
			if E in S:
				ret.add(E)

选择所属叶子

ChooseLeaf(T, E):
	// 在R树中寻找新索引条目所属叶子节点
	// 输入：R树根节点T、索引条目E
	// 输出：E所属R树中叶子节点

	if T.is_leaf():
		Assert(E.is_subset(T))
		return T

	else:
		for T_E in T.entries:
			if E.is_subset(T_E)
				return ChooseLeaf(T_E, E) or T_E

插入新条目

Insert(T, E):
	// 向R树中插入新条目
	// 输出：R树根T、新条目E

	L = ChooseLeaf(T, E)
	if L.has_slot():
		L.add(E)
	else:
		LL = L.split()
		L.add(E)
		P = L.get_parent()
		

调整树

AdjustTree(T, L):
	// 从不满足节点开始调整R树至满足要求
	// 输入：R树根T、不满足要求节点L
	// 输出：

	if L.is_root():
		return

	P = L.get_parent_node()
	if L.splitted():
		NN = L.get_split_node()
		if P.
	// 调整节点L在父节点中矩形框I大小
	addjust_I(P.L.I)

R*-tree

X-tree

SS-tree

SR-Tree

Metric-tree