A Parallel Navigation Algorithm with Dynamic Load Balancing for OODBMSs

• Item type: Trans(1)
• 公開日: 1999-05-15
• タイトル: A Parallel Navigation Algorithm with Dynamic Load Balancing for OODBMSs
• タイトル / 言語: en
• タイトル: A Parallel Navigation Algorithm with Dynamic Load Balancing for OODBMSs
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Institute of Industrial Science University of Tokyo
• 著者所属: Department of Information Science Utsunomiya University
• 著者所属: Department of Information Science Utsunomiya University
• 著者所属: Department of Information Science Utsunomiya University
• 著者所属(英): en
• 著者所属(英): Institute of Industrial Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Utsunomiya University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Utsunomiya University
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Utsunomiya University
• 著者名: LAWRENCE, MUTENDA; TAKANOBU, BABA; TSUTOMU, YOSHINAGA; KANEMITSU, OOTSU
• 著者名(英): Lawrence, Mutenda; Takanobu, Baba; Tsutomu, Yoshinaga; Kanemitsu, Ootsu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: High-performance navigational access to objects is crucial if the demands of object-oriented database management system (OODBMS) target application areas are to be met. We propose an algorithm to navigate in parallel objects in a parallel OODBMS for a shared-nothing environment. The algorithm exploits among others qualified path expressions and the setvalued nature of OODBMS attributes to generate independent paths that can be traversed in parallel if the objects referenced therein are declustered across multiple nodes. We also propose a decentralised dynamic load balancing algorithm based on the premise that the cost of arbitrary user-defined functions (UDF) in the predicates of qualified path expressions can be estimated accurately by an average calculated over time and used in determining the load at each node in a shared-nothing system. Analytical and simulation results are presented which show that our navigation and load balancing strategies can improve query response time significantly. Simulation shows that if objects are uniformly partitioned across system nodes our algorithm can achieve a speedup of up to 13.1 from 2 to 32 nodes. If the data is skewed dynamic load balancing decreases the response time for navigating a seven level path expression by up to 34 %.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: High-performance navigational access to objects is crucial if the demands of object-oriented database management system (OODBMS) target application areas are to be met. We propose an algorithm to navigate, in parallel, objects in a parallel OODBMS for a shared-nothing environment. The algorithm exploits, among others, qualified path expressions and the setvalued nature of OODBMS attributes to generate independent paths, that can be traversed in parallel if the objects referenced therein are declustered across multiple nodes. We also propose a decentralised dynamic load balancing algorithm based on the premise that the cost of arbitrary user-defined functions (UDF) in the predicates of qualified path expressions can be estimated accurately by an average calculated over time and used in determining the load at each node in a shared-nothing system. Analytical and simulation results are presented which show that our navigation and load balancing strategies can improve query response time significantly. Simulation shows that if objects are uniformly partitioned across system nodes, our algorithm can achieve a speedup of up to 13.1 from 2 to 32 nodes. If the data is skewed, dynamic load balancing decreases the response time for navigating a seven level path expression by up to 34 %.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 40, 号 SIG05(TOD2), p. 29-42, 発行日 1999-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会