論文の概要: 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の通信,作業,最大負荷の保証を証明し,その精度を複数のグラフ上で実験的に実証する。

関連論文リスト

• Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
  プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。 目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。 そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元するアルゴリズムであるMaximumDegree (MAD)を提案する。
  論文  参考訳（メタデータ） (2025-02-13T01:27:11Z)
• Billion-scale Similarity Search Using a Hybrid Indexing Approach with Advanced Filtering [49.1574468325115]
  本稿では,CPU推論に最適化された数十億規模のデータセット上での複雑なフィルタリング機能を備えた類似度探索のための新しい手法を提案する。 提案手法は,従来のIVF-Flatインデックス構造を拡張し,多次元フィルタを統合する。 提案アルゴリズムは,高次元空間での高速な探索を可能にするため,高密度埋め込みと離散フィルタ特性を組み合わせる。
  論文  参考訳（メタデータ） (2025-01-23T07:47:00Z)
• 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)

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

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