Analysis of Parallel Query Processing Algorithms for Semi-structured Data

Abstract

Semi-structured data can be described by a labelled directed graph. Query costs on semi-structured data could be very high due to the sequential processing of path matching in a graph shape data structure. In this paper two types of parallel path-based query processing methods are introduced for improving the system performance. The first type includes three parallel version of pointer chasing methods based on the principle of message-driven computation. In the second type of method, the pre-fetch technique is used to achieve a low communication cost and a high degree of parallelisation.