論文の概要: On the LSH Distortion of Ulam and Cayley Similarities
- arxiv url: http://arxiv.org/abs/2605.11921v1
- Date: Tue, 12 May 2026 10:36:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-13 21:48:56.799264
- Title: On the LSH Distortion of Ulam and Cayley Similarities
- Title（参考訳）: ウラムのLSH歪みとケイリー類似性について
- Authors: Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Erasmo Tani,
- Abstract要約: 局所性感受性ハッシュ(LSH)は基本的なプリミティブとして広く利用されている。
LSH歪みは、類似性関数がLSHスキームを持つことを乗法的にクローズする方法を測定する。
ウラム類似性は、$O(n / sqrtlog n)$の線形LSH歪みを許容し、最高のLSH歪みを達成可能な$(n0.12)$の低い境界も証明する。
- 参考スコア（独自算出の注目度）: 11.5709847167898
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Locality-sensitive hashing (LSH) has found widespread use as a fundamental primitive, particularly to accelerate nearest neighbor search. An LSH scheme for a similarity function $S:\mathcal{X} \times \mathcal{X} \to [0,1]$ is a distribution over hash functions on $\mathcal{X}$ with the property that the probability of collision of any two elements $x,y\in \mathcal{X}$ is exactly equal to $S(x,y)$. However, not all similarity functions admit exact LSH schemes. The notion of LSH distortion measures how multiplicatively close a similarity function is to having an LSH scheme. In this work, we study the LSH distortion of the Ulam and Cayley similarities, which are popular similarity measures on permutations of $n$ elements. We show that the Ulam similarity admits a sublinear LSH distortion of $O(n / \sqrt{\log n})$; we also prove a lower bound of $Ω(n^{0.12})$ on the best LSH distortion achievable. On the other hand, we show that the LSH distortion of the Cayley similarity is $Θ(n)$.
- Abstract（参考訳）: 局所性に敏感なハッシュ (LSH) は、特に近接探索を加速するために、基本的なプリミティブとして広く利用されている。
類似関数 $S:\mathcal{X} \times \mathcal{X} \to [0,1]$ に対する LSH スキームは、任意の二つの元 $x,y\in \mathcal{X}$ の衝突確率がちょうど$S(x,y)$ であるという性質を持つ、$\mathcal{X}$ 上のハッシュ関数上の分布である。
しかし、すべての類似性関数は正確な LSH スキームを許容するわけではない。
LSH歪みの概念は、LSHスキームを持つことに類似性関数を乗法的に閉化する方法を測定する。
本研究では,Ulam と Cayley の類似点の LSH 歪みについて検討する。
ウラム類似性は、$O(n / \sqrt{\log n})$の線型LSH歪みを許容することを示し、また、最高のLSH歪みが達成可能な$Ω(n^{0.12})$の低い境界も証明する。
一方、ケイリー類似性のLSH歪みは、$(n)$であることを示す。
関連論文リスト
- Online Realizable Regression and Applications for ReLU Networks [14.292982828097465]
近似三角形の不等式を満たす損失(擬似測度)下での対向モデルにおける実現可能なオンライン回帰について検討する。
我々の主な貢献は、具体的なダドリー型エントロピー積分により、$mathbbD_mathrmonl$を上界とする一般ポテンシャル法である。
論文 参考訳（メタデータ） (2026-02-22T13:02:25Z) - Rényi divergence-based uniformity guarantees for $k$-universal hash functions [53.80737717363129]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
本稿では,MNL関数近似を用いたMDPの新たなクラスについて検討し,状態空間上の確率分布の正当性を保証する。
その大きな利点にもかかわらず、非線形関数を組み込むことは、統計的および計算効率の両方において重大な課題を提起する。
我々は,$widetildemathcalO(dH2sqrtK + kappa-1d2H2)$を後悔するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-27T11:31:54Z) - Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss [33.18537822803389]
L2$ と $Psi_p$ の位相が我々の仮説クラス $mathscrF$, $mathscrF$ に同値であるときにいつでも、$mathscrF$ は弱準ガウス類であることを示す。
以上の結果から, 混合への直接的な依存は高次項に還元されるため, この問題は実現可能か否かを判断できる。
論文 参考訳（メタデータ） (2024-02-08T18:57:42Z) - Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文 参考訳（メタデータ） (2023-02-27T16:34:21Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Cascading Bandit under Differential Privacy [21.936577816668944]
本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。
DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。
Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
論文 参考訳（メタデータ） (2021-05-24T07:19:01Z) - Locality-sensitive hashing in function spaces [6.316693022958221]
我々は、$mathbbRN$上のLSH関数を$Lp$空間に拡張できる2つの方法を提案する。
提示されたハッシュスキームを用いて、1次元連続確率分布上のワッサーシュタイン距離のLSH族を構成する。
論文 参考訳（メタデータ） (2020-02-10T16:16:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。