随着计算机的逐渐普及和互联网技术的日益成熟,各个行业每天都会产生海量的数据,而这些数据往往具有规模大、维度高的特性,所以如何从中快速有效的提取有价值的信息给科学界带来了新的研究课题。在处理这些数据过程中一个重要的技术便是信息检索,而从数据库中查询相关信息最根本就是近邻搜索问题。最近邻查询是指在给定集合内寻找与查询点相距最近的点,它是当代信息检索的一种重要手段。基于k-d树的近邻搜索算法是近邻搜索算法中较为经典算法之一,自从1975年提出k-d树结构用于近邻搜索起,国内外很多学者已经对其进行改进也产生了很多成果,但该算法运行速度较慢主要原因是在k-d树中分割超平面都是轴平行导致每个结点的单元格通常都要远大于结点所表示的凸包从而导致计算得到的近似距离远大于实际查询点到结点内最近邻点的距离。针对上述缺陷和分析的原因,本文提出了一种新型数据结构--半凸包树（Semi-convex Hull Tree）,并在半凸包树的基础上提出了一个快速近邻搜索算法和其改进版本的近邻搜索算法,对近邻搜索实现了加速,可对大规模数据进行有效处理。本文的内容主要包括以下三点:（1）针对k-d树进行了深入的研究和分析,对k-d树的相关概念、定义进行描述,并详细介绍如何构建k-d树以及如何利用k-d树来完成最近邻搜索。分析它的缺陷以及主要原因,一是目前的分割超平面不是最好的分割轴来计算近似距离,二是由于每个分割超平面都是轴平行的,因此每个结点的单元格通常都要远大于结点所表示的凸包。针对k-d树缺陷和其原因提出新的思路。（2）提出一种新的数据结构--半凸包树,并给出其相关定义和性质。详细介绍半凸包树的数据结构。此外还提出构建半凸包树的算法,其思想是使用非轴平行超平面分割数据空间,将数据空间分割成若干个区域。整个算法的过程主要包括分割超平面的确定以及超平面的继承与改进。每次分割都会得到一些新的结点,它们都代表一个半凸包。每个结点中都是由若干个不同的线性约束和数据点构成。此外本文还对构建半凸包树的算法进行理论分析,其时间复杂度为（7）（7）（8）（8）O n Wlog W,其中n表示数据集总数,W是半凸包树中叶子结点的个数。（3）提出基于半凸包树的并行批处理快速近邻搜索算法,该算法主要思想是利用简化的二次规划计算点到结点之间的距离,并对叶子结点中数据点的重新排序使得算法在GPU上应用时减少指针跳转从而充分利用GPU的并行能力,来完成近邻查询。此外还发现使用半凸包树进行近邻的查询时,在大规模数据集上进行近邻查询其结果与在数据集的一个小样本上进行查询的结果很相似,因而提出一个新的改进近邻搜索算法,即基于样本的半凸包树并行批处理快速近邻搜索算法。通过在各种不同维度的真实数据上验证,实验表明本文提出的近邻搜索算法效率相对于其他算法有较大的提升,尤其是在中低维数据上,随着数据规模的扩大,运行时间依然趋近于次线性。但是在高维数据上仍需要进一步改进。