高级数据库大作业

深圳大学考试答题纸。

以**、报告等形式考核专用)

二○ 一五～二○ 一六学年度第一学期。

摘要：本文介绍一种用于高维空间中的快速最近邻和近似最近邻查找技术——kd-tree（kd树）。kd-tree，即k-dimensional tree，是一种高维索引树形数据结构，常用于在大规模的高维数据空间进行最近邻查找(nearest neighbor)和近似最近邻查找(approximate nearest neighbor)，例如图像检索和识别中的高维图像特征向量的k近邻查找与匹配。

本文首先介绍kd-tree的基本算法原理，包括基本的建树、查找和更新等操作；设计和实现了一颗支持多维数据的范围和最近邻查询的kd树；并将kd树的算法与普通的线性搜索整个数据集的算法进行比较分析，附有详细的对比试验和测试结果。

关键字：kd树；最近邻；算法。

1 kd树的基本算法原理。

kd树的基本算法原理主要分为树的构建和基于kd树进行最近邻的查询2个过程。

1.1 kd树的定义。

kd-树是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，y，z..)中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。

本质上说，kd树就是一种平衡二叉树。

kd树又称为空间划分树，就是把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索操作。想像一个三维空间，kd树按照一定的划分规则把这个三维空间划分了多个空间。

**引自课程ppt）

1.2 kd树的构建。

将一个k维数据与kd-tree的根结点和中间结点进行比较，只不过不是对k维数据进行整体的比较，而是选择某一个维度di，然后比较两个k维数在该维度di上的大小关系，即每次选择一个维度di来对k维数据进行划分，相当于用一个垂直于该维度di的超平面将k维数据空间一分为二，平面一边的所有k维数据在di维度上的值小于平面另一边的所有k维数据对应维度上的值。也就是说，我们每选择一个维度进行如上的划分，就会将k维数据空间划分为两个部分，如果我们继续分别对这两个子k维空间进行如上的划分，又会得到新的子空间，对新的子空间又继续划分，重复以上过程直到每个子空间都不能再划分为止。

1）在k维数据集合中选择具有最大方差的维度k，然后在该维度上选择中值m为pivot对该数据集合进行划分，得到两个子集合；同时创建一个树结点node，用于存储；

2）对两个子集合重复（1）步骤的过程，直至所有子集合都不能再划分为止；如果某个子集合不能再划分时，则将该子集合中的数据保存到叶子结点（leaf node）。

举例：给定二维数据集合：(2,3), 5,4), 9,6), 4,7), 8,1), 7,2)，利用上述算法构建一棵kd-tree。

左图是kd-tree对应二维数据集合的一个空间划分，右图是构建的一棵kd-tree。

**引自。其中圆圈代表了中间结点(k, m)，而红色矩形代表了叶子结点。

1.3 kd树的最近邻查找。

算法原理是选出与给定数据最近的k个数据，然后根据k个数据中占比最多的分类作为测试数据的最终分类。

1）将查询数据q从根结点开始，按照q与各个结点的比较结果向下访问kd-tree，直至达到叶子结点。

其中q与结点的比较指的是将q对应于结点中的k维度上的值与m进行比较，若q(k)

2）进行回溯（backtracking）操作，该操作是为了找到离q更近的“最近邻点”。即判断未被访问过的分支里是否还有离q更近的点，它们之间的距离小于dcur。

如果q与其父结点下的未被访问过的分支之间的距离小于dcur，则认为该分支中存在离p更近的数据，进入该结点，进行（1）步骤一样的查找过程，如果找到更近的数据点，则更新为当前的“最近邻点”pcur，并更新dcur。

如果q与其父结点下的未被访问过的分支之间的距离大于dcur，则说明该分支内不存在与q更近的点。

回溯的判断过程是从下往上进行的，直到回溯到根结点时已经不存在与p更近的分支为止。

1.4 kd树的更新。

1.4.1 kd树的插入。

元素插入到一个kd树的方法和二叉检索树类似。本质上，在偶数层比较x坐标值，而在奇数层比较y坐标值。当我们到达了树的底部，（也就是当一个空指针出现），我们也就找到了结点将要插入的位置。

生成的k-d树的形状依赖于结点插入时的顺序。给定n个点，其中一个结点插入和检索的平均代价是o(log2n)。

1.4.2 kd树的删除。

kd树的删除可以用递归程序来实现。我们假设希望从k-d树中删除结点（a,b）。如果（a,b）的两个子树都为空，则用空树来代替（a,b）。

否则，在（a,b）的子树中寻找一个合适的结点来代替它，譬如(c,d)，则递归地从k-d树中删除（c,d）。一旦(c,d)已经被删除，则用（c,d）代替（a,b）。假设(a,b)是一个x识别器，那么，它得替代节点要么是（a,b）左子树中的x坐标最大值的结点，要么是（a,b）右子树中x坐标最小值的结点。

1.5 kd树的范围查找。

使用k-d树可以进行范围查找，利用欧氏距离。

例如，在二维的情况下，可以查找x在一定范围的结点如果到达某个结点发现识别器的关键码大于这个范围了，那么该结点的右子树就不用搜索了，因为它们必然都大于这个范围。同理，如果识别器的关键码小于这个范围了，该结点的左子树都不用搜索了。

2 kd树算法的**实现。

本作业报告设计和实现的是三维kd树，文档中提供了大部分的类定义以及重要算法的实现。

2.1 三维坐标点结构体。

struct spoint3d

float x;

float y;

float z;

spoint3d()

2.2 计算时间的结构体（算法效率用所用时间体现）。

struct stime

large_integer begaintime1 ;

large_integer endtime1 ;

large_integer frequency1 ;

void starttime()

double endtime()

2.3 坐标点类以及重要成员函数的实现 (用于从文件中读取坐标点和保存坐标点到文件中)。

class cpoint3d

private:

svecpoint3d m_point;

float m_minx;

float m_maxx;

float m_miny;

float m_maxy;

float m_minz;

float m_maxz;

public:

cpoint3d();

~cpoint3d();

void readpointfromfile(const char *v_pfilename);

void s**epointtofile(const char *v_pfilename, svecpoint3d &vvecpoint3d);

void getpoint(svecpoint3d &vvecpoint3d); 获取坐标点。

float getminx();

float getmaxx();

float getminy();

float getmaxy();

float getminz();

float getmaxz();

/从文件中读取坐标点集。

void cpoint3d::readpointfromfile(const char *v_pfilename)

ifstream input;

if (spoint3d point;

char temp;

m_input >>temp >>temp >>

while (!

nth_element(&m_ &m_ &m_ lessthanx);

m_minx = m_

nth_element(&m_ &m_ &m_ lessthanx);

m_maxx = m_

nth_element(&m_ &m_ &m_ lessthany);

m_miny = m_

nth_element(&m_ &m_ &m_ lessthany);

m_maxy = m_

高级数据库大作业

数据库大作业样本

高级数据库技术

高级数据库题目

其他用户还读了