【摘 要】
：
自大数据概念被提出已经过去了将近10年时间,随着时代的发展和社会的进步,计算机应用界所面对的数据量已经逐渐增长到TB、PB甚至EB级。对于如此级别的数据量,线性时间复杂度算法的执行时间也变得不可接受。因此,理论界提出了亚线性算法的概念,从复杂性的角度在根本上解决了大数据计算时间开销过大的问题。本论文挑选了若干比较重要的近邻问题,对其设计了亚线性算法,并以严密的分析证明了这些算法的亚线性时间复杂度。
论文部分内容阅读
自大数据概念被提出已经过去了将近10年时间,随着时代的发展和社会的进步,计算机应用界所面对的数据量已经逐渐增长到TB、PB甚至EB级。对于如此级别的数据量,线性时间复杂度算法的执行时间也变得不可接受。因此,理论界提出了亚线性算法的概念,从复杂性的角度在根本上解决了大数据计算时间开销过大的问题。本论文挑选了若干比较重要的近邻问题,对其设计了亚线性算法,并以严密的分析证明了这些算法的亚线性时间复杂度。本论文所研究的问题有全k-最近邻问题、近似最近邻的图灵归约问题及双近似标准下的近似k-最近邻问题。针对这些问题,本论文的研究成果如下。第一,本文研究了全k-最近邻问题。我们在相关研究领域中发现了一篇高引用的重要文献,基于其中提出的算法,人们一直以为全k-最近邻问题存在O（n logn）时间算法。在经过仔细分析之后,我们发现该文献中的算法实际上无法达到所声明的复杂度。我们证明了该文献中提出的算法实际上具有Ω（n2）时间复杂度下界,并提出了新的算法,修正了该算法中超过O（n2）时间复杂度上界的部分,使得最终的算法真正达到了 O（n log n）时间复杂度。第二,本文研究了近似最近邻的图灵归约问题。在近似最近邻问题的许多算法中,基于图灵归约的算法是最近的也是能够实现亚线性时间复杂度的一类算法。该类算法定义了一个简记为（c,r）-NN的问题,并通过将近似最近邻问题归约到（c,r）-NN问题来解决之。已知（c,r）-NN问题具有伪亚线性算法,如果能够设计出亚线性或伪亚线性时间的图灵归约,则近似最近邻问题也可以在亚线性时间内解决。在现存研究工作中,有三个工作提出了从近似最近邻问题到（c,r）-NN问题的归约算法,它们的复杂度各有不同,但是它们的查询时间复杂度,也即调用（c,r）-NN问题的算法次数,都高于O（log n）。在本论文中,我们提出了新的从近似最近邻问题到（c,r）-NN的归约算法,实现了 O（log n）查询时间复杂度,低于所有现存算法。第三,本文研究了两种特殊情况下近似最近邻图灵归约问题的高效算法,两种特殊情况分别指输入适用于Assouad维度的情况和输入服从泊松点过程的情况。本文中提出的近似最近邻的图灵归约算法的预处理时间复杂度和空间复杂度上都有O（（d2/∈）d）的因子,该因子在维度数d较高时是无法接受的。因此,我们针对两种特殊情况,提出了具有更低时空复杂度的新算法。首先,针对输入适用于Assouad维度的情况提出了新的算法,其预处理时间复杂度和空间复杂度中的因子从O（（d2/∈）d）降低到O（（d/∈）d）。然后针对输入服从泊松点过程的情况,提出了新算法并分析其期望时空复杂度,使得预处理时间复杂度和空间复杂度都降为O（n log n）。第四,本文研究了双近似标准下的近似k-最近邻问题。在近似k-最近邻问题的研究领域中有两种不同的近似标准,分别称为距离标准和召回率标准。通过分析现有的研究工作,我们发现召回率标准只用于衡量实验结果的好坏而没有理论保证,距离标准只有寥寥数个工作有部分的理论保证。在这样的情况下,我们提出了双近似标准下的近似k-最近邻问题,并提出了相应的算法,使得算法输出在任何情况下都至少可以满足距离标准和召回率标准之一,并且有一定概率同时满足两个近似标准。
其他文献
绿道作为融合健康、生态与景观的连续性开敞空间,已成为我国城乡绿色空间生态与景观结合发展重要规划手段,同时也是国土空间规划与全域旅游发展推动的有效载体之一,以休闲游憩空间建设引领区域空间绿色化发展,提供解决快速城镇化发展中的环境问题及社会矛盾途径。但目前城乡绿道建设出现发展不均衡、技术不成熟等问题,特别是环境资源较复杂的市县域地区各类资源协同机制薄弱,对区域绿道空间可持续发展形成限制。论文立足于全域
紫外激光光源在微加工、紫外医疗、光刻等领域具有重要的应用,固体激光器是当前紫外激光光源非常重要的组成部分。而紫外非线性光学晶体材料作为固体激光器的核心器件,受到广泛的关注和研究。磷酸盐因其丰富的晶体结构和优异的光学性能,是探索紫外非线性光学晶体材料的优选体系。然而紫外磷酸盐存在倍频效应和双折射率普遍较小的问题,因此为了增强其倍频效应和双折射率,本文将不同的原子与碱金属磷酸盐复合,合成了多种新型紫外
近年来,随着可穿戴电子产品的智能化、便携化和多功能化发展,对柔性能源存储设备提出了新的要求与挑战。柔性超级电容器因其装配简单,操作安全,环境友好等优点,引起了研究人员的广泛关注。如何通过有效的结构设计制备高界面稳定性和良好兼容性的柔性电极和凝胶电解质来满足柔性器件在不同形变条件下稳定的能量输出是目前亟待解决的问题。相比于其他的柔性电极,织物基电极因其独特的物理化学性质,可以最大程度的释放连续形变过
在我国极端环境工程需求日益增长的情况下,以及“一带一路”等国家战略中许多重要工程将会跨越若干个冬季施工期的背景下,保障混凝土工程在寒冷环境下安全可靠、提高冬期施工的关键技术及理论基础愈加重要。水泥的早期水化硬化是保证冬期施工混凝土性能及质量的关键影响因素,如何在负温下促进水泥快速水化、保证强度持续发展、并避免冻害发生是需要攻克的难点。通常会采取保温蓄热养护方法,然而这类方法不仅会消耗大量的人力物力
由于具有绿色、环保和节省资源等优势,自修复智能材料受到了研究者们的广泛关注。随着研究的深入,人们发现一些因素制约着自修复材料的发展,如较好自修复能力与强机械性能难以同时实现以及自修复材料制备效率低等难题。目前,人工材料的自修复能力还难与自然界生物体相媲美,而复杂的制备过程也进一步阻碍了自修复材料的实际应用。本论文利用模拟人体表皮结构的仿生设计,实现了自修复性能与高模量/高硬度的有效结合,完成了类表
大分子自组装是构筑功能化微纳米材料的重要手段之一,基于大分子自组装制备的材料已经被证实在药物载体、微纳马达、光电材料、微电子器材等方面具有广泛的应用前景。目前大分子自组装的研究对象集中在线性嵌段共聚物和支化嵌段共聚物上。事实上,广泛的氢键作用、分子内易引入功能化单体、结构单元交替链接和超强的结晶性等特征使得聚酰胺有望成为一种非常有潜力的自组装基元。然而迄今为止,关于聚酰胺自组装的研究报道还非常少。
煤热解废水中含有多种有毒难生物降解有机化合物,其中含氮杂环化合物（Nitrogen heterocyclic compounds,NHCs）是煤热解废水中典型的高浓度、高毒性的有机污染物,对污泥微生物的生长代谢具有明显的生物毒性抑制作用,严重影响煤热解废水生化处理单元的处理效果和稳定性。在处理高浓度有毒难降解有机化合物方面,厌氧工艺有着独特的优势。寻求高效可行的强化厌氧技术实现NHCs的有效去除,
随着大数据多媒体时代的到来,互联网、便携设备日益普及,图像作为信息的重要载体,出现在我们身边的每个角落。如何利用计算机充分获取并理解图像信息,一直以来吸引学者们的广泛关注。近年来,在人工智能、深度学习理论蓬勃发展的大背景下,计算机视觉的经典研究问题,例如图像分类、目标检测等,均取得了快速发展和巨大成功;而在自然语言处理方面,机器翻译、人机对话的相关技术也得到了显著提升。受此启发,学者们逐渐将目光转