基于粒子索引排序算法的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%。