最近邻搜索是一种用来识别相似数据的经典方法,广泛应用于数据库、人工智能、软件工程等各个领域。随着机器学习、数据挖掘等技术的迅速发展,数据已经成为了一种宝贵的财富,为了降低本地的存储成本和计算开销并且保护数据的安全,所有者通常将数据加密后外包到云服务器。但是传统的加密算法(如AES、RC4等)在提高安全性的同时大大降低了数据可用性,没有明文访问权限的用户及云服务器无法直接在密文序列上进行最近邻检索。为此提出了安全最近邻检索算法,此类算法可使云服务器直接对密文进行最近邻检索,大大提高了数据的可用性。虽然目前有多种方案支持加密数据的最近邻查询,但是现有的解决方案仍然不能在效率和隐私之间达到很好的平衡。依赖于非轻量级加密算法(如同态加密)的最近邻检索方案具有更强的安全性,但是加密算法的复杂性使得数据预处理开销过大,检索时间过长;利用轻量级的保序加密算法可以提高检索效率,但是会遭遇推理攻击从而威胁数据安全。针对目前方案中存在的局限性,本文利用空间填充曲线、噪声扰动和保序加密设计了两种可以应用于不同场景中的安全近似最近邻检索方案,主要研究内容和成果总结如下:第一种方案通过单一的空间填充曲线映射和噪声扰动对明文数据进行预处理,使扰动后的数据更加稀疏,从而抵御推理攻击,增强对数据的隐私保护,实现了高级别的安全定义(IND-OCPA)。除此之外,方案在数据预处理及查询阶段都保持了较低的计算开销,并且达到了对数时间的查询效率,适用于对查询时效性要求高的场景。大量的实验结果表明,该方案在有效保护数据隐私的同时实现了高效的最近邻查询,有效解决了目前方案中存在的安全性和查询效率之间的平衡问题。第二种方案通过多条平移的空间填充曲线对数据进行预处理,在和方案一保持相同级别安全性的同时,大大提高了查询结果的准确性。虽然方案二的数据预处理算法较方案一稍显复杂,但相比其它基于非轻量级加密算法的安全最近邻检索方案,该方案在计算开销方面仍然具有很大的优势。本文通过大量实验对方案二的查询准确性和查询效率进行了测试,实验结果表明,该方案在构造数据集和真实数据集上的查询准确性均优于方案一,并且保持了对数时间的查询效率,适用于同时要求查询效率和查询准确性的场景。