Fugu-MT 論文翻訳(概要): Daisy Bloom Filters

論文の概要: Daisy Bloom Filters

arxiv url: http://arxiv.org/abs/2205.14894v1
Date: Mon, 30 May 2022 07:22:24 GMT
ステータス: 処理完了
システム内更新日: 2022-05-31 18:35:39.395107
Title: Daisy Bloom Filters
Title（参考訳）: デイジーブルームフィルタ
Authors: Ioana O. Bercea, Jakob B{\ae}k Tejs Houen, and Rasmus Pagh
Abstract要約: 重み付きブルームフィルタは、クエリ要素に従ってハッシュ関数の数を調整する。本稿では,$n$要素を独立に挿入するモデルにおいて,パラメータ$k_x$のほぼ最適選択を決定する。我々の上界は情報自明な下界で補われ、デイジーブルームフィルタの空間利用が定数係数までの最良であることを示す。
参考スコア（独自算出の注目度）: 10.867892203887749
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Weighted Bloom filters (Bruck, Gao and Jiang, ISIT 2006) are Bloom filters that adapt the number of hash functions according to the query element. That is, they use a sequence of hash functions $h_1, h_2, \dots$ and insert $x$ by setting the bits in $k_x$ positions $h_1(x), h_2(x), \dots, h_{k_x}(x)$ to 1, where the parameter $k_x$ depends on $x$. Similarly, a query for $x$ checks whether the bits at positions $h_1(x), h_2(x), \dots, h_{k_x}(x)$ contain a $0$ (in which case we know that $x$ was not inserted), or contains only $1$s (in which case $x$ may have been inserted, but it could also be a false positive). In this paper, we determine a near-optimal choice of the parameters $k_x$ in a model where $n$ elements are inserted independently from a probability distribution $\mathcal{P}$ and query elements are chosen from a probability distribution $\mathcal{Q}$, under a bound on the false positive probability $F$. In contrast, the parameter choice of Bruck et al., as well as follow-up work by Wang et al., does not guarantee a nontrivial bound on the false positive rate. We refer to our parameterization of the weighted Bloom filter as a $\textit{Daisy Bloom filter}$. For many distributions $\mathcal{P}$ and $\mathcal{Q}$, the Daisy Bloom filter space usage is significantly smaller than that of Standard Bloom filters. Our upper bound is complemented with an information-theoretical lower bound, showing that (with mild restrictions on the distributions $\mathcal{P}$ and $\mathcal{Q}$), the space usage of Daisy Bloom filters is the best possible up to a constant factor. Daisy Bloom filters can be seen as a fine-grained variant of a recent data structure of Vaidya, Knorr, Mitzenmacher and Kraska. Like their work, we are motivated by settings in which we have prior knowledge of the workload of the filter, possibly in the form of advice from a machine learning algorithm.
Abstract（参考訳）: 重み付きブルームフィルタ(Bruck, Gao, Jiang, ISIT 2006)は、クエリ要素に応じてハッシュ関数の数を調整するブルームフィルタである。すなわち、ハッシュ関数 $h_1, h_2, \dots$ の列を使い、$k_x$ の位置 $h_1(x), h_2(x), \dots, h_{k_x}(x)$ to 1 でビットを設定することで $x$ を挿入する。同様に、$x$ のクエリは、位置 $h_1(x), h_2(x), \dots, h_{k_x}(x)$ のビットが$0$($x$が挿入されていないことを知っている場合)、または$1$s($x$が挿入されているかもしれないが、偽陽性である場合もある)を含むかどうかをチェックする。本稿では,n$要素が確率分布$\mathcal{P}$から独立に挿入され,クエリ要素が確率分布$\mathcal{Q}$から選択されるモデルにおいて,偽陽性確率$F$のバウンダリの下でパラメータ$k_x$のほぼ最適選択を決定する。対照的に、Bruck et al. のパラメータ選択と Wang et al. のフォローアップ作業は、偽陽性率の非自明な境界を保証しない。重み付きブルームフィルタのパラメータ化を $\textit{Daisy Bloom filter}$ と呼ぶ。多くの分布に対して $\mathcal{P}$ と $\mathcal{Q}$ は、ダイジーブルームフィルタ空間の使用量は標準ブルームフィルタのそれよりもかなり小さい。私たちの上界は情報理論上の下界で補われており、($\mathcal{p}$ と $\mathcal{q}$ の分布に対する軽度な制限により)デイジー・ブルームフィルターの空間的利用は定数係数まで可能な最良であることを示している。デイジーブルームフィルタは、ヴァイディヤ、クノール、ミッツェンマッハ、クラスカの最近のデータ構造のきめ細かい変種と見なすことができる。彼らの仕事と同じように、私たちはフィルターのワークロードについて、おそらくは機械学習アルゴリズムからのアドバイスの形で事前に知っている設定によって動機付けられています。

関連論文リスト

Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity [3.9657575162895196]
曖昧な部分空間の埋め込みは、ランダムな$mtimes n$ matrix $Pi$で、その部分空間内のすべてのベクトルのノルムを1pmepsilon$ factorで保存する。最適次元が $m=Theta(d/epsilon2)$ で、最適間隔が $tilde O (1/epsilon)$ のとき、非零エントリは $Pi$ である。
論文参考訳（メタデータ） (2024-11-13T16:58:51Z)
Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
論文参考訳（メタデータ） (2024-07-18T15:58:04Z)
Group-invariant max filtering [4.396860522241306]
我々は$G$-不変実数値関数の族を$V$上に構築し、最大フィルタと呼ぶ。 V=mathbbRd$ と $G$ が有限の場合、適切な最大フィルタバンクは軌道を分離し、商計量においてビリプシッツである。
論文参考訳（メタデータ） (2022-05-27T15:18:08Z)
One-Sided Box Filter for Edge Preserving Image Smoothing [9.67565473617028]
信号の平滑化はできるが,信号に不連続な特徴を保持する一方的なボックスフィルタを提案する。より具体的には、8つの片側ウィンドウでボックスフィルタを実行し、片側ボックスフィルタでコーナーとエッジを保存します。
論文参考訳（メタデータ） (2021-08-11T04:22:38Z)
Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文参考訳（メタデータ） (2021-05-31T16:10:49Z)
Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文参考訳（メタデータ） (2021-05-17T16:40:48Z)
Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
論文参考訳（メタデータ） (2020-11-02T14:59:39Z)
Data Agnostic Filter Gating for Efficient Deep Networks [72.4615632234314]
現在のフィルタプルーニング法は主に特徴写像を利用してフィルタの重要なスコアを生成し、より小さなスコアのプルーンを生成する。本稿では,Daggerモジュールと呼ばれる補助的ネットワークを用いてプルーニングを誘導するデータフィルタプルーニング手法を提案する。さらに,特定のFLOP制約でプルーネフィルタを支援するために,明示的なFLOPを意識した正規化を活用して,プルーニングフィルタを直接対象のFLOPに向けて推進する。
論文参考訳（メタデータ） (2020-10-28T15:26:40Z)
Pruning Filter in Filter [38.6403556260338]
プルーニングは、現代のニューラルネットワークを圧縮し、加速する非常に強力で効果的な技術になっている。従来のフィルタプルーニング法よりもきめ細かな粒度を実現するため,フィルタ内のフィルタをプルークする手法を提案する。 SWPは従来のFP法よりも有効であることを示し,CIFAR-10とImageNetデータセットの最先端プルーニング比を実現する。
論文参考訳（メタデータ） (2020-09-30T03:35:16Z)
Filter Grafting for Deep Neural Networks: Reason, Method, and Cultivation [86.91324735966766]
フィルタは現代の畳み込みニューラルネットワーク(CNN)のキーコンポーネントである本稿では,この目的を達成するためにフィルタグラフト(textbfMethod)を導入する。我々は,フィルタの情報を測定するための新しい基準と,グラフトされた情報をネットワーク間でバランスをとるための適応重み付け戦略を開発する。
論文参考訳（メタデータ） (2020-04-26T08:36:26Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文参考訳（メタデータ） (2020-02-17T18:41:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。