| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-05-26 14:15 Some extensions of DLT priority sampling -- Covariance and Sliding Window -- Takashi Sugimori（Algosystem）・○Yoshinori Takei（Nagaoka Univ. of Tech.）  COMP2009-14 |
|
| 抄録 | （和） | Duffield, Lund, Thorup が提案した優先サンプリングは、 $n$ アイテムからなる 重み付きの大きなストリームの任意の部分集合の重みを、限られた数$k$ 個のサンプルだけから推定する。この手法は同じサンプル数$k$の 手法の中で推定量の分散の合計の意味で準最適であることが、Szegedy により 示されている。本報告では、優先サンプリングの二つの拡張を与える。 まず、ベクトルで重み付けられたストリームに対するサンプリング手法を 与える。これは、ある準最適性を満たす。この手法の応用として、 一つのアイテムに関連づけられた２種類の重みの共分散を推定する優先サンプリング を与える。そして、最近のある一定数のアイテムからなるスライディング窓の中の 任意の重み部分和を推定する変形された優先サンプリングを与える。これら提案手法に 対して実験的解析を行う。 |
| （英） | The priority sampling scheme, proposed by Duffield, Lund, and Thorup, estimates the weight of an arbitrary subset of a large weighted stream of $n$ items, using only a limited number $k$ of samples. Szegedy showed that the scheme is almost optimal in terms of the total variance of the estimators among schemes of the same sample size $k$. In this report, we present two extensions of priority sampling. First, we present a sampling scheme for a vector weighted stream, which satisfies some near-optimality. As an application of the scheme, we present a priority sampling scheme to estimate the covariance of two kinds of weights associated to an item. Then we present a modified version of priority sampling that estimates an arbitrary subset sum of weights in the sliding window, a set of recent items of a fixed size. We analyze the proposed schemes experimentally. |
|
| キーワード | （和） | ストリームアルゴリズム / 貯蔵庫サンプリング / 分散 / / / / / |
| （英） | stream algorithms / reservoir sampling / variance / / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 54, COMP2009-14, pp. 31-38, 2009年5月. | |
| 資料番号 | COMP2009-14 | |
| 発行日 | 2009-05-19 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2009-14 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2009-05-26 - 2009-05-26 |
| 開催地（和） | 埼玉大学 |
| 開催地（英） | Saitama Univ. |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2009-05-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Some extensions of DLT priority sampling |
| サブタイトル（英） | Covariance and Sliding Window |
| キーワード(1)（和/英） | ストリームアルゴリズム / stream algorithms |
| キーワード(2)（和/英） | 貯蔵庫サンプリング / reservoir sampling |
| キーワード(3)（和/英） | 分散 / variance |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 杉森 隆司 / Takashi Sugimori / スギモリ タカシ |
| 第1著者 所属（和/英） | アルゴシステム (略称： アルゴシステム) Algosystem (略称： Algosystem) |
| 第2著者 氏名（和/英/ヨミ） | 武井 由智 / Yoshinori Takei / タケイ ヨシノリ |
| 第2著者 所属（和/英） | 長岡技術科学大学 (略称： 長岡技科大) Nagaoka University of Technology (略称： Nagaoka Univ. of Tech.) |
| 講演者 | 第2著者 |
| 発表日時 | 2009-05-26 14:15:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2009-14 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.54 |
| ページ範囲 | pp.31-38 |
| ページ数 | 8 |
| 発行日 | 2009-05-19 (COMP) |
[研究会発表申込システムのトップページに戻る]