基于自动终止准则改进的kd-tree粒子近邻搜索研究  

Improved Kd-tree Particle Nearest Neighbor Search Based on Automatic Termination Criterion

作　　者：张挺[1] 王宗锴 林震寰 郑相涵 ZHANG Ting;WANG Zongkai;LIN Zhenhuan;ZHENG Xianghan(College of Civil Engineering,Fuzhou University,Fuzhou 350116,China;College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350116,China)

机构地区：[1]福州大学土木工程学院,福建福州350116 [2]福州大学计算机与大数据学院,福建福州350116

出　　处：《工程科学与技术》2024年第6期217-229,共13页Advanced Engineering Sciences

基　　金：国家自然科学基金项目(52079032);福建省水利科技重大项目(MSK202215)。

摘　　要：对于大规模运动模拟问题而言,近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立kd-tree的最大深度dmax与粒子总数N的自适应关系式,提出了kd-tree自动终止准则,即ATC-kd-tree,同时还考虑了叶子节点大小阈值n_(0)对近邻搜索效率的影响。试验表明,ATC-kd-tree具有更高的近邻搜索效率,相较于不使用自动终止准则的kd-tree搜索效率最高提升46%,且适用性更强,可求解不同N值的近邻搜索问题,解决了粒子总数N发生改变时需要再次率定最大深度dmax的问题。同时,本文还提出了网格搜索法组合坐标下降法的两步参数优化算法GSCD法。通过2维阿米巴虫形状的参数优化试验发现,GSCD法可更为快速地率定ATC-kd-tree的可变参数,其优化效率比网格搜索法最高提升了205%,相较于改进网格搜索法最高提升了90%。研究结果表明,ATC-kd-tree和GSCD法不仅提高了近邻搜索的效率,也为复杂运动中近邻粒子搜索问题提供了一种更为高效的解决方案,能够显著降低计算资源的消耗,进一步提升模拟的精度和效率。Objective In large-scale motion simulation problems,the search efficiency for nearest neighbor points critically influences the overall operational efficiency.This study applies correlation analysis to establish an adaptive relationship between the maximum depth of the kd-tree(dmax)and the total number of particles(N).A novel automatic termination criterion for the kd-tree,known as ATC-kd-tree,addresses the impact of the leaf node size threshold(n_(0))on nearest neighbor search efficiency.This method effectively addresses the challenges of recalibrating dmax as N varies,en-hancing the efficiency and applicability of the kd-tree in various scenarios.Methods The ATC-kd-tree framework is designed to dynamically adjust the kd-tree structure based on the current particle count,ensuring optim-al performance for efficient searches in real-time applications.This method involves a comprehensive analysis of particle distributions,enabling the algorithm to adaptively modify dmax based on the specific characteristics of the particle set at any given time.The ATC-kd-tree effectively re-sponds to the spatial arrangement of particles,enhancing search accuracy and speed by integrating data-driven adjustments.In addition,a two-step parameter optimization algorithm that combines grid search with coordinate descent methods(GSCD)is introduced.This hybrid approach exped-ites the calibration of variable parameters crucial for optimizing ATC-kd-tree performance,facilitating a more precise search process.The GSCD method accelerates the pace of parameter adjustment and increases accuracy by ensuring that the most appropriate parameters are selected based on empirical evidence.A comprehensive series of experimental trials is conducted involving various particle distribution models,such as uniform,random,and clustered configurations.These trials are designed to assess the efficiency of the ATC-kd-tree and the GSCD optimization process.Key performance metrics,including search time,cache miss rates,and overall computational efficiency,are di

关 键 词：KD-TREE 粒子近邻搜索 自适应 网格搜索法 坐标下降法 

分 类 号：O35[理学—流体力学]