Fugu-MT 論文翻訳(概要): Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation

論文の概要: Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation

arxiv url: http://arxiv.org/abs/2008.03260v2
Date: Mon, 17 Aug 2020 22:48:52 GMT
ステータス: 処理完了
システム内更新日: 2022-11-02 19:04:46.097052
Title: Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation
Title（参考訳）: MPIを用いた分散テラスケール類似度探索:単一距離計算のない数十億以上の効率的な類似度探索
Authors: Nicholas Meisburger, Anshumali Shrivastava
Abstract要約: SLASHはテラバイト規模のデータセットの類似性を近似的に検索する分散システムである。 SLASHはこの2.3テラバイトのデータを1時間以内に20ノードにインデックスし、クエリ時間をミリ秒単位で表示する。
参考スコア（独自算出の注目度）: 40.75034970144169
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present SLASH (Sketched LocAlity Sensitive Hashing), an MPI (Message Passing Interface) based distributed system for approximate similarity search over terabyte scale datasets. SLASH provides a multi-node implementation of the popular LSH (locality sensitive hashing) algorithm, which is generally implemented on a single machine. We show how we can append the LSH algorithm with heavy hitters sketches to provably solve the (high) similarity search problem without a single distance computation. Overall, we mathematically show that, under realistic data assumptions, we can identify the near-neighbor of a given query $q$ in sub-linear ($ \ll O(n)$) number of simple sketch aggregation operations only. To make such a system practical, we offer a novel design and sketching solution to reduce the inter-machine communication overheads exponentially. In a direct comparison on comparable hardware, SLASH is more than 10000x faster than the popular LSH package in PySpark. PySpark is a widely-adopted distributed implementation of the LSH algorithm for large datasets and is deployed in commercial platforms. In the end, we show how our system scale to Tera-scale Criteo dataset with more than 4 billion samples. SLASH can index this 2.3 terabyte data over 20 nodes in under an hour, with query times in a fraction of milliseconds. To the best of our knowledge, there is no open-source system that can index and perform a similarity search on Criteo with a commodity cluster.
Abstract（参考訳）: 本稿では、テラバイト規模のデータセット上での類似性探索を近似するためのMPIベースの分散システムSLASH(Sketched LocAlity Sensitive Hashing)を提案する。 slashは、一般的なlsh(locality sensitive hashing)アルゴリズムのマルチノード実装を提供する。我々は,LSHアルゴリズムにヘビーヒットタスケッチを付加して,単一距離計算なしで(高い)類似性探索問題を確実に解く方法を示す。数学的には、現実的なデータ仮定の下では、与えられたクエリのすぐ隣にある$q$ in sub-linear($ \ll O(n)$)の単純なスケッチアグリゲーション操作のみを識別できる。このようなシステムを実用化するために,機械間通信のオーバーヘッドを指数的に低減する新しい設計・スケッチソリューションを提案する。競合するハードウェアを直接比較すると、SLASHはPySparkの一般的なLSHパッケージよりも10000倍以上高速である。 PySparkは大規模なデータセットのためのLSHアルゴリズムの広く採用されている分散実装で、商用プラットフォームにデプロイされている。最後に、我々のシステムが40億以上のサンプルでテラスケールのCriteoデータセットにスケールする方法を示す。 slashはこの2.3テラバイトデータを1時間以内に20ノードにインデックスし、クエリ時間はほんの数ミリ秒である。私たちの知る限りでは、コモディティクラスタでcriteo上で類似性検索をインデックス化および実行できるオープンソースシステムは存在しません。

関連論文リスト

Distributed Collapsed Gibbs Sampler for Dirichlet Process Mixture Models in Federated Learning [0.22499166814992444]
本稿では,DPMM (DisCGS) のための分散マルコフ連鎖モンテカルロ (MCMC) 推論手法を提案する。我々のアプローチでは、崩壊したGibbsサンプルラーを使用し、独立マシンと異種マシンの分散データを扱うように設計されています。例えば、100Kのデータポイントのデータセットでは、中央集権的なアルゴリズムは100回のイテレーションを完了するのに約12時間かかります。
論文参考訳（メタデータ） (2023-12-18T13:16:18Z)
DeepLSH: Deep Locality-Sensitive Hash Learning for Fast and Efficient Near-Duplicate Crash Report Detection [0.29998889086656577]
リアルタイムストリーミングバグ収集では、システムはすぐに質問に答える必要がある: 新しいバグと最もよく似たバグは何か? LSHは、クラッシュバケットの文献では考慮されていない。本稿では、局所性感度特性を完璧に近似した、元の損失関数を持つシームズアーキテクチャであるDeepLSHを紹介する。
論文参考訳（メタデータ） (2023-10-10T15:26:27Z)
Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文参考訳（メタデータ） (2022-10-14T01:42:05Z)
Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search [57.18075258042082]
このコンペティションは、ANNSアルゴリズムをハードウェアコスト、精度、性能で数十億ドル規模で比較する。このコンペティションのために新たに4つの、60億の多様なデータセットをまとめました。
論文参考訳（メタデータ） (2022-05-08T02:41:54Z)
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文参考訳（メタデータ） (2022-03-28T21:34:16Z)
SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings [18.916058638077274]
本稿では,ANN (Non-parametric and data-independent learning from set-structured data using almost near neighbor (ANN) solutions。 Sliced-Wasserstein set embedding as a computerly efficient "set-2-vector" mechanism that possible downstream ANN。本稿では,SLOSH (Set-LOcality Sensitive Hashing) と呼ばれるアルゴリズムの有効性を,様々なデータセットで示す。
論文参考訳（メタデータ） (2021-12-11T00:10:05Z)
IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
分散環境でのロードバランスとスケーラビリティを維持しながら、高い精度を得る方法とのトレードオフが必要だ。クエリ項目関連データから直接バケットを学習することで、アイテムを反復的に分割するIRLIと呼ばれる新しいアプローチを提案する。我々は,irliが極めて自然な仮定の下で高い確率で正しい項目を検索し,優れた負荷分散を実現することを数学的に示す。
論文参考訳（メタデータ） (2021-03-17T23:13:25Z)
LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew [58.21885402826496]
全ペアセットの類似性は、大規模で高次元のデータセットであっても広く使われているデータマイニングタスクである。我々は,全対集合の類似性を近似するために,新しい分散アルゴリズム LSF-Join を提案する。 LSF-Joinは、小さな類似度閾値やスキュー入力セットであっても、最も近いペアを効率的に見つける。
論文参考訳（メタデータ） (2020-03-06T00:06:20Z)

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

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