文献

J-GLOBAL ID：202002269474683056   整理番号：20A0148292

ワイルドカードを用いたデータストリームにおける周期性【JST・京大機械翻訳】

Periodicity in Data Streams with Wildcards

著者 (5件)： Erguen Funda (School of Informatics and Computing, Indiana University, Bloomington, IN, USA) ,  Grigorescu Elena (Department of Computer Science, Purdue University, West Lafayette, IN, USA) ,  Sadeqi Azer Erfan (School of Informatics and Computing, Indiana University, Bloomington, IN, USA) ,  Zhou Samson (School of Informatics and Computing, Indiana University, Bloomington, IN, USA) ,  Zhou Samson (Department of Computer Science, Purdue University, West Lafayette, IN, USA)
資料名： Theory of Computing Systems  (Theory of Computing Systems)
巻： 64  号： 1  ページ： 177-197  発行年： 2020年 
JST資料番号： D0592A  ISSN： 1432-4350  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 長さnのストリングS内の周期的傾向を検出する問題を調べ,k=o(n)のほとんどのk野生カード特性を含むストリーミングモデルに到達した。野生カード文字は,他の文字を割り当てることができる特殊な文字である。著者らは,結果として得られたストリームにおいて,長さn-pのプレフィックスが長さn-pの接尾suffに等しいように,Sが野生カード特性の各々に割り当てられるならば,Sは野生周期pを持つことを示した。著者らは,空間の[数式:原文を参照]ビットを用いてSの野心周期を計算する2パスストリーミングアルゴリズムを提示し,一方,著者らは,この問題が1パスの部分線形空間において解決できないことも示した。また,[数式:原文を参照]空間を用いてSの最後のpシンボルに現れる[数式:原文を参照]によりSのすべての野生型周期pを計算し,野生カード特性を持たない1パスランダム化ストリーミングアルゴリズムを与えた。Copyright 2019 Springer Science+Business Media, LLC, part of Springer Nature Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 野生型 ,  *ストリーミング ,  アルゴリズム ,  ベクトル空間
準シソーラス用語： ストリーミングアルゴリズム ,  プレフィックス ,  データストリーム , 【Automatic Indexing@JST】

著者キーワード (5件)： ストリーミングアルゴリズム ,  周期性 ,  野生カード ,  ランダム化アルゴリズム ,  ストリングアルゴリズム

分類 (2件)： システム・制御理論一般  (IA02010H) ,  システム設計・解析  (IA02030D)

タイトルに関連する用語 (2件)： データストリーム ,  周期性