Improved Parallel Algorithms for Path Expression Query Processing of Semi-Structured Data

Semi-structured data can be described by a labelled directed graph. The costs of processing path expression based queries on semi-structured data could be very high due to conventional graph traversals may be intensively involved. Parallel query processing is an attractive solution for improving system performance. In this paper four parallel path-based query process methods are introduced. The first three methods are parallel versions of pointer chasing methods based on the principles of message-driven computation. In the fourth method the pro-fetch technique is used to achieve a low communication cost and a high degree of parallelisation. The initial algorithm analyses are also presented.