論文の概要: Efficient Set of Vectors Search

• arxiv url: http://arxiv.org/abs/2107.06817v1
• Date: Wed, 14 Jul 2021 16:22:20 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-15 14:10:05.722494
• Title: Efficient Set of Vectors Search
• Title（参考訳）: 効率的なベクトル探索
• Authors: Michael Leybovich and Oded Shmueli
• Abstract要約: 一般事例に対する近似探索アルゴリズムを提案する。 これらのアルゴリズムの根底にある考え方は、一組のベクトルを「長い」単一ベクトルで符号化することである。
• 参考スコア（独自算出の注目度）: 2.741266294612776
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider a similarity measure between two sets $A$ and $B$ of vectors, that balances the average and maximum cosine distance between pairs of vectors, one from set $A$ and one from set $B$. As a motivation for this measure, we present lineage tracking in a database. To practically realize this measure, we need an approximate search algorithm that given a set of vectors $A$ and sets of vectors $B_1,...,B_n$, the algorithm quickly locates the set $B_i$ that maximizes the similarity measure. For the case where all sets are singleton sets, essentially each is a single vector, there are known efficient approximate search algorithms, e.g., approximated versions of tree search algorithms, locality-sensitive hashing (LSH), vector quantization (VQ) and proximity graph algorithms. In this work, we present approximate search algorithms for the general case. The underlying idea in these algorithms is encoding a set of vectors via a "long" single vector.
• Abstract（参考訳）: ベクトルのペアの平均と最大コサイン距離をバランスさせる2つの集合 $A$ と $B$ の類似度測度を考え、その1つは集合 $A$ と 1 は集合 $B$ から。 この尺度の動機として,データベース上での系統追跡を提案する。 この測度を実際に実現するためには、ベクトルの集合A$とベクトルの集合B_1,...,B_n$を与えられた近似探索アルゴリズムが必要である。 すべての集合がシングルトン集合である場合、基本的には1つのベクトルであり、木探索アルゴリズムの近似バージョン、局所性感受性ハッシュ(LSH)、ベクトル量子化(VQ)、近接グラフアルゴリズムなどの効率的な近似探索アルゴリズムが存在する。 本研究では,一般事例に対する近似探索アルゴリズムを提案する。 これらのアルゴリズムの根底にある考え方は、一組のベクトルを「長い」単一ベクトルで符号化することである。

関連論文リスト

• A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix [2.7050250604223693]
  与えられた$dtimes d$ matrix $A$ のトップ固有ベクトルのよい近似を見つけることは、基礎的で重要な計算問題である。 上位固有ベクトルの近似の古典的な記述を出力する2つの異なる量子アルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-05-23T16:33:13Z)
• Fast Exact Retrieval for Nearest-neighbor Lookup (FERN) [0.0]
  厳密な近接探索は一般に、サブ線形解を持たない$O(Nd)$問題であると認識されている。 近距離近傍探索(FERN)のための対数的高速エクササイズ検索のための新しいアルゴリズムを提案する。 このアルゴリズムは1000万ドルの$d=128$に対して100%リコールした$O(dlog N)$ルックアップを達成する。
  論文  参考訳（メタデータ） (2024-05-07T15:57:39Z)
• Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
  Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。 Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-11T16:36:48Z)
• 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)
• 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)
• Matching Map Recovery with an Unknown Number of Outliers [0.0]
  我々は,2組の$d$次元雑音特徴ベクトル間のマッチング写像を求める問題を考察する。 高次元環境では、信号対雑音比が5(dlog(4nm/alpha))1/4$より大きい場合、真のマッチングマップは確率1-alpha$で復元可能であることを示す。
  論文  参考訳（メタデータ） (2022-10-24T15:59:10Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• Well Separated Pair Decomposition and power weighted shortest path metric algorithm fusion [0.0]
  私たちは、あるポイントセットで$s$-wellの分離ペアを$mathbbrn$, $n$$$>$$1で計算するアルゴリズムを考えています。 また、ダイクストラのアルゴリズムの置換であるアルゴリズムについても検討し、特定のパワー重み付き最短経路メトリックを用いてk$-nearestの隣人を計算し、$mathbbrn$,$n$$$$$$$$$$で計算する。
  論文  参考訳（メタデータ） (2021-03-20T17:38:13Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。 低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
  論文  参考訳（メタデータ） (2020-10-13T17:26:09Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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