文献

J-GLOBAL ID：202002219259387873   整理番号：20A1922065

ビッグデータ計算における扱いやすさの認識【JST・京大機械翻訳】

Recognizing the tractability in big data computing

著者 (4件)： Gao Xiangyu (Harbin Institute of Technology, Harbin, Heilongjiang 150001, China) ,  Li Jianzhong (Harbin Institute of Technology, Harbin, Heilongjiang 150001, China) ,  Miao Dongjing (Harbin Institute of Technology, Harbin, Heilongjiang 150001, China) ,  Liu Xianmin (Harbin Institute of Technology, Harbin, Heilongjiang 150001, China)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 838  ページ： 195-207  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 既存のコンピュータの計算電力の限界により,多項式時間は,大きなデータコンピューティングにおける扱いやすい問題を同定するのに働かない。本論文は,新しい標準としてサブ線形時間を採用して,大きなデータコンピューティングにおける扱いやすさを認識し,計算複雑度理論に関して扱いやすい問題を研究した。ランダムアクセスTuringマシンを計算モデルとして用いて,大きなデータで扱いやすい問題を特徴付けた。最初に,純粋な扱いやすいクラスPTを提案し,その内の2つの重要なクラス,PPLとPDPを研究した。この2つの純粋な扱いやすいクラスの構造を深く調べ,それらはPPLi⊂PPLi+1,PPL>PTおよびPDPk+1>PDPk>PTであることを立証した。次に,擬似牽引可能なクラスPsTを提案して,前処理技術に従って,2つのクラス,PsTRとPsTEに分割した。擬似牽引可能クラスと他の複雑性クラス間の関係を調べ,PsT⊆Pと[数式:原文を参照]が証明した。最後に,PPLはDLOGTIME還元の下で閉鎖されることを示した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 電力 ,  前処理 ,  *Turing機械 ,  計算量 ,  線形性 ,  コンピュータ ,  計算モデル
準シソーラス用語： ランダムアクセス ,  複雑性 ,  多項式時間 ,  *ビッグデータ , 【Automatic Indexing@JST】

著者キーワード (4件)： ビッグデータコンピューティング ,  扱いやすさ ,  サブリニア ,  複雑性理論

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (2件)： ビッグデータ ,  計算