摘要
XML数据处理中一个基本问题是树形数据排序.本文针对已有算法的不足提出了一种XML文档多核并行外存排序算法——XPSort.XPSort扫描XML文档产生相互独立的排序任务,利用多核CPU对任务进行并行处理;同时,利用数据压缩、单临时文件以及避免子树匹配等策略,有效地减少磁盘I/O,提高排序性能;它克服了NEXSORT算法没能有效利用内存空间、存在大量随机I/O的问题以及难以处理"右深树"的缺陷,也克服了HERMES的数据冗余、大量磁盘开销等缺点.文章对不同特性的XML文档开展了大量比较实验,结果表明XPSort优于已有算法,所提优化方法是有效可行的.
A fundamental problem in XML data handling is hierarchical data sorting .This paper focuses on this problem and proposes an effective sorting algorithm called XPSort for XML document .XPSort exploits multi-core CPU to parallelize the execu-tions of the mutually independent tasks generated by scanning the XML document ;and effectively reduces disk I/Os through data compression ,single temporary-file storage and avoidance of tree-matching .XPSort overcomes the issues of inefficient space utiliza-tion ,large number of random I/Os and inability to handle right-deep tree in NEXSORT ,and avoids data redundancy and large disk I/O costs in HERMES .Extensive experiments on XML documents with different characteristics show that XPSort outperforms other existing sorting algorithms .
出处
《电子学报》
EI
CAS
CSCD
北大核心
2014年第2期292-300,共9页
Acta Electronica Sinica
基金
国家自然科学基金(No.61070042)
浙江省自然科学基金(No.Y1090096
No.Y13F020110)
关键词
XML文档
树形数据
排序算法
并行算法
XML document
hierarchical data
sorting algorithm
parallel algorithm
