| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-03-18 10:20 ストリームに対するO(log log n)領域を用いたReservoir sampling ○園田尚人・山内由紀子・来嶋秀治・山下雅史（九大）  COMP2012-53 |
|
| 抄録 | （和） | 本論文ではストリーム中の要素を一様ランダムにサンプルするための簡単なアルゴリズムを提案する．本アルゴリズムは，未知の入力サイズn について，O(log log n)bit の領域のみを用いてリゾーバサンプリングできるものである．そのアイデアは，緒方ら[4] が提案したベルヌーイサンプリングアルゴリズムに基づいている．緒方らのアルゴリズムはO(log log n)bit の領域のみを用いて，一様ランダムなサンプリングを行うことができるが，定数個のサンプルを取り出すということは不可能であった．一方で，我々のアルゴリズムではちょうどc 個のサンプルを出力することができる．また，本サンプルを用いた，頻度の差を推定するための乱択近似アルゴリズムも提案する． |
| （英） | This paper presents a simple algorithm for uniform sampling of elements in a stream; that is for reservoir sampling uses memory of O(loglogn)bits for an input stream with length n, without knowing an approximate value of n in advance. The idea of our algorithm is based on the Bernoulli sampling algorithm by Ogata et al (2011). Ogata ’s algorithm samples uniformly using memory of O(loglogn)bits, but the number of samples is not fixed. On the other hand, our algorithm outputs exactly c elements for samples of the stream. Using this algorithm, we present a randomized approximation algorithm for the difference of the frequency of elements between streams. | |
| キーワード | （和） | リゾーバサンプリング / 空間複雑性 / ストリーミングアルゴリズム / 頻度の差 / 乱択近似アルゴリズム / / / |
| （英） | reservoir sampling / space complexity / streaming algorithm / difference of frequency / randomize approximation algorithm / / / | |
| 文献情報 | 信学技報, vol. 112, no. 498, COMP2012-53, pp. 5-12, 2013年3月. | |
| 資料番号 | COMP2012-53 | |
| 発行日 | 2013-03-11 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2012-53 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2013-03-18 - 2013-03-18 |
| 開催地（和） | 岐阜大学 |
| 開催地（英） | Gifu University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2013-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | ストリームに対するO(log log n)領域を用いたReservoir sampling |
| サブタイトル（和） | |
| タイトル（英） | Reservoir sampling in stream using O(log log n) space |
| サブタイトル（英） | |
| キーワード(1)（和/英） | リゾーバサンプリング / reservoir sampling |
| キーワード(2)（和/英） | 空間複雑性 / space complexity |
| キーワード(3)（和/英） | ストリーミングアルゴリズム / streaming algorithm |
| キーワード(4)（和/英） | 頻度の差 / difference of frequency |
| キーワード(5)（和/英） | 乱択近似アルゴリズム / randomize approximation algorithm |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 園田 尚人 / Naoto Sonoda / ソノダ ナオト |
| 第1著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山内 由紀子 / Yukiko Yamauchi / ヤマウチ ユキコ |
| 第2著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 来嶋 秀治 / Shuji Kijima / キジマ シュウジ |
| 第3著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 山下 雅史 / Masafumi Yamashita / ヤマシタ マサフミ |
| 第4著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-03-18 10:20:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2012-53 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.498 |
| ページ範囲 | pp.5-12 |
| ページ数 | 8 |
| 発行日 | 2013-03-11 (COMP) |
[研究会発表申込システムのトップページに戻る]