Efficient Processing of Distributed Twig Queries Based on Node Distribution

Xin Bi, Xiang Guo Zhao*, Guo Ren Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

Massive XML data are increasingly generated for the representation, storage and exchange of web information. Twig query processing over massive XML data has become a research focus. However, most traditional algorithms cannot be directly implemented in a distributed manner. Some of the existing distributed algorithms generate a lot of useless intermediate results and execute many join operations of partial results in most cases; others require the priori knowledge of query pattern before XML partition, storage and query processing, which is impractical in the cases of large-scale data or frequent incoming new queries. To improve efficiency and scalability, in this paper, we propose a 3-phase distributed algorithm DisT3 based on node distribution mechanism to avoid unnecessary intermediate results. Furthermore, we propose a lightweight local index ReP with an enhanced XML partitioning approach using arbitrary partitioning strategy, and based on ReP we propose an improved 2-phase distributed algorithm DisT2ReP to further reduce the communication cost. After the performance guarantees are analyzed, extensive experiments are conducted to verify the efficiency and scalability of our proposed algorithms in distributed twig query applications.

Original languageEnglish
Pages (from-to)78-92
Number of pages15
JournalJournal of Computer Science and Technology
Volume32
Issue number1
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes

Keywords

  • XML
  • distributed computing
  • node distribution
  • twig query

Fingerprint

Dive into the research topics of 'Efficient Processing of Distributed Twig Queries Based on Node Distribution'. Together they form a unique fingerprint.

Cite this