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

論文の概要: Daisy Bloom Filters

arxiv url: http://arxiv.org/abs/2205.14894v2
Date: Sun, 16 Jun 2024 15:29:00 GMT
ステータス: 処理完了
システム内更新日: 2024-06-19 13:29:49.589247
Title: Daisy Bloom Filters
Title（参考訳）: デイジーブルームフィルタ
Authors: Ioana O. Bercea, Jakob Bæk Tejs Houen, Rasmus Pagh,
Abstract要約: フィルター(英: filter)とは、ある宇宙から与えられた要素のセット$S$(可算集合)の近似を保存するために広く用いられるデータ構造である。ブルームフィルタを使用する利点は、いくつかの偽陽性が許容されるとき、空間使用量が$S$を正確に保存するために必要なものよりも小さくなることである。 Bloom filter は $textitDaisy Bloom filter$ と呼ばれ、操作を高速に実行し、標準の Bloom filter よりもはるかに少ないスペースを使用する。
参考スコア（独自算出の注目度）: 10.428888893980739
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: A filter is a widely used data structure for storing an approximation of a given set $S$ of elements from some universe $U$ (a countable set).It represents a superset $S'\supseteq S$ that is ''close to $S$'' in the sense that for $x\not\in S$, the probability that $x\in S'$ is bounded by some $\varepsilon > 0$. The advantage of using a Bloom filter, when some false positives are acceptable, is that the space usage becomes smaller than what is required to store $S$ exactly. Though filters are well-understood from a worst-case perspective, it is clear that state-of-the-art constructions may not be close to optimal for particular distributions of data and queries. Suppose, for instance, that some elements are in $S$ with probability close to 1. Then it would make sense to always include them in $S'$, saving space by not having to represent these elements in the filter. Questions like this have been raised in the context of Weighted Bloom filters (Bruck, Gao and Jiang, ISIT 2006) and Bloom filter implementations that make use of access to learned components (Vaidya, Knorr, Mitzenmacher, and Krask, ICLR 2021). In this paper, we present a lower bound for the expected space that such a filter requires. We also show that the lower bound is asymptotically tight by exhibiting a filter construction that executes queries and insertions in worst-case constant time, and has a false positive rate at most $\varepsilon $ with high probability over input sets drawn from a product distribution. We also present a Bloom filter alternative, which we call the $\textit{Daisy Bloom filter}$, that executes operations faster and uses significantly less space than the standard Bloom filter.
Abstract（参考訳）: フィルター(英: filter)とは、ある宇宙から与えられた要素の集合S$(可算集合)の近似を保存するために広く用いられるデータ構造である。スーパーセット $S'\supseteq S$ は ''close to $S$'' であり、$x\not\in S$ の場合、$x\in S'$ の確率は $\varepsilon > 0$ となる。ブルームフィルタを使用する利点は、いくつかの偽陽性が許容されるとき、空間使用量が$S$を正確に保存するために必要なものよりも小さくなることである。フィルタは最悪の場合の観点からよく理解されているが、最先端の構造が特定のデータやクエリの分布に最適に近づいていないことは明らかである。例えば、ある元が 1 に近い確率を持つ$S$ であるとする。すると、それを常に$S'$に含め、フィルタにこれらの要素を表現せずにスペースを節約することは理にかなっている。このような問題は、重み付きブルームフィルタ(Bruck, Gao and Jiang, ISIT 2006)や、学習したコンポーネントへのアクセスを利用するブルームフィルタの実装(Vaidya, Knorr, Mitzenmacher, Krask, ICLR 2021)の文脈で提起されている。本稿では,そのようなフィルタが要求する期待空間の低境界について述べる。また、下界は、最悪のケースでクエリや挿入を行うフィルタ構造を示し、製品分布から引き出された入力集合よりも高い確率で最大$\varepsilon$の偽陽性率を示すことにより、漸近的に厳密であることを示す。また、標準的なBloomフィルタよりもはるかに少ないスペースで操作を高速に実行する、$\textit{Daisy Bloom filter}$というBloomフィルタの代替案も提示します。

関連論文リスト

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)
Compressing (Multidimensional) Learned Bloom Filters [7.6058140480517356]
Bloomフィルタは、要素が基礎となる集合に含まれていないか、あるいは特定のエラー率に含まれていないかを明らかにする。ディープラーニングモデルは、このメンバシップテストの問題を解決するために使用される。学習したブルームフィルタの利点は、膨大なデータを考慮する場合にのみ明らかである。
論文参考訳（メタデータ） (2022-08-05T07:54:48Z)
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)

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

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