? Efficient Processing of Distributed Twig Queries Based on Node Distribution
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2017, Vol. 32 Issue (1) :78-92    DOI: 10.1007/s11390-017-1707-1
Data Management and Data Mining Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
Efficient Processing of Distributed Twig Queries Based on Node Distribution
Xin Bi, Xiang-Guo Zhao*, Member, CCF, and Guo-Ren Wang, Member, CCF, ACM, IEEE
College of Computer Science and Engineering, Northeastern University, Shenyang 110815, China

Related Articles
Download: [PDF 468KB]     Export: BibTeX or EndNote (RIS)  
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.
Articles by authors
Xin Bi
Xiang-Guo Zhao
Guo-Ren Wang
KeywordsXML   twig query   distributed computing   node distribution     
Received 2016-02-29;

This work is supported in part by the National Natural Science Foundation of China under Grant Nos. 61272181, 61672145, 61572121 and U1401256.

Corresponding Authors: Xiang-Guo Zhao     Email: zhaoxiangguo@mail.neu.edu.cn
About author: Xin Bi received his M.S. degree in computer science from Northeastern University, Shenyang, in 2011. Currently, he is a Ph.D. candidate of Northeastern University, Shenyang. His main research interest includes XML data management and distributed database system.
Cite this article:   
Xin Bi, Xiang-Guo Zhao, Guo-Ren Wang.Efficient Processing of Distributed Twig Queries Based on Node Distribution[J]  Journal of Computer Science and Technology, 2017,V32(1): 78-92
Copyright 2010 by Journal of Computer Science and Technology