Media.Player

A parallel twig join algorithm for XML processing using a GPGPU (Technion)

Summary

Background:
The problem is how to match XML query twig patterns in a parallel graphics processing unit (GPU) multi-threaded computing platform. There are sequential solutions to this problem such as the PathStack/TwigStack algorithm and its parallelization for corresponding CPU multi-threaded computing platforms. The limitation of the current algorithms is the number of threads that can be used along with these algorithms. The current algorithms only fit systems with a maximum of several dozens of threads.

Method:
The presented algorithm uses the data and task parallelism of the GPU to perform memory-intensive tasks allowing the CPU to be used to perform I/O and resource management. The invention therefore efficiently exploits both the high-bandwidth GPU memory interface and the lower-bandwidth CPU main memory. This approach uses the representation of positions of XML elements and string values via stream representation, in which each stream contains the positional representations of the database nodes whose label is identical to that of some particular element label in the document. The proposed novel storage scheme for managing XML documents enables the efficient identification of the ancestors of each node in the XML document tree, within the stream representation of the document. Then, the relevant data for answering the query among a large amount of different threads can be distributed, enabling the parallel processing of a single query.

Technology Benefits

· Uses GPUs to accelerate the processing of a single query, when a stream representation of documents is used

· Enables encoding the structural characteristics of the document within the streams

· Allows database systems that support XML documents to work in a multi-core GPU environment

· Significantly increases the speedup of processing twig joins for XML documents

Technology Application

Improving database systems that support XML documents to work in multi-core GPU environment.

ID No.

COM-1401

Country/Region

Israel