基于粒子索引排序算法的kd-tree缓存优化问题研究
作者机构:福州大学土木工程学院
出 版 物:《工程科学与技术》 (Advanced Engineering Sciences)
年 卷 期:2024年
核心收录:
学科分类:08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:国家自然科学基金项目(52079032) 福建省水利科技项目(MSK202215,MSK202333)
主 题:kd-tree 粒子近邻搜索 缓存优化 粒子索引值排序
摘 要:在使用kd-tree进行大规模随机粒子近邻搜索时,可能出现计算域内索引值相近的粒子在空间上距离较远而导致kd-tree的搜索路径在短时间内产生较大差异,使得节点数据的访问效率降低,最终影响kd-tree近邻搜索的效率。为解决该问题,本文引入了主成分分析中最大离散度降维的思想,采用平均绝对差作为离散度衡量指标,提出了基于平均绝对差粒子索引值排序的缓存优化策略,即MAD-index-sort,通过计算粒子集群平均绝对差最大的维度来实现数据降维,进而完成粒子的索引值重排序,并应用具有自动终止准则的ATC-kd-tree进行近邻搜索。为验证MAD-index-sort缓存优化策略的可行性,本文设计了不同维度和离散度对照组进行近邻搜索效率对比实验。结果表明,MAD-index-sort能根据粒子集群的离散度自动改变排序方向,具有更强的适应性,相较于未排序的情况性能最高可提升30.3%。