Paper Info
Title
Parallel Structural Join Algorithm on Shared-Memory Multi-Core Systems
Abstract
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.
Year
DOI
Venue
2008
10.1109/WAIM.2008.11
WAIM
Keywords
Field
DocType
parallel structural join algorithm,xpath step,high speedup ratio,efficient parallel structural join,psj algorithm,shared-memory multi-core systems,traditional single-thread xpath query,high performance,evaluation algorithm,efficient parallel algorithm,multi-core cpus,computing resource,parallel,encoding,algorithm design and analysis,relational databases,energy efficiency,parallel algorithms,computer science,productivity,energy efficient,parallel algorithm,concurrent computing,xml,information management,computer experiment
Algorithm design,Shared memory,Computer science,Parallel algorithm,Parallel computing,Algorithm,XPath,Concurrent computing,Multi-core processor,Encoding (memory),Speedup
Conference
Citations 
PageRank 
References 
9
0.60
15
Authors
5
Name
Order
Citations
PageRank
Le Liu17011.08
Jianhua Feng22713121.30
Guoliang Li33077154.70
Qian Qian4273.70
Jianhui Li514631.34