空间剖分树形查找结构的效率分析  

Analyzing efficiency of space-subdivision-based searching data structures

作　　者：董晓芬[1,2] 张伟[1] 庞明勇[1,2] DONG Xiaofen;ZHANG Wei;PANG Mingyong(College of Information Science and Engineering, Zaozhuang University, Zaozhuang, Shandong 277000, China;Department of Educational Technology, Nanjing Normal University, Nanjing 210097, China)

机构地区：[1]枣庄学院信息科学与工程学院,山东枣庄277000 [2]南京师范大学教育技术系,南京210097

出　　处：《计算机工程与应用》2016年第15期73-78,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.41271383;No.60873175);江苏省高校自然科学基金(No.11KJB520008);江苏省现代教育技术研究2014年度课题(No.2014-R-33356)

摘　　要：空间剖分是构造快速空间查找数据结构的有效方法,四叉树、八叉树、Kd-树是典型的基于空间剖分思想的树形空间查找结构。选择合适的参数来构造实际点集数据的树形查找结构,对提高相关算法的效率具有重要意义。在分析三种树形查找结构基本原理的基础上,通过构造具有不同空间分布特征的实验数据,设置不同的树形空间剖分结构参数,来分析三种结构支持下搜索算法的时间消耗,确定使查找效率达到最优的树形结构构造参数。相关研究结论对于优化空间剖分树形查找结构的效率、提高相关算法的性能等,有一定的参考价值。Space subdivision is a key and efficient way for constructing data structures of point searching, such as quad-tree,octree and Kd-tree and so on, which are typical data structures constructed on space subdivision. How to choose suitableparameters to construct the tree structures has obvious and significant impact on the efficiency of the algorithms that thestructures are involved in. In this paper, based on analyzing the basic ideas of these three tree structures, it investigatesand discusses the relationship between the parameters of the trees and the time-efficiency of the algorithms by a set ofpoint data with various space distributions. It gives optimized tree-parameters finally. The conclusion can provide a usefulguide for constructing optimized tree structures for point searching algorithm.

关 键 词：空间剖分 树形数据结构 最近邻点搜索 算法优化 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]