XPSort --树形数据多核并行外存排序算法

• 作者: 周为钢 杨良怀 王靖 边继东
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: XML文档 树形数据 排序算法 并行算法
• 年，卷（期）: 2014,（2）
• 所属期刊栏目: 学术论文
• 页码范围: 292-300
• 页数: 9页
• 分类号: TP301
• 字数: 8710字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2014.02.013

摘要

XML数据处理中一个基本问题是树形数据排序．本文针对已有算法的不足提出了一种XML文档多核并行外存排序算法---XPSort ．XPSort扫描XML文档产生相互独立的排序任务，利用多核CPU对任务进行并行处理；同时，利用数据压缩、单临时文件以及避免子树匹配等策略，有效地减少磁盘I/O ，提高排序性能；它克服了NEXSORT算法没能有效利用内存空间、存在大量随机I/O的问题以及难以处理“右深树”的缺陷，也克服了HERMES的数据冗余、大量磁盘开销等缺点．文章对不同特性的XML文档开展了大量比较实验，结果表明XPSort优于已有算法，所提优化方法是有效可行的．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨良怀	浙江工业大学计算机学院	32	138	7.0	10.0
2	周为钢	杭州市公安局交通警察局科研所	9	14	2.0	3.0
3	王靖	浙江工业大学计算机学院	3	4	2.0	2.0
4	边继东	浙江工业大学计算机学院	4	5	2.0	2.0