摘要
对于大规模运动模拟问题而言,近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立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 diligently monitored and analyzed.Rigorous comparisons against baseline methods,comprising traditional kd-trees and alternative sorting algorithms,are executed to ensure a thor-ough evaluation of the proposed techniques.Results and Discussions The study’s findings demonstrated that the ATC-kd-tree framework significantly improves the efficiency of nearest neighbor searches,especially in large-scale motion simulations characterized by dynamically fluctuating particle distributions.Experiments in-volving particle distribution shapes,such as rectangular,cuboidal,notched cuboidal,spherical,and annular,are frequently employed in fluid dy-namics studies to corroborate their efficiency.The ATC-kd-tree achieved an impressive average reduction in search time of up to 30.3%com-pared to traditional unsorted kd-tree implementations across all tested configurations.When analyzing datasets comprising 40000 and 575000 particles,the search times exhibit significant enhancement:the ATC-kd-tree reduces the search time from 1.75 seconds with traditional methods to 1.22 seconds for the former dataset and from 7.12 seconds to 4.97 seconds for the latter.This performance improvement is particularly marked in environments with high spatial divergence among particles,where traditional methods often falter with inconsistent search paths.In addition,an average reduction of 24.2%in cache miss rates is observed when employing the ATC-kd-tree.In scenarios with larger particle counts,the cache miss rate decreases from 35%in the traditional unsorted kd-tree to 26%with the ATC-kd-tree,which directly contributes to enhanced computa-tional efficiency,facilitating quicker data retrieval during neighbor searches.The ATC-kd-tree demonstrated exceptional adaptability to rapidly evolving particle configurations in computational fluid dynamics(CFD)simulations.In a specific experiment involving 50000 particles exposed to external forces causing irregular movements,the ATC-kd-tree shows a 20%reduction in cache misses and a 15%decrease in overall computa-tional time compared to traditional methods.This capacity to effectively manage irregular particle movements underscores the ATC-kd-tree’s ro-bustness for real-time applications that demand rapid adaptability to dynamic changes.The GSCD optimization method further augments the per-formance of the ATC-kd-tree,as the analysis indicates that GSCD accelerates parameter calibration by 205%relative to traditional grid search methods.In experiments,the GSCD method reduces calibration time significantly,from over 120 seconds in traditional methods to approxim-ately 40 seconds.This enhancement enables rapid adjustments to the parameters of the kd-tree and ensures that the tree remains optimally con-figured to the specific characteristics of the particle distributions encountered during simulations.The adaptability of the ATC-kd-tree is evident across various particle distribution scenarios.This algorithm consistently surpasses traditional unsorted kd-trees and alternative sorting methods in clustered configurations,such as the Z-index sort.In these configurations,the search time is significantly reduced,demonstrating the ATC-kd-tree’s ability to dynamically reorganize its structure based on real-time analysis of particle distributions.This capability maximizes cache utilization and minimizes cache misses.The findings indicated that the ATC-kd-tree is particularly effective in scenarios involving non-uniform particle dis-tributions,as its capacity to adjust dmax based on the number of particles eliminates the cumbersome recalibration processes typically required by traditional methods.Hence,this leads to a smoother and more efficient search process,even as particle distributions experience significant changes.These results highlight the critical importance of incorporating adaptive techniques into kd-tree implementations to improve search effi-ciency in large-scale simulations.The improvements in search time and cache utilization achieved by the ATC-kd-tree provide compelling evid-ence of its potential to transform how nearest neighbor searches are conducted in dynamic environments.Conclusions The introduction of the ATC-kd-tree provides a valuable approach to optimizing kd-tree-based nearest neighbor searches,particu-larly in dynamic and large-scale motion simulations.This research aims to enhance search efficiency and deliver a scalable solution for managing varying particle distributions by integrating an automatic termination criterion with a rapid parameter optimization method.The results showed that the ATC-kd-tree can improve operational performance,reducing computational overhead and cache misses,which is crucial for real-time ap-plications where efficiency is paramount.In addition,the principles explored in this study can extend beyond the kd-tree framework,demonstrat-ing new avenues for research into adaptive data access techniques that can prove beneficial across various computational domains,including ma-chine learning,computer graphics,and robotics.Future efforts will concentrate on integrating the ATC-kd-tree with advanced cache management strategies to optimize performance and investigate methods to reduce computational complexity in high-dimensional contexts,which remains a critical area of investigation.This study aims to address these challenges and broaden the applicability of kd-tree methods in real-time environ-ments,making them more adaptable to complex and dynamic conditions.It contributes to enhancing the functionality of kd-trees and provides in-sights into the broader field of data structure optimization,laying a foundation for future developments in efficient data processing techniques.
作者
张挺
王宗锴
林震寰
郑相涵
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)
出处
《工程科学与技术》
EI
CAS
CSCD
北大核心
2024年第6期217-229,共13页
Advanced Engineering Sciences
基金
国家自然科学基金项目(52079032)
福建省水利科技重大项目(MSK202215)。
