Parallel Prime Number Labeling of Large XML Data Using MapReduce

Massive XML (Extensible Markup Language) data are available on the web. XML data labeling schemes have been suggested for structural query processing of massive XML data. Notable schemes include interval- based, prefix-based, and prime number-based labeling schemes. Of these, the prime number labeling scheme has the advantage of query processing by simple arithmetic operations. However, a parallel algorithm for this scheme does not exist. The requirement that all parents' labels have to be multiplied to obtain the label of a node makes it difficult to label XML data in a parallel fashion. To address the issue, in this paper, we propose a cluster-based technique wherein all parent nodes for a node are aggregated to compute its label by two-step MapReduce jobs. Our experiments on real-world XML datasets showed the advantages over a single machine-based system.