Multi-Core Processing of XML Twig Patterns

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, which often may be abstracted by twig patterns. Finding all occurrences of such a twig pattern in an XML database is a basic operation for XML query processing. We present the parallel path stack algorithm (PPS) and the parallel twig stack algorithm (PTS). PPS and PTS are novel and efficient algorithms for matching XML query twig patterns in a parallel multi-threaded computing platform. PPS and PTS are based on the PathStack and TwigStack algorithms [1]. These algorithms employ a sophisticated search technique for limiting processing to specific subtrees. We conducted extensive experimentation with PPS and PTS. We compared PPS and PTS to the standard (sequential) PathStack and TwigStack algorithms in terms of run time (to completion). We checked their performance for varying numbers of threads. Experimental results indicate that using PPS and PTS significantly reduces the running time of queries in comparison with the PathStack/TwigStack algorithm (up to 44 times faster for DBLP queries and up to 22 times faster for XMark queries).