高效KD树并行算法优化

摘要：

KD树作为一种用于查询高维键值的流行算法,由于其准确性高、可扩展性强与较快的查询速度而应用于多媒体检索领域, 但缓慢的建树效率已不能很好的满足当前的应用场景. 针对 KD 树的低效建树过程, 作者探寻并分析了KD树建树现存的并行潜能并提出了一种面向KD树建树过程的多核并行算法—ParK(Parallel KD-Tree). ParK探求了不同的并行模式来充分利用现代硬件中的计算资源,并在此基础上提出了一种新的内存分配策略来解决并行处理中的数据争用状况. 实验结果表明Park相比于原始串行版本最高能够在16核的服务器上达到21.75倍的加速.

关键词：多媒体检索、KD树、多核、并行

所属期刊栏目：24

分类号：TP3;TB9

资助基金：上海市科委科技攻关项目13DZ1108800;国家高技术研究发展计划8632012AA010901;国家自然科学基金61370081

在线出版日期：2015-10-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1-9