XML query processing using GPU

Vincent Jordan (KDE lab.)

The main purpose of this research topic is to evaluate the efficiency of GPU parallel excution for XML query processing. The algorithm implemented on GPU is the Parallel TwigStack algorithm. Parallel TwigStack execution has already been studied on cluster and multi cores CPU but not on GPU.
Original TwigStack algorithm is explained in the following research paper:

Holistic Twig Joins: Optimal XML Pattern Matching
Nicolas Bruno, Nick Koudas and Divesh Srivastava
SIGMOD 2002
Task parallelism of TwigStack algorithm is explained in the following PhD thesis:
A Study on Parallel Holistic Twig Joins for XML Query Processing
Imam Machdi
PhD thesis 2010
An implementation of Parallel TwigStack algorithm is made using the CUDA toolkit in order to get a first idea on the suitability of the current NVidia GPU architecture for XML query processing.

XML query processing overview
Overview of the project. metadata generator and query processor have been implemented.

Used algorithm does not feature an uniform parallelism which matches CUDA programation model. Its implementation requires first the development of a dynamic data structure. This work has been done by creating the v_array library.

Project location

Latest version of the implementation of my research can be found there (user account on KDE lab. server is required):
svn+ssh://kde.cs.tsukuba.ac.jp/projects/webdav/data/home/vjordan/svn/

Documentation

Howto

Wiki

Random questions

Links

xhtml valid? | css valid? | last update on August 2010