求k邻域的体素栅格算法研究

• 作者: 董洪伟
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: k最近邻域 BSP树 kd树
• 年，卷（期）: 2007,（21）
• 所属期刊栏目: 学术探讨
• 页码范围: 52-56
• 页数: 5页
• 分类号: TP391
• 字数: 4657字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2007.21.016

摘要

给定一个度量空间中的一组数据点集,k邻域问题在于对于某个数据点求出按照该空间的距离度量离数据点最近的k个数据样本.目前主要有2种方法,一种是基于立方体分割形成的三维立方体体素索引数组的体素栅格(CG(Cell Grid)方法,另一种方法是基于树索引结构的方法如kd-Tree等.论文主要研究经典CG方法及解决其内存消耗过多问题的两个改进方法:排序体素栅格(SCG)方法和投影体素栅格(PCG)方法.CG、SCG、PCG算法采用了改进的搜索方法,避免了传统CG算法[2-4]可能得到错误k邻域的问题.对三种算法的时空性能进行了分析比较,给出了相应的实验比较数据.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	董洪伟	江南大学信息工程学院	49	386	11.0	18.0