径向基函数在高超声速热流插值中支撑点选择的判据研究

在使用径向基函数进行高超声速热流插值时,为了避免传统单一绝对误差判据选择得到的支撑点在热流较小处插值不准确的问题,提出一种双重误差判据下的径向基函数插值过程。该过程首先使用绝对误差判据标准选择一定数量的支撑点,再使用相对误差判据标准选择另一部分点。通过数值实验验证同时采用以绝对误差和相对误差为标准选取支撑点的方法,结果表明:采用双重误差判据可以同时保证热流较大与较小处的插值精度,尤其能避免传统单一绝对误差判据导致插值结果中容易出现负热流的问题。

基于切比雪夫距离的支撑点选择算法的并行优化研究

求解切比雪夫距离的支撑点选择算法中,由于计算量较大,如何快速判断支撑点的优劣是一个难以解决的问题,为此,提出一套以切比雪夫距离为目标函数的快速支撑点优选策略。通过并行化分析找出相对独立的计算任务,使用OpenMP对支撑点的选择并行化处理;为降低算法层面的时间复杂度,将切比雪夫距离转化为曼哈顿距离,减少了总体计算量;采用多线程的方法对目标函数值的排序环节进行总体重构,避免了无意义的访存开销。实验结果表明,相比传统方法,支撑点优选算法具有较为明显的加速效果,加速比达到了174.62,并解决了算法的数据依赖问题。

基于近期最远遍历的支撑点选择

度量空间数据管理分析方法把数据抽象成度量空间中的点,具有高度的通用性,是应对大数据多样性挑战的有效手段之一.由于度量空间没有坐标,很多数学工具无法直接使用,一般以数据到参考点(也称作支撑点)的距离作为坐标.支撑点的好坏对于度量空间数据管理分析的性能发挥着关键性的影响.最远优先遍历(Farthest First Traversal,FFT)可以选出数据拐角的点,具有线性的时间复杂度和空间复杂度,是使用最广泛的支撑点选取算法之一.但是,实验表明最好的支撑点往往不是最拐角的点,故FFT很难选出最好的支撑点.提出近期最远遍历(Recent Farthest Traversal,RFT)算法,只以近期的几个支撑点来选择下一个支撑点,能够更快地选出性能更优的支撑点.同时,实验表明FFT还可以在数据内部均匀抽样.提出支撑点集合选择算法(Pivot Set Selection,PSS),可以一次性选出所有支撑点.以RFT选择候选集,以FFT选择评价集,选出支撑点并构建相似性索引,PSS使得索引构建代价大大降低,索引性能得到一定提升.实验表明,RFT选出好的支撑点的速度远快于FFT,准确率高于FFT,而FFT的抽样效果良好.

RPA:一种内存高效的度量空间recall@R近似最近邻搜索索引

现有的度量空间的近似最近邻搜索(approximate nearest neighbor search, ANNS)方法通常依赖于预选择的支撑点构成的序列,序列中的支撑点按照到数据元素的距离升序排列.然而,大多数现有的度量空间ANNS方法由于索引结构复杂、支撑点过多或者未能充分利用距离信息导致搜索时内存开销巨大.为此,提出精简排列阵(reduced permutation array, RPA)的度量空间recall@R近似最近邻搜索方法.对于全体数据元素,RPA预先选择k个支撑点,对每个数据元素仅存储离该数据元素最近的l个(l<<k),并将所有元素的支撑点序列构建为一个数组结构.在搜索过程中,利用一种得分函数,该函数基于查询对象到各个支撑点的距离来近似计算数据元素到查询对象的距离.同时,维护一个有界最小堆,以保存R个候选结果数据元素.RPA具有结构简单、内存效率高和可扩展性强等特点.实验结果表明,在相同召回率的情况下,与排列索引(permutation-based index, P-index)相比,RPA平均具有高达3倍的内存压缩比.研究结果可在内存资源有限的单机环境下提供一种有效的针对海量数据的ANNS方法.