Technical Report CS-2012-03

Title: Practical and Theoretical Aspects of a Parallel Twig Join Algorithm for XML Processing using a GPGPU
Authors: Lila Shnaiderman, Oded Shmueli
Abstract: With an increasing amount of data and demand for fast query processing, the efficiency of database operations continues to be a challenging task. A common approach is to leverage parallel hardware platforms. With the introduction of general-purpose GPU (Graphics Processing Unit) computing, massively parallel hardware has become available within commodity hardware. XML is based on a tree-structured data model. Naturally, the most popular XML querying language (XPath) uses patterns of selection predicates on multiple elements, related by a tree structure. These are often abstracted by twig patterns. Finding all occurrences of such a (XML query) twig pattern in an XML document is a core operation for XML query processing. We present a new algorithm, GPU-Twig, for matching twig patterns in large XML documents, using a GPU. Our algorithm uses the data and task parallelism of the GPU to perform memory-intensive tasks whereas the CPU is used to perform I/O and resource management. We therefore efficiently exploit both the high-bandwidth GPU memory interface and the lower-bandwidth CPU main memory.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2012
To the main CS technical reports page

Computer science department, Technion