論文の概要: DartMinHash: Fast Sketching for Weighted Sets
- arxiv url: http://arxiv.org/abs/2005.11547v1
- Date: Sat, 23 May 2020 14:59:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-30 03:53:48.543488
- Title: DartMinHash: Fast Sketching for Weighted Sets
- Title（参考訳）: DartMinHash: 軽量セットの高速スケッチ
- Authors: Tobias Christiani
- Abstract要約: 重み付きハッシュは、類似性探索や大規模カーネルマシンに応用した標準的な次元削減手法である。
mathbbR_geq 0d$の重み付き集合を$xとし、期待時間に$k$独立ミンハッシュを計算する単純なアルゴリズムを導入する。
- 参考スコア（独自算出の注目度）: 0.5584060970507505
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Weighted minwise hashing is a standard dimensionality reduction technique
with applications to similarity search and large-scale kernel machines. We
introduce a simple algorithm that takes a weighted set $x \in \mathbb{R}_{\geq
0}^{d}$ and computes $k$ independent minhashes in expected time $O(k \log k +
\Vert x \Vert_{0}\log( \Vert x \Vert_1 + 1/\Vert x \Vert_1))$, improving upon
the state-of-the-art BagMinHash algorithm (KDD '18) and representing the
fastest weighted minhash algorithm for sparse data. Our experiments show
running times that scale better with $k$ and $\Vert x \Vert_0$ compared to ICWS
(ICDM '10) and BagMinhash, obtaining $10$x speedups in common use cases. Our
approach also gives rise to a technique for computing fully independent
locality-sensitive hash values for $(L, K)$-parameterized approximate near
neighbor search under weighted Jaccard similarity in optimal expected time
$O(LK + \Vert x \Vert_0)$, improving on prior work even in the case of
unweighted sets.
- Abstract（参考訳）: 重み付きハッシュは、類似性探索や大規模カーネルマシンに応用した標準的な次元削減手法である。
重み付き集合 $x \in \mathbb{r}_{\geq 0}^{d}$ をとり、期待時間$o(k \log k + \vert x \vert_{0}\log( \vert x \vert_1 + 1/\vert x \vert_1))$ を計算し、最先端のbagminhashアルゴリズム(kdd '18)に基づいて改善し、スパースデータに対する最速の重み付きminhashアルゴリズムを表す単純なアルゴリズムを導入する。
ICWS (ICDM '10) や BagMinhash と比較して,$k$ と $\Vert x \Vert_0$ でスケールした実行時間は,一般的なユースケースでは 10$x のスピードアップが得られる。
提案手法は, ジャカルド類似性により, 最大期待時間$O(LK + \Vert x \Vert_0)$の近傍探索に対して, 完全独立局所性感性ハッシュ値を$(L, K)$パラメータ化して計算し, 未加重集合においても先行処理を改善する手法である。
関連論文リスト
- Mini-Batch Kernel $k$-means [4.604003661048267]
私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。
実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
論文 参考訳（メタデータ） (2024-10-08T10:59:14Z) - Faster Private Minimum Spanning Trees [11.72102598708538]
本稿では,時間内で動作中の既存手法の実用性に適合する新しい差分プライベートMSTアルゴリズムを提案する。
我々は,少なくとも$O(n2)$カットエッジを$O(sqrtn log n)$ timeでサンプリングすることのできるデータ構造を示す。
論文 参考訳（メタデータ） (2024-08-13T16:00:30Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Minwise-Independent Permutations with Insertion and Deletion of Features [0.07252027234425332]
Broder textitet. al.citepBroderCFM98は、バイナリデータの低次元スケッチを計算する$mathrmminHash$アルゴリズムを導入している。
アルゴリズムの厳密な理論的解析を行い、実世界の複数のデータセットに関する広範な実験を補完する。
論文 参考訳（メタデータ） (2023-08-22T07:27:45Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - 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) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。