XPSort：A Multi-core Parallel Sorting Algorithm for Hierarchical Data in External Memory

YANG Liang-huai; WANG Jing; ZHOU Wei-gang; BIAN Ji-dong

您当前的位置：

首页 >

文章列表页 >

XPSort：A Multi-core Parallel Sorting Algorithm for Hierarchical Data in External Memory

更新时间：2025-07-16

- XPSort：A Multi-core Parallel Sorting Algorithm for Hierarchical Data in External Memory
- Acta Electronica Sinica Vol. 42, Issue 2, Pages: 292-300(2014)
- 作者机构：
  
  1. 浙江工业大学计算机学院,浙江,杭州,310023
  2. 杭州市公安局交通警察局科研所,浙江,杭州,310014
  3. 浙江工业大学计算机学院,浙江,杭州,310023
  4. 杭州市公安局交通警察局科研所,浙江,杭州,310014
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP301
- Published：2014
- 稿件说明：
移动端阅览
YANG Liang-huai, WANG Jing, ZHOU Wei-gang, et al. XPSort：A Multi-core Parallel Sorting Algorithm for Hierarchical Data in External Memory[J]. Acta Electronica Sinica, 2014, 42(2): 292-300.
DOI：

YANG Liang-huai, WANG Jing, ZHOU Wei-gang, et al. XPSort：A Multi-core Parallel Sorting Algorithm for Hierarchical Data in External Memory[J]. Acta Electronica Sinica, 2014, 42(2): 292-300. DOI：

摘要

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

Abstract

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 executions 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 utilization

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.

关键词

Keywords

references

Views

1424

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design

A Fast Efficient Parallel Algorithm for Hough Transform

An Efficient Parallel Algorithm for H.264/AVC Encoder

An Implementation for Parallel Computing SPT in Cluster Router

Related Author

XU Ning

CHEN Guo-long

GUO Wen-zhong

LI Ze-peng

LIU Geng-geng

QIN Ling

CHEN Ling

CHEN Hong-jian

Related Institution

College of Computer and Data Science, Fuzhou University

School of Information Engineering, Wuhan University of Technology

National Key Lab of Novel Software TechNanjing Univ.NanjingJiangsu 210093China

Department of Computer ScienceYangzhou UniversityYangzhouJiangsu 225009China

National Key Lab of Novel Software Tech,Nanjing Univ.

⁰