CAJ | 학술논문

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