論文の概要: 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}$ の分布に対する軽度な制限により)デイジー・ブルームフィルターの空間的利用は定数係数まで可能な最良であることを示している。
デイジーブルームフィルタは、ヴァイディヤ、クノール、ミッツェンマッハ、クラスカの最近のデータ構造のきめ細かい変種と見なすことができる。
彼らの仕事と同じように、私たちはフィルターのワークロードについて、おそらくは機械学習アルゴリズムからのアドバイスの形で事前に知っている設定によって動機付けられています。
関連論文リスト
- Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity [8.100854060749212]
本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
論文 参考訳(メタデータ) (2023-12-09T19:22:10Z) - Testing Dependency of Unlabeled Databases [5.384630221560811]
2つのランダムデータベース $mathsfXinmathcalXntimes d$ と $mathsfYinmathcalYntimes d$ は統計的に依存するかどうかによって異なる。
最適テストが情報理論上不可能かつ可能なしきい値の特徴付けを行う。
論文 参考訳(メタデータ) (2023-11-10T05:17:03Z) - Noisy Computing of the $\mathsf{OR}$ and $\mathsf{MAX}$ Functions [22.847963422230155]
ノイズの多いクエリを使って$n$変数の関数を計算することの問題を考察する。
我々は, [ (1 pm o(1)) fracnlog frac1deltaD_mathsfKL(p | 1-p) ] のクエリ数が十分であり,両関数の計算に必要であることを示す。
論文 参考訳(メタデータ) (2023-09-07T19:37:52Z) - Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。
この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
論文 参考訳(メタデータ) (2023-02-07T10:39:44Z) - On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
カーネル群に基づく暗黙の空間性誘導機構について述べる。
アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
論文 参考訳(メタデータ) (2021-10-12T09:36:41Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳(メタデータ) (2021-09-06T14:21:43Z) - 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) - On Avoiding the Union Bound When Answering Multiple Differentially
Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。
一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文 参考訳(メタデータ) (2020-12-16T17:58:45Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。