制御-変分法を用いたTug-of-Warsketchの改良【JST・京大機械翻訳】

Pratap Rameshwar; Verma Bhisham Dev; Kulkarni Raghav

プレプリント

J-GLOBAL ID：202202210582100305 整理番号：22P0299082

制御-変分法を用いたTug-of-Warsketchの改良【JST・京大機械翻訳】

Improving \textit{Tug-of-War} sketch using Control-Variates method

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2022年03月04日プレプリントサーバーでの情報更新日： 2022年03月04日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

大規模データの計算空間効率的要約,即ち,大データのスケッチは,ストリーミングアルゴリズムにおける中心問題である。そのようなスケッチを用いて,いくつかのデータ分析タスクにおける事後クエリを回答した。スケッチを計算するためのアルゴリズムは,通常,高速,正確,および空間効率を必要とする。ストリーミングアルゴリズムフレームワークにおける基本的問題は,データストリームの周波数モーメントを計算することである。タイプiのf_i要素を含むシーケンスの周波数モーメントは,i≡[n]のF_k=Σ_i=1 ̄nf_i ̄kである。これは周波数ベクトル(f_1,f_2,.f_n)のl_kノルムとも呼ばれる。もう一つの重要な問題は,対応する周波数ベクトルの内積を計算することによって,2つのデータストリームの間の類似性を計算することである。Alon,MatiasおよびSzegedy ̄cite{AMS},a.k.a.戦争(またはAMS)スケッチは,周波数モーメントを計算するためのランダム化サブ線形空間(および線形時間)アルゴリズム,およびデータストリームに対応する2つの周波数ベクトルの間の内積を与える。しかし,これらの推定値の分散は典型的に大きい傾向がある。本研究では,これらの推定の分散を最小化することに焦点を当てた。著者らは,モンテカルロシミュレーションにおける分散低減のために主に知られている古典的制御-Variate法(Lavenberg)から技術を使用し,その結果,わずかな計算オーバヘッドのコストで,大きな分散低減を得ることができた。本提案の理論解析を提示し,合成および実世界データセットに関する支援実験により補完した。【JST・京大機械翻訳】

, , , , , ,
, , , , , , , , 【Automatic Indexing@JST】

計算理論 , データ保護 , データベースシステム , 半導体集積回路 , 数値計算

前のページに戻る