論文の概要: Minwise-Independent Permutations with Insertion and Deletion of Features
- arxiv url: http://arxiv.org/abs/2308.11240v1
- Date: Tue, 22 Aug 2023 07:27:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-23 13:35:36.307283
- Title: Minwise-Independent Permutations with Insertion and Deletion of Features
- Title（参考訳）: 特徴の挿入と削除を伴うマイナー非依存的な置換
- Authors: Rameshwar Pratap and Raghav Kulkarni
- Abstract要約: Broder textitet. al.citepBroderCFM98は、バイナリデータの低次元スケッチを計算する$mathrmminHash$アルゴリズムを導入している。
アルゴリズムの厳密な理論的解析を行い、実世界の複数のデータセットに関する広範な実験を補完する。
- 参考スコア（独自算出の注目度）: 0.07252027234425332
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In their seminal work, Broder \textit{et. al.}~\citep{BroderCFM98} introduces
the $\mathrm{minHash}$ algorithm that computes a low-dimensional sketch of
high-dimensional binary data that closely approximates pairwise Jaccard
similarity. Since its invention, $\mathrm{minHash}$ has been commonly used by
practitioners in various big data applications. Further, the data is dynamic in
many real-life scenarios, and their feature sets evolve over time. We consider
the case when features are dynamically inserted and deleted in the dataset. We
note that a naive solution to this problem is to repeatedly recompute
$\mathrm{minHash}$ with respect to the updated dimension. However, this is an
expensive task as it requires generating fresh random permutations. To the best
of our knowledge, no systematic study of $\mathrm{minHash}$ is recorded in the
context of dynamic insertion and deletion of features. In this work, we
initiate this study and suggest algorithms that make the $\mathrm{minHash}$
sketches adaptable to the dynamic insertion and deletion of features. We show a
rigorous theoretical analysis of our algorithms and complement it with
extensive experiments on several real-world datasets. Empirically we observe a
significant speed-up in the running time while simultaneously offering
comparable performance with respect to running $\mathrm{minHash}$ from scratch.
Our proposal is efficient, accurate, and easy to implement in practice.
- Abstract（参考訳）: 独創的な著作では、broder \textit{et。
アル
}~\citep{brodercfm98} は$\mathrm{minhash}$アルゴリズムを導入し、ペアワイズジャッカーの類似性に密接に近い高次元バイナリデータの低次元スケッチを計算する。
その発明以来、$\mathrm{minhash}$は様々なビッグデータアプリケーションで実践者が一般的に使用してきた。
さらに、データは現実のシナリオの多くで動的であり、その機能セットは時間とともに進化します。
この機能がデータセットに動的に挿入され、削除される場合を考える。
この問題に対するナイーブな解決策は、更新された次元に関して繰り返し$\mathrm{minhash}$を再計算することである。
しかし、新しいランダムな置換を生成する必要があるため、これは高価なタスクである。
我々の知る限りでは、$\mathrm{minHash}$の体系的な研究は、機能の動的挿入と削除という文脈で記録されていない。
本研究では,この研究を開始し,特徴の動的挿入と削除に適応する$\mathrm{minHash}$スケッチを実現するアルゴリズムを提案する。
アルゴリズムの厳密な理論的解析を行い、実世界の複数のデータセットに関する広範な実験を補完する。
経験的に、実行時の大幅なスピードアップを観察しながら、スクラッチから$\mathrm{minHash}$の実行に対して同等のパフォーマンスを提供する。
私たちの提案は効率的で正確で、実践が容易です。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - Pb-Hash: Partitioned b-bit Hashing [21.607059258448594]
我々は、$B$ビットを$m$チャンク、例えば$btimes m =B$に分割することでハッシュを再使用することを提案する。
我々の理論的分析により、ハッシュ値を$m$チャンクに分割することで、精度が低下することが明らかとなった。
一部のリージョンでは、Pb-Hashは4.9ドルよりもずっと大きい$m$でもうまく機能している。
論文 参考訳（メタデータ） (2023-06-28T06:05:47Z) - Adaptive and Dynamic Multi-Resolution Hashing for Pairwise Summations [19.602149096819776]
本稿では,適応的で動的なマルチレゾリューションハッシュデータ構造であるAdam-Hashを提案する。
提案したAdam-Hash は適応型 PSE クエリにも頑健であり,従来のクエリの出力に応じて mathbbRd$ のクエリ $q_j を選択することができる。
論文 参考訳（メタデータ） (2022-12-21T23:23:24Z) - Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。
これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。
我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
論文 参考訳（メタデータ） (2022-07-26T04:38:47Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Nearly Minimax Algorithms for Linear Bandits with Shared Representation [86.79657561369397]
我々は、次元が$d$で、それぞれ$T$のラウンドで$M$リニアバンディットをプレイする設定を考え、これらの$M$リニアバンディットタスクは共通の$k(ll d)$次元リニア表現を共有する。
我々は$widetildeOleft(dsqrtkMT + kMsqrtTright)$ regret boundsを達成する新しいアルゴリズムを考案した。
論文 参考訳（メタデータ） (2022-03-29T15:27:13Z) - C-MinHash: Rigorously Reducing $K$ Permutations to Two [25.356048456005023]
MinHash (Minwise hashing) は、大量のバイナリ (0/1) データにおける Jaccard (resemblance) の類似性を近似するために、ランダムハッシュを生成するための重要かつ実用的なアルゴリズムである。
我々は、bf Circulant MinHash (C-MinHash)を提案する。
論文 参考訳（メタデータ） (2021-09-07T21:06:33Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - An Efficient $k$-modes Algorithm for Clustering Categorical Datasets [8.528384027684194]
我々は, OTQT と呼ばれる$k$-modes の斬新で効率的な実装を提供する。
OTQTは既存の$k$-modesアルゴリズムでは検出不可能な目的関数を改善するために更新されていることを証明している。
OTQTはイテレーション毎に常に正確で、最終最適化までほぼ常に高速である(一部のデータセットではわずかに遅い)。
論文 参考訳（メタデータ） (2020-06-06T18:41:36Z) - DartMinHash: Fast Sketching for Weighted Sets [0.5584060970507505]
重み付きハッシュは、類似性探索や大規模カーネルマシンに応用した標準的な次元削減手法である。
mathbbR_geq 0d$の重み付き集合を$xとし、期待時間に$k$独立ミンハッシュを計算する単純なアルゴリズムを導入する。
論文 参考訳（メタデータ） (2020-05-23T14:59:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。