論文の概要: A Note on Graph-Based Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2012.11083v1
• Date: Mon, 21 Dec 2020 02:18:05 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-27 06:27:55.605196
• Title: A Note on Graph-Based Nearest Neighbor Search
• Title（参考訳）: グラフに基づく最近傍探索に関する一考察
• Authors: Hongya Wang, Zhizheng Wang, Wei Wang, Yingyuan Xiao, Zeng Zhao, Kaixiang Yang
• Abstract要約: 高いクラスタリング係数は、グラフの最大強連結成分 (scc) に、q の k に近い近傍の大半を配置することを示している。 グラフに基づく探索アルゴリズムは,任意の地点を訪れると最大 SCC を横切ることが保証されている。
• 参考スコア（独自算出の注目度）: 4.38837720322254
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nearest neighbor search has found numerous applications in machine learning, data mining and massive data processing systems. The past few years have witnessed the popularity of the graph-based nearest neighbor search paradigm because of its superiority over the space-partitioning algorithms. While a lot of empirical studies demonstrate the efficiency of graph-based algorithms, not much attention has been paid to a more fundamental question: why graph-based algorithms work so well in practice? And which data property affects the efficiency and how? In this paper, we try to answer these questions. Our insight is that "the probability that the neighbors of a point o tends to be neighbors in the KNN graph" is a crucial data property for query efficiency. For a given dataset, such a property can be qualitatively measured by clustering coefficient of the KNN graph. To show how clustering coefficient affects the performance, we identify that, instead of the global connectivity, the local connectivity around some given query q has more direct impact on recall. Specifically, we observed that high clustering coefficient makes most of the k nearest neighbors of q sit in a maximum strongly connected component (SCC) in the graph. From the algorithmic point of view, we show that the search procedure is actually composed of two phases - the one outside the maximum SCC and the other one in it, which is different from the widely accepted single or multiple paths search models. We proved that the commonly used graph-based search algorithm is guaranteed to traverse the maximum SCC once visiting any point in it. Our analysis reveals that high clustering coefficient leads to large size of the maximum SCC, and thus provides good answer quality with the help of the two-phase search procedure. Extensive empirical results over a comprehensive collection of datasets validate our findings.
• Abstract（参考訳）: 近隣の検索は、機械学習、データマイニング、大規模データ処理システムに多くの応用を見出している。 過去数年間、空間分割アルゴリズムよりも優れているため、グラフベースの近接探索パラダイムが人気を博してきた。 グラフベースのアルゴリズムの効率を実証する実証的研究は多いが、なぜグラフベースのアルゴリズムが実際にこれほどうまく機能するのかという根本的な疑問にはあまり注目されていない。 そして、どのデータプロパティが効率と方法に影響するのか? 本稿では,これらの疑問に答えようと試みる。 我々の洞察では、"ある点 o の隣人が KNN グラフの隣人となる確率" は、クエリ効率にとって重要なデータ特性である。 与えられたデータセットに対して、そのような性質はKNNグラフのクラスタリング係数によって定性的に測定することができる。 クラスタリング係数がパフォーマンスにどのように影響するかを示すために、グローバル接続の代わりに、あるクエリq周辺のローカル接続がリコールに直接影響を与えることを識別する。 具体的には、高いクラスタリング係数がq の k 近傍の大部分をグラフ内の最大連結成分 (SCC) に配置することを示した。 アルゴリズム的な観点からは、探索手続きは実際には最大scc外の2つのフェーズと、それに含まれるもう1つのフェーズで構成されており、これは広く受け入れられている単一の経路や複数の経路の探索モデルとは異なる。 グラフに基づく探索アルゴリズムは,任意の地点を訪れると最大 SCC を横切ることが保証されている。 解析の結果,クラスタリング係数が高いと最大sccのサイズが大きくなり,二相探索の助けを借りて回答品質が良好であることが判明した。 包括的なデータセットコレクションに対する広範な実験結果が、我々の発見を裏付ける。

関連論文リスト

• 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)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Scalable and Effective Conductance-based Graph Clustering [9.938406925123722]
  グラフクラスタリングフレームワーク textitPCon を開発した。 既存のソリューションの多くをフレームワークに還元できることを示します。 本稿では,線形時間と空間の複雑さを考慮した2つの新しいアルゴリズムである textitPCon_core と emphPCon_de を提案する。
  論文  参考訳（メタデータ） (2022-11-22T12:45:27Z)
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search [20.928821121591493]
  効率的なグラフ探索を実現するための高速推論手法であるFINGERを提案する。 FINGERは、近傍の残差ベクトルと低ランク基底と分布マッチングとの角度を推定することで距離関数を近似する。 実証的に、FINGERによるHNSWと呼ばれるグラフベースの手法の高速化は、異なるベンチマークデータセット間で既存のグラフベースの手法を20%から60%上回っている。
  論文  参考訳（メタデータ） (2022-06-22T22:30:46Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。 提案されたSSCAGは最先端のアプローチと競合する。
  論文  参考訳（メタデータ） (2021-04-24T08:09:27Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods [44.007522460918565]
  密度の高い部分グラフをマイニングすることは、グラフマイニングタスクのスペクトルにおいて重要なプリミティブである。 実世界のグラフから非自明な大きさのクランプと準クランプをマイニングすることは、しばしば難しい問題ではないことを示す。
  論文  参考訳（メタデータ） (2020-08-18T15:50:25Z)
• Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
  重複する部分グラフを多数必要とせず,完全に学習可能なクラスタリングフレームワークを提案する。 提案手法はクラスタリングの精度を大幅に向上させ,その上で訓練した認識モデルの性能を向上させるが,既存の教師付き手法に比べて桁違いに効率的である。
  論文  参考訳（メタデータ） (2020-04-01T13:39:37Z)

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

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