基于查表的空间填充曲线映射算法  

Table-based Space-filling Curve Generation

作　　者：吴国福[1] 窦强[1] 窦文华[1] 

机构地区：[1]国防科技大学计算机学院,湖南长沙410073

出　　处：《国防科技大学学报》2010年第5期75-79,共5页Journal of National University of Defense Technology

基　　金：国家自然科学基金资助项目(60633050)

摘　　要：空间填充曲线是进行数据降维处理的典型方法。首先给出对角线空间填充曲线的映射规则,该规则使得在高维情况下存在唯一曲线,并且每一维度上的格点数目不受限制。然后提出等势面的概念,推导出不同等势面上格点数量的递推关系。在此基础上,给出基于查表的对角线空间填充曲线映射算法,该算法执行快、可扩展性好,其时间复杂度随维度的增加呈线性增长。Space-filling curves are classical ways to reduce the dimensions of data.This paper first presents the mapping rules of the diagonal space-filling curve.Unique curve which exists under the rules and the number of grids on each dimensionality is not constrained.Then a new conception about equipotential surface was given,and the relationship between the number of grids on different equipotential surface was dirived.Table-based space-filling curve generation algorithms on the basis of the realtionship were presented.It is found that the algorithms have low running time and high scalability.

关 键 词：空间填充曲线 对角线 等势面 降维 

分 类 号：O244[理学—计算数学]