DocumentCode :
3036678
Title :
Comparison of parallel algorithms for path expression query in object database systems
Author :
Wang, Guoren ; Yu, Ge ; Kaneko, Kunihiko ; Makinouchi, Akifumi
Author_Institution :
Sch. of Inf. Sci. & Eng., Northeastern Univ., Shenyang, China
fYear :
2001
fDate :
21-21 April 2001
Firstpage :
250
Lastpage :
257
Abstract :
Proposes a new parallel algorithm for computing path expressions, named the "parallel cascade semi-join" (PCSJ) algorithm. Moreover, a new scheduling strategy called the "right-deep zigzag tree" is designed to further improve the performance of the PCSJ algorithm. The experiments have been implemented in a distributed and parallel NOW (network of workstations) environment. The results show that the PCSJ algorithm outperforms two other parallel algorithms [the parallel forward pointer chasing (PFPC) algorithm and the index-splitting parallel algorithm (IndexSplit)] when computing path expressions with restrictive predicates, and that the right-deep zigzag tree scheduling strategy has a better performance than the right-deep tree scheduling strategy.
Keywords :
object-oriented databases; parallel algorithms; query processing; scheduling; tree data structures; workstation clusters; IndexSplit algorithm; algorithm performance; distributed parallel environment; index splitting; object database systems; parallel algorithms; parallel cascade semi-join algorithm; parallel forward pointer chasing algorithm; path expression queries; restrictive predicates; right-deep zigzag tree; scheduling strategy; workstation network; Algorithm design and analysis; Binary search trees; Concurrent computing; Data engineering; Database systems; Object oriented databases; Parallel algorithms; Scheduling algorithm; Software libraries; Spatial databases;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Database Systems for Advanced Applications, 2001. Proceedings. Seventh International Conference on
Conference_Location :
Hong Kong, China
Print_ISBN :
0-7695-0996-7
Type :
conf
DOI :
10.1109/DASFAA.2001.916385
Filename :
916385
Link To Document :
بازگشت