异常检测是指发现系统或用户偏离常规的行为,在信用卡欺诈、网络入侵、系统故障检测等方面有着广泛的应用。异常检测通常将正常的行为特征存储在数据库中,然后将当前行为特征与数据库中的行为特征进行比较,当两者偏差足够大时判断发生了异常。用于异常检测的方法很多,LOF (Local Outlier Factor)算法通过计算测试实例的LOF值来判断其是否异常,由于检测率高而得到广泛的应用。然而,LOF算法的计算复杂度很高,其中时间开销最大的操作是kNN计算。在数据规模很大时,LOF算法的时间开销限制了它在低延迟应用中的使用。虽然有很多工作对LOF算法以及kNN算法进行了多种方式的优化,但这些优化方法在数据规模很大或数据维度很高时都存在复杂度太高的问题。近年来,GPU已经发展为包含成百上千个计算单元、具有强大计算能力的众核处理器。GPU统一架构及CUDA (Compute Unified Device Architecture)的出现极大地方便了GPU的编程工作,使得GPU的应用领域从最初的图形图像渲染很快扩展到通用计算领域。目前已有一些工作使用GPU来加速异常检测领域的算法,其中就有针对LOF算法以及kNN算法的并行化工作。但这些工作都没有充分利用GPU的体系结构特点,LOF算法和kNN算法在GPU上还有很大的优化空间。本文研究基于GPU的LOF算法高效实现,重点研究时间开销最大的kNN算法的高效实现。本文将kNN计算分为距离计算和k-近邻查找两个步骤,分别进行优化。对于距离计算,本文重新定义了数据实例的数据结构以及存储方式,并充分利用全局存储器的合并访问特性来提高访存效率。对于k-近邻查找,本文通过距离过滤减少需要参与排序的距离值,减少了线程串行化排序的执行时间。基于高效的kNN实现,本文在CPU-GPU平台上实现了LOF算法的并行加速。本文在真实的数据集上对基于GPU的kNN算法实现及LOF算法实现进行了实验评估,并与其它同类实现进行了比较。实验表明本文实现比已有同类实现有显著的性能提升。