Parallel Structural Join Algorithm on Shared-memory Multi-core Systems

摘要：

The leap from single-core to multi-core has permanently altered the course of computing, enabling increased productivity, powerful energy-efficient performance, and leading-edge advanced computing experiences.Although traditional single-thread Xpath query evaluation algorithms can run properly on multi-core CPUs, they cannot take full use of the computing resources of multi-core CPUs.To take advantage of multi-core, efficient parallel algorithms are fairly desirable to evaluate Xpath in parallel.In this paper, we present, PSJ, an efficient Parallel Structural Join algorithm for evaluating Xpath.PSJ can skip many ancestor or descendant elements by evenly and efficiently partitioning the input element lists into some buckets.PSJ obtains high performance by evaluating Xpath step in each bucket in parallel.It is very efficient to partition the input lists and is effective to evaluate Xpath step in buckets, and therefore PSJ achieves a high speedup ratio.We have implemented our proposed algorithm and the experimental results show that PSJ algorithm achieves high performance and outperforms the existing state-of-the-art methods significantly.

关键词： even partition parallel speedup ratio structural join

作者: Le Liu Jianhua Feng Guoliang Li Qian Qian Jianhui Li

作者单位: Department of Computer Science and chnology Tsinghua University Beijing,China Department of Computer Science and Technology Tsinghua University Beijing,China Intel Corporation Shanghai,China

会议类型: 国际会议

会议名称: The Ninth International Conference on Web-Age Information Management(第九届web时代信息管理国际会议)(WAIM 2008)

会议地点: 张家界

会议语种:英文

在线出版日期: 2008-07-20（万方平台首次上网日期，不代表论文的发表时间）