論文の概要: LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew

• arxiv url: http://arxiv.org/abs/2003.02972v1
• Date: Fri, 6 Mar 2020 00:06:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-26 01:56:31.785196
• Title: LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew
• Title（参考訳）: LSF-Join: 分散オールペアのための局所性感性フィルタ
• Authors: Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff
• Abstract要約: 全ペアセットの類似性は、大規模で高次元のデータセットであっても広く使われているデータマイニングタスクである。 我々は,全対集合の類似性を近似するために,新しい分散アルゴリズム LSF-Join を提案する。 LSF-Joinは、小さな類似度閾値やスキュー入力セットであっても、最も近いペアを効率的に見つける。
• 参考スコア（独自算出の注目度）: 58.21885402826496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: All-pairs set similarity is a widely used data mining task, even for large and high-dimensional datasets. Traditionally, similarity search has focused on discovering very similar pairs, for which a variety of efficient algorithms are known. However, recent work highlights the importance of finding pairs of sets with relatively small intersection sizes. For example, in a recommender system, two users may be alike even though their interests only overlap on a small percentage of items. In such systems, some dimensions are often highly skewed because they are very popular. Together these two properties render previous approaches infeasible for large input sizes. To address this problem, we present a new distributed algorithm, LSF-Join, for approximate all-pairs set similarity. The core of our algorithm is a randomized selection procedure based on Locality Sensitive Filtering. Our method deviates from prior approximate algorithms, which are based on Locality Sensitive Hashing. Theoretically, we show that LSF-Join efficiently finds most close pairs, even for small similarity thresholds and for skewed input sets. We prove guarantees on the communication, work, and maximum load of LSF-Join, and we also experimentally demonstrate its accuracy on multiple graphs.
• Abstract（参考訳）: all-pairs set similarityは、大規模かつ高次元のデータセットでも広く使われているデータマイニングタスクである。 伝統的に類似性探索は、様々な効率的なアルゴリズムが知られている非常に類似したペアを見つけることに集中してきた。 しかし、最近の研究は、比較的小さな交叉サイズを持つ集合のペアを見つけることの重要性を強調している。 例えば、レコメンダシステムでは、2人のユーザーは、関心がわずかな割合でしかオーバーラップしていないのに似ています。 このようなシステムでは、しばしば非常に人気があるため、いくつかの次元は高度に歪められている。 これら2つの特性は、大きな入力サイズに対して以前のアプローチでは不可能である。 この問題に対処するために,全ペア集合の類似性を近似する新しい分散アルゴリズム lsf-join を提案する。 アルゴリズムのコアは局所性に敏感なフィルタリングに基づくランダムな選択手順である。 提案手法は,局所性に敏感なハッシュ法に基づく近似アルゴリズムから逸脱する。 理論的には、LSF-Joinは、小さな類似度閾値や歪んだ入力セットであっても、最も近いペアを効率的に見つける。 我々は,LSF-Joinの通信,作業,最大負荷の保証を証明し,その精度を複数のグラフ上で実験的に実証する。

関連論文リスト

• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [8.15681999722805]
  本稿では, 点集合の密度に基づくクラスタリングについて検討する。 密度ピークの異なる変種を単一のフレームワークPECANNに統合する。 PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
  論文  参考訳（メタデータ） (2023-12-06T22:43:50Z)
• ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms [5.478671305092084]
  本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。 我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
  論文  参考訳（メタデータ） (2023-05-07T19:28:23Z)
• Scalable Batch Acquisition for Deep Bayesian Active Learning [70.68403899432198]
  ディープラーニングでは、各ステップでマークアップする複数の例を選択することが重要です。 BatchBALDのような既存のソリューションでは、多くの例を選択する際に大きな制限がある。 本稿では,より計算効率のよいLarge BatchBALDアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-13T11:45:17Z)
• Parallel Instance Filtering for Malware Detection [0.0]
  この研究は、Parallel Instance Filtering (PIF)と呼ばれる新しい並列インスタンス選択アルゴリズムを提案する。 このアルゴリズムの主な考え方は、データセット全体をカバーしているインスタンスの重複しないサブセットにデータセットを分割し、各サブセットにフィルタリングプロセスを適用することである。 我々はPIFアルゴリズムと、50,000の悪意あるサンプルからなる大規模なデータセット上で、最先端のインスタンス選択アルゴリズムを比較した。
  論文  参考訳（メタデータ） (2022-06-28T11:14:20Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendation [20.42993976179691]
  本稿では,任意のマッチング関数にANN探索を拡張する新しい手法を提案する。 我々の主な考えは、すべての項目から構築された類似性グラフに一致する関数で、欲張りのウォークを実行することである。 提案手法は,Taobaoのディスプレイ広告プラットフォームに完全に展開されており,広告収入の大幅な増加をもたらす。
  論文  参考訳（メタデータ） (2022-02-14T07:55:57Z)
• 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)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。 代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。 データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
  論文  参考訳（メタデータ） (2021-12-06T20:34:55Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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