Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (9): 146-150.DOI: 10.3778/j.issn.1002-8331.2009.09.042

• 数据库、信号与信息处理 • Previous Articles     Next Articles

Multifractal dimension and multifractal spectrum algorithm based on Z-ordering technique

YAN Guang-hui1,MA Zhi-cheng2,LIU Li-song1,Du Lin-na1,YANG Xia-xia1   

  1. 1.School of Information and Electrical Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China
    2.Gansu Electric Power Information & Communication Centre,Lanzhou 730050,China
  • Received:2008-01-28 Revised:2008-04-25 Online:2009-03-21 Published:2009-03-21
  • Contact: YAN Guang-hui

基于Z-ordering的多重分形维数及多重分形谱算法

闫光辉1,马志程2,刘利松1,杜琳娜1,杨霞霞1   

  1. 1.兰州交通大学 电子与信息工程学院,兰州 730070
    2.甘肃电力信息通信中心,兰州 730050
  • 通讯作者: 闫光辉

Abstract: The efficient algorithm for evaluating the fractal dimension is the key problem to the implementation of the fractal theory.However,the classical fractal dimension algorithm has become a bottle neck in the application of the fractal theory for its high time and space complexity.Based on Z-ordering technique,the ZBMFD(Z-ordering Based Multifractal Dimension) algorithm is presented.ZBMFD scans the dataset only once to initialize the lowest cell queue and evaluates the fractal dimension of the data set through mapping the lower cells to the higher cells by transforming the coordinate of the lower cells.The elementary time-space complexity of the ZBMFD is presented.Several comparative experiments using synthetic and real life data set show the performance and the effectivity of ZBMFD.

摘要: 分形维数的高效求解是分形理论应用与实践的关键问题,传统分形维数计算方法由于时空复杂性高已成为当前分形技术应用的一个主要瓶颈。借鉴Z-ordering索引技术的思想,设计并实现了一种改进的多重分形维数计算方法ZBMFD(Z-ordering Based Multifractal dimension Algorithm),该方法扫描数据集一遍建立底层网格结构,通过动态修改网格坐标编码递推实现低层网格到高层网格之间的动态映射并计算数据集的分形维数。在实际数据集的实验表明算法在保持O(N×logN)时间复杂性的基础上,降低了分形维数算法的空间复杂性,且计算结果精度与已有算法相当,拓广了分形技术在当前高维、海量数据处理等领域的应用。