2024-03-29T00:51:25Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002037312023-04-27T10:00:04Z01164:02592:10084:10172
データストリームに対する頻出アイテム系列発見のための省メモリアルゴリズムjpnhttp://id.nii.ac.jp/1001/00203636/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=203731&item_no=1&attribute_id=1&file_no=1Copyright (c) 2020 by the Information Processing Society of Japan北海道大学大学院情報科学研究科北海道大学大学院情報科学研究科鳥谷部, 直弥喜田, 拓也本稿では,データストリームに対する頻出アイテム系列問題に取り組む.頻出アイテム系列問題とは,データ中にある閾値より多く出現するアイテム系列の集合を求める問題である.今回,頻出アイテム系列問題の制約を緩和した (ε,l) 近似 φ 頻出アイテム系列問題を定義する.この問題は,求めるアイテム系列の長さの最大値を l とし,入力系列長Nに対して閾値 φN を越えて出現するアイテム系列を出力する.ここで,0<ε<φ<1 であり,出力される集合には (φ-ε)N を超えて出現するアイテム系列を偽陽性の解として含むことを許容する.この問題に対し,ε 近似 φ 頻出アイテム問題を解くアルゴリズム Space saving のアイデアに基づいたアルゴリズム StringSS を提案する.StringSS は,アイテム一つあたりの更新時間がならし O(l) 平均時間,作業領域が O(l/ε) 語空間,各アイテム系列の頻度誤差が εN で動作する.AN1009593X研究報告アルゴリズム(AL)2020-AL-1771182020-03-092188-85662020-02-27