論文の概要: GPU-Accelerated Construction of the Gabriel Graph: Parallelization Strategies and Applications to Large-Margin Classification and Graph-Based Clustering

• arxiv url: http://arxiv.org/abs/2610.28759v1
• Date: Tue, 20 Oct 2026 18:03:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-23 00:40:06.112335
• Title: GPU-Accelerated Construction of the Gabriel Graph: Parallelization Strategies and Applications to Large-Margin Classification and Graph-Based Clustering
• Title（参考訳）: GPUによるガブリエルグラフの構築:並列化戦略と大規模マージン分類とグラフベースクラスタリングへの応用
• Abstract要約: 本稿では,ガブリエルグラフを大規模に構築するための並列化戦略を提案する。 本稿では,ガブリエルグラフに基づく大規模分類器(NN-clas)の高速化と,ガブリエルグラフクラスタリングアルゴリズムについて評価する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Gabriel graph is a proximity graph widely used in computational geometry and geometric machine learning, underlying large-margin classifiers and, as we show in this work, density-aware clustering methods. Its construction, however, has cubic time complexity $O(N^3)$ in the naive formulation, which severely limits its use on datasets beyond a few thousand samples. This paper presents a set of GPU parallelization strategies, implemented in CUDA, that make Gabriel graph construction practical at scale. We introduce (i) an implicit closed-form mapping from a linear thread index to the corresponding vertex pair $(i,j)$, which removes the need for an explicit $O(N^2)$ adjacency structure and lets every thread locate its pair in constant time and constant memory; (ii) a two-pass, bitmask-based, atomically-compacted edge-list construction that produces a dense edge array proportional only to the number of edges actually found; and (iii) a thread-coarsening strategy in which each thread evaluates several candidate pairs, trading launch and scheduling overhead against load balance. We evaluate these strategies on the acceleration of a Gabriel-graph-based large-margin classifier (NN-clas) and on a novel Gabriel-graph clustering algorithm that identifies connected components on a residual graph and performs GPU-parallel Union-Find with hierarchical edge-based merging. On 14 public benchmark datasets, the GPU implementation reduces Gabriel graph construction time by two to nearly four orders of magnitude relative to a sequential CPU baseline (up to 8484x), without loss of classification accuracy, and the proposed clustering method is statistically competitive with DBSCAN on the topological validity index Dunn while eliminating the need for an explicit density radius parameter.
• Abstract（参考訳）: ガブリエルグラフ(Gabriel graph)は、計算幾何学および幾何機械学習において広く用いられる近接グラフであり、大マルジン分類器の基礎であり、この研究で示されているように、密度対応クラスタリング法である。 しかし、その構成は、単純定式化において3次時間複雑性$O(N^3)$であり、数千サンプルを超えるデータセットの使用を著しく制限している。 本稿では,CUDAで実装されたGPU並列化戦略の集合について述べる。 紹介 i) 線形スレッドインデックスから対応する頂点ペア$(i,j)$への暗黙的なクローズドフォームマッピングで、明示的な$O(N^2)$アジャシアンス構造の必要性を排除し、すべてのスレッドがそのペアを一定時間と一定メモリで配置できるようにする。 (ii)実際に見つかったエッジの数に比例した密度のエッジアレイを生成する2パスビットマスクベースの原子計算エッジリスト構成 3) 各スレッドが複数の候補ペアを評価し,ロードバランシングに対するオーバヘッドのトレーディングとスケジューリングを行うスレッド粗大化戦略。 本稿では,ガブリエルグラフに基づく大規模クラスタ化器(NN-clas)の高速化と,残グラフ上の連結成分を識別し,階層的なエッジベースのマージによるGPU並列Union-Findを実行するガブリエルグラフクラスタリングアルゴリズムについて評価する。 14の公開ベンチマークデータセットにおいて、GPU実装は、分類精度を損なうことなく、連続CPUベースライン(8484xまで)と比較してガブリエルグラフ構築時間を2～4桁に短縮し、提案したクラスタリング法は、明示的な密度半径パラメータを排除しつつ、トポロジ的妥当性指標Dunn上のDBSCANと統計的に競合する。

関連論文リスト

• GraphGSOcc: Semantic-Geometric Graph Transformer with Dynamic-Static Decoupling for 3D Gaussian Splatting-based Occupancy Prediction [2.3239379129613535]
  GraphGSOccは、意味グラフと幾何学グラフを組み合わせ、動的静的オブジェクトを分離する新しいフレームワークである。 SurroundOcc-nuScenes、Occ3D-nuScenes、OpenOcc、KITTIの占有ベンチマークで最先端のパフォーマンスを実現している。
  論文  参考訳（メタデータ） (2025-06-13T06:09:57Z)
• PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms [14.601622103700516]
  グラフのクラスタリングノードは、グラフ解析の土台である。 いくつかの一般的な方法は、非常に大きなグラフには適さない。 この研究は、クラスタリングアルゴリズムを高速化するオーバーレイであるPASCOを導入している。
  論文  参考訳（メタデータ） (2024-12-18T08:15:55Z)
• GC-Bench: An Open and Unified Benchmark for Graph Condensation [54.70801435138878]
  我々は,グラフ凝縮の性能を解析するための総合的なグラフ凝縮ベンチマーク (GC-Bench) を開発した。 GC-Benchは、グラフ凝縮の特徴を以下の次元で体系的に研究している。 我々は,再現性のある研究を容易にするために,異なるGC手法を訓練し,評価するための簡易ライブラリを開発した。
  論文  参考訳（メタデータ） (2024-06-30T07:47:34Z)
• Accel-GCN: High-Performance GPU Accelerator Design for Graph Convolution Networks [12.181052673940465]
  グラフ畳み込みネットワーク(GCN)は、様々な領域にわたるグラフデータから潜伏情報を抽出する上で重要である。 本稿では,GCNのためのGPUアクセラレータアーキテクチャであるAccel-GCNを紹介する。 18のベンチマークグラフに対するAccel-GCNの評価では、cuSPARSE、GNNAdvisor、Graph-BLASTをそれぞれ1.17倍、1.86倍、2.94倍で上回っている。
  論文  参考訳（メタデータ） (2023-08-22T23:12:17Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  我々は,超効率的なサイストリックアレイベースの多用途ハードウェアアクセラレータである textitVersaGNN を提案する。 textitVersaGNNは平均3712$times$ speedup with 1301.25$times$ energy reduction on CPU、35.4$times$ speedup with 17.66$times$ energy reduction on GPUを達成している。
  論文  参考訳（メタデータ） (2021-05-04T04:10:48Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。 提案されたSSCAGは最先端のアプローチと競合する。
  論文  参考訳（メタデータ） (2021-04-24T08:09:27Z)
• Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
  ポイントクラウド上で学習するためのグラフ畳み込みネットワーク(GCN)の計算効率の向上を目指します。 一連の実験により、最適化されたネットワークは計算複雑性を減らし、メモリ消費を減らし、推論速度を加速した。
  論文  参考訳（メタデータ） (2021-04-12T17:59:16Z)
• Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for Large Eigengaps of Dense Graphs and Hypergraphs [0.0]
  Graph Convolutional Networks (GCNs) は、グラフベースのデータセットで半教師付き分類を行うツールとして成功している。 本稿では,三部フィルタ空間が高密度グラフを対象とする新しいGCN変種を提案する。
  論文  参考訳（メタデータ） (2020-08-03T08:48:41Z)

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

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