第六章 基础知识 (Preliminaries)
基础知识章节是一个可选的章节。根据需要,本章节主要用来介绍一些基础知识,以便于读者能够更好的理解设计与实现章节的内容。
有些情况下,论文研究的问题比较复杂,需要较大篇幅的文字,甚至是需要使用数学工具来解释。这时可以将问题定义独立设置为一个章节,
命名为问题定义(Problem Definition),或者也可以考虑将其设置为基础知识章节中的一个子章节。这样做可以简化设计章节的结构和逻辑。
在论文写作时,一般会假设读者具备了一定的计算机基础知识。但是不应假设读者是某领域的专家。但凡涉及到某领域的特定知识时,
这些知识内容是需要详细介绍的。例如,在并行计算领域,以下两个知识点常被设置为独立章节解释其工作原理。(1)MapReduce框架:
介绍MapReduce框架的主要目的是为了突出与其他并行计算框架的不同之处。因为shuffling是MapReduce框架特有的一个处理过程,
有些论文会着重讲解shuffling的工作原理。(2)GPU结构。利用GPU的计算能力来增强程序处理性能也是一个并行计算的发展方向。
因为GPU工作原理与CPU不同,而且GPU与CPU之间的数据传输有可能成为新算法的性能瓶颈,所以,与GPU相关的论文一般都会详细的介绍GPU的工作原理,
以及强调新算法使用了哪些 GPU 的特性,以增强算法性能。以下是一篇有着MapReduce 和GPU介绍的论文例子,以供参考。
本例引用自 Wenlu Wang, Ji Zhang, Min-Te Sun, and Wei-Shinn Ku. A Scalable Spatial Skyline Evaluation System
Utilizing Parallel Independent Region Groups. The VLDB Journal, 2018.
为了更好的阐述本章节的作用,下面的例子不仅在基础知识章节定义了所研究的问题,还详细介绍了当前对于费马韦伯(Fermat-Weber)问题研究的现状。
费马韦伯问题是一个世界著名的难题。在数学界,研究人员提出并证实了很多成果。有些成果已经应用于人们的生活中。在本例中,
该论文所提出的新方法需要用到费马韦伯问题的解法来寻找在多维空间中的一个最优位置。因为计算机领域的研究人员并不熟悉费马韦伯方法的内部细节,所以,
该论文使用了一个子章节介绍这个问题的研究现状和目前的研究结论。
被人们熟知的费马问题是,在空间中任意给定三点,并在空间中寻找一个最优点,使得从这个最优点到给定的三个点的距离和最小。
费马韦伯进一步扩展了这个问题。它将给定的点数扩展为n个,并且为每个给定的点设置了一个权值,按照加权的距离和最小来寻找最优点。根据目前的研究现状可知,
当给定点共线时,最优点的位置可在线性的时间内找到,找到的点是精确的最优点。但是在三个以上给定点且不共线的情况下,以目前的研究水平还无法找到精确的最优点。
但是,可以以一种迭代的方式无限逼近这个最优点。这个迭代的方法从任意一个(不与给定点重叠的)点 q0 开始,
不断的调用迭代函数 qi+1 = f(qi)。
由该迭代函数单调收敛(Monotonic Convergence)的特性可知,qi+1比 qi 更接近于这个最优点。
理论上讲,这个最优点应该无限接近于limi→∞ qi = fi(q0)。
若对本例的内容感兴趣,可参考该论文章节 2.3。
本例引用自 Ji Zhang, Wei-Shinn Ku, Min-Te Sun, Xiao Qin, and Hua Lu. Multi-Criteria Optimal Location
Query with Overlapping Voronoi Diagrams. In Proceedings of the 17th International Conference
on Extending Database Technology (EDBT), Athens, Greece, 2014.
本例的全文可在官方网址处免费获取。