@techreport{oai:ipsj.ixsq.nii.ac.jp:00220139,
 author = {垣村, 尚徳 and 新田, 陸 and Naonori, Kakimura and Riku, Nitta},
 issue = {1},
 month = {Sep},
 note = {本講演では，データストリーム中の各アイテムの頻度を見積もる問題に対して，省領域の乱択ストリーミングアルゴリズムを提案する．提案アルゴリズムは，確率的数え上げをもちいたカウンターにもとづくアルゴリズムである．???? をアイテムの総数としたとき，???? 個のカウンターをもつ提案アルゴリズムは，1 − ???? 以上の確率で，各アイテムの頻度を相対誤差 (1 + ????) ????/???? 以内で見積もる．このときの空間計算量は???? (???? log log ???? + ???? log (????−1????−1???? ) ) である．, This note studies the problem of estimating frequencies of items over data streams. We propose a simple streaming algorithm for the problem in small space complexity. Our algorithm is a counter-based algorithm with the aid of probabilistic counting. We show that our algorithm with ???? counters computes, with probability at least 1 − ????, the estimation with relative error at most (1 + ????) ????/????, where ???? is the total number of items, taking ???? (???? log log ???? + ???? log (????−1????−1???? ) ) space.},
 title = {ストリーミングデータにおけるアイテム頻出数を求める省領域乱択アルゴリズム},
 year = {2022}
}