文献

J-GLOBAL ID：202202243034814215   整理番号：22A1085540

二分探索を越えて:暗黙探索木レイアウトの並列インプレース構築【JST・京大機械翻訳】

Beyond Binary Search: Parallel In-Place Construction of Implicit Search Tree Layouts

著者 (4件)： Berney Kyle (Information and Computer Sciences, University of Hawai’i at Manoa, Honolulu, HI, USA) ,  Casanova Henri (Information and Computer Sciences, University of Hawai’i at Manoa, Honolulu, HI, USA) ,  Karsin Ben (System Engineering, NVIDIA Corporation, Santa Clara, CA, USA) ,  Sitchinava Nodari (Information and Computer Sciences, University of Hawai’i at Manoa, Honolulu, HI, USA)
資料名： IEEE Transactions on Computers  (IEEE Transactions on Computers)
巻： 71  号： 5  ページ： 1104-1116  発行年： 2022年 
JST資料番号： C0233A  ISSN： 0018-9340  CODEN： ICTOB4  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 並列アルゴリズムを提示し,レベル次数二値探索ツリー(BST),レベル次数Bツリー(Bツリー),およびvan Emde Boas(vEB)レイアウトに,ソートアレイを効率的に透過する。提案アルゴリズムの複雑性を解析的に決定し,その性能を経験的に測定した。データを入力して,一連の探索クエリを実行するために,全時間を考慮するとき,vEBレイアウトはCPUに関して最良の性能を提供した。NN=537百万64ビット整数の入力を考えて,クエリ性能(バイナリ探索と比較して)の利益は,NNクエリのわずか0.37%を実行するとき,現場置換のコストを凌駕する。GPU上では,結果は,BツリーとvEBレイアウトが最良である特定のアーキテクチャに依存する。二値探索によるブレークンポイントに達するのに必要なクエリの数は,NN=1,074百万32ビット整数の1.3%から8.9%までの範囲である。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  性能 ,  レイアウト ,  ソーティング ,  木【グラフ】 ,  計算機アーキテクチャ ,  *二分探索 ,  並列アルゴリズム
準シソーラス用語： Bツリー ,  複雑性 ,  クエリー ,  探索木 ,  バイナリー , 【Automatic Indexing@JST】

分類 (2件)： データベースシステム  (JD03030U) ,  計算機網  (JC03000K)

タイトルに関連する用語 (4件)： 二分探索 ,  探索木 ,  レイアウト ,  構築