论文摘要
可视化技术是海量数据处理与分析的重要手段。目前海量数据可视化面临许多困难,存在预处理时间长、绘制速度慢、磁盘消耗大等问题,实现海量数据的实时、交互可视化仍十分困难,因此该领域是国际上可视化的研究难点与热点。本文在系统地研究与分析海量数据预处理方法、并行绘制技术及加速显示方法的基础上,针对存在的问题,结合坐标空间划分、标量空间划分、核外数据调度及并行绘制显示等方法,对基于数据二维划分的BBIO树技术、基于跨度空间划分的压缩索引技术进行了深入研究,并完成了相关算法与系统框架实现。本文的主要工作及取得的主要研究成果包括:1)提出了加速BBIO树节点区间检索过程的四端点算法。针对传统BBIO树构造算法易产生病态树形结构的缺陷,四端点算法对BBIO树节点进行了基于重排序的组织与管理,有效提高了BBIO树节点内元单元的搜索效率,保证了实验规模数据的树形结构检索时间小于0.001秒。2)提出了基于数据二维划分的BBIO树方法。通过对海量数据集进行坐标空间的二维划分,使数据集的绘制显示能够适合多通道显示环境的显示需求,从而实现海量数据高分辨率显示的目的。在绘制阶段使用间隔标记法,元单元等值面提取时间较传统Marching Cubes平均减少了23%。3)提出了基于跨度空间划分的压缩索引方法。针对坐标空间划分数据易造成并行处理负载不均衡的问题,使用跨度空间划分方法分割网格标量空间,并使用并行归并排序和全互换数据通信完成对数据的分配,有效保证了并行绘制负载均衡。针对跨度空间划分方式存在索引结构占内存大的问题,采用压缩索引方法实现了基于压缩结构的BBIO树索引,与传统BBIO树组织结构相比,索引数据所占空间减少了40%。4)提出了基于立方体子元单元的二叉区间树方法。针对间隔标记法存在的性能与等值面分布相关问题,采用立方体子元单元对元单元进行划分组织,提高了等值面加速绘制性能。实验结果表明采用新方法绘制速度较传统Marching Cubes算法平均提高了32%。5)结合基于数据二维划分的BBIO树方法和基于跨度空间划分的压缩索引方法,依照现代软件工程的目标和原则,构建了海量数据可视化框架结构,描述了完整的包图和类结构图,明确了模块的功能,阐明了模块与模块之间的关系。框架结构具有扩展性好、重用性强等特点。