ストリーミングデータにおけるアイテム頻出数を求める省領域乱択アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2022-09-08
• タイトル: ストリーミングデータにおけるアイテム頻出数を求める省領域乱択アルゴリズム
• タイトル / 言語: en
• タイトル: Randomized Counter-Based Algorithms for Frequency Estimation over Data Streams in ????(log log ????) space
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 慶應義塾大学理工学部
• 著者所属: 日本IBM
• 著者所属(英): en
• 著者所属(英): Department of Mathematics, Faculty of Science and Technology, Keio University
• 著者所属(英): en
• 著者所属(英): IBM Japan
• 著者名: 垣村, 尚徳; 新田, 陸
• 著者名(英): Naonori, Kakimura; Riku, Nitta
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本講演では，データストリーム中の各アイテムの頻度を見積もる問題に対して，省領域の乱択ストリーミングアルゴリズムを提案する．提案アルゴリズムは，確率的数え上げをもちいたカウンターにもとづくアルゴリズムである．???? をアイテムの総数としたとき，???? 個のカウンターをもつ提案アルゴリズムは，1 − ???? 以上の確率で，各アイテムの頻度を相対誤差 (1 + ????) ????/???? 以内で見積もる．このときの空間計算量は???? (???? log log ???? + ???? log (????−1????−1???? ) ) である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-189, 号 1, p. 1-2, 発行日 2022-09-08
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会