GPU-Accelerated Construction of the Gabriel Graph: Parallelization Strategies and Applications to Large-Margin Classification and Graph-Based Clustering

1 Introduction

• The empty-hypersphere check costs O(N^3) across candidate pairs, limiting Gabriel-graph pipelines as datasets reach thousands of samples.The paper identifies this cost as a bottleneck for large-scale and real-time applications.Source: §1 · p. 2
• A closed-form mapping assigns each CUDA thread index to a vertex pair in O(1) time and memory, avoiding an O(N^2) index table.Source: §1 · p. 2
• Two-pass bitmask compaction uses atomic operations to store valid edges in a dense array sized near O(|E|), rather than O(N^2).Source: §1 · p. 2
• Thread coarsening assigns multiple candidate pairs to each thread, but its best factor varies by dataset.It reduces execution time on one dataset but not another.Source: §1 · p. 2
• The approach supports an accelerated NN-clas classifier and a GPU-native clustering method using filtered-graph connected components and hierarchical Union–Find merging.Source: §1 · p. 2
• Across 14 public datasets, the evaluation reports speedups up to 8484× over a sequential CPU baseline and compares clustering quality with K-means and DBSCAN.Source: §1 · p. 2

Gabriel-graph-based classification

• Gabriel-graph classifiers use cross-class support edges to delineate a margin without explicit optimization; prior studies address label-noise filtering, FPGA acceleration, and multiclass extensions.The cited works are Garcia et al. (2015), Arias-Garcia et al. (2024), and Hanriot et al. (2024).Source: §2 · p. 3

GPU-accelerated machine learning

• Prior GPU machine-learning work motivates acceleration generally but does not address proximity-graph construction's specific combinatorial structure.Source: §2 · p. 3

Thread granularity and coarsening

• Thread coarsening assigns more work to each GPU thread to address scheduling overhead from one-thread-per-element mappings, a principle adopted and evaluated for Gabriel-graph construction.The discussion builds on Magni et al. (2014).Source: §2 · p. 3

Graph-based clustering

• The clustering approach selects edges with an elbow-based threshold on sorted Gabriel edge weights, then evaluates cluster validity with internal indices.The passage situates these choices within prior work on connected-component clustering and validity-index surveys.Source: §2 · p. 3

3.1 Definition and Basic Properties

• A Gabriel edge exists when no other point lies strictly inside the open hypersphere with the pair as its diameter.In labeled binary classification, cross-class support edges localize the decision boundary under mild class-overlap assumptions.Source: §3.1 · p. 3
• Checking each candidate pair costs O(N), yielding O(N^3) naive construction, while the graph is sparse and motivates memory-conscious parallel construction.The graph is a Delaunay subgraph; its edge count is O(N) in the planar case and generally much less than N^2 in higher dimensions for non-adversarial data.Source: §3.1 · pp. 3–4
• Figure 1 distinguishes same-class gray edges from red cross-class support edges and illustrates an admitted edge whose dashed circle contains no other point.Source: §3.1 · p. 3, Figure 1 · p. 4

3.2 The SIMT Execution Model

• Each candidate pair can be evaluated independently by a GPU thread with read-only access to the immutable point set.CUDA groups threads into lock-step warps, with performance affected by control-flow divergence, memory coalescing, and atomic-write contention.Source: §3.2 · p. 4

4.1 Naive Parallelization and the Indexing Problem

• A direct one-thread-per-pair GPU mapping still requires each thread to recover its pair from a linear index, while an explicit lookup table can consume prohibitive O(N^2) memory.Source: §4.1 · p. 5

4.2 Implicit Index Mapping k 7→(i, j)

• The closed-form inverse maps each linear index k to its vertex pair (i, j) in constant time and memory, without an auxiliary table or per-thread branching.Source: §4.2 · p. 5

4.3 Two-Pass Construction with Bitmask Compaction

• A two-pass bitmask scheme marks valid pairs, allocates the exact edge-list size, then compacts marked edges into a dense array proportional to |E|.Bit packing reduces flag storage relative to one integer per pair.Source: §4.3 · p. 6

4.4 Thread Coarsening

• Assigning each thread several contiguous candidate pairs amortizes per-thread overhead, but larger blocks can worsen load balance and increase execution time.The optimal coarsening factor is dataset-dependent.Source: §4.4 · p. 6

4.5 Summary of the Construction Pipeline

• The construction pipeline combines implicit indexing, thread coarsening, and two-pass compaction.Source: §4.5 · p. 6

5.1 Accelerating a Gabriel-Graph Large-Margin Classifier

• NN-clas builds the Gabriel graph before and after quality-based vertex filtering; those two construction passes dominate its cost and are accelerated, while filtering and border-vertex classification remain comparatively cheap.Source: §5.1 · pp. 6–7

5.2 A Gabriel-Graph Clustering Algorithm

• The clustering method selects an edge-weight threshold with an elbow heuristic, forms a residual graph, and computes its connected components using GPU parallel Union–Find.If a target K is supplied and the component count exceeds it, the method can hierarchically merge components using the minimum-weight connecting edge.Source: §5.2 · pp. 7–8
• The clustering pipeline remains on the GPU after graph construction, requires no density radius or minimum-points parameter, and reports the elbow-implied cluster count when no target K is supplied.Source: §5.2 · p. 8

6.3 Effect of Thread Coarsening

• On Diabetes, execution time was about 15% below c = 1 at c = 128–512 pairs per thread, but about 35% above c = 1 at c = 65536.At c ≳8192, time exceeded the c = 1 time.Source: §6.3 · p. 9
• On Internet Firewall Data, execution time increased across tested coarsening factors; c = 1 was best, while c = 1024 was roughly 40% slower.Run-to-run variability was large relative to neighboring settings, so the authors advise reading only the overall trend.Source: §6.3 · p. 9

6.2 Sequential vs. Parallel Graph-Based Classification

• 237× to 8484× speedups were measured for GPU-parallel classification, with accuracy and F1-score matching the sequential baseline in every case.The range runs from Golub (N = 72) to German (N = 1000); Table 1 reports execution time, speedup, accuracy, and F1-score.Source: §6.2 · p. 9, Table 1 · p. 9, Figure 3 · p. 10

6.1 Setup

• The clustering evaluation used 14 datasets and five internal validity indices, with both automatic and K-optimized regimes.Datasets comprised seven synthetic 2-D sets and seven real UCI datasets; timings isolated kernel and algorithmic execution rather than host–device transfers.Source: §6.1 · p. 8, §6.4 · p. 10

6.4 Clustering Quality

• On Dunn, clustering was statistically indistinguishable from DBSCAN in the K-optimized regime, while K-optimized Silhouette and Davies–Bouldin results were statistically indistinguishable from K-means.Dunn average ranks were 1.69 for the proposed method and 1.73 for DBSCAN; hierarchical merging corrected over-fragmentation seen in the automatic regime.Source: §6.4 · p. 10

• GPU construction reduces execution time by two to nearly four orders of magnitude without loss of downstream accuracy; thread coarsening helps some datasets, but not all.Source: §7 · pp. 10–11
• Clustering is competitive with DBSCAN on the Dunn index while avoiding an explicit density-radius parameter.Source: §7 · p. 11
• Speedups compare a single-threaded CPU with a single GPU; a multi-threaded CPU baseline would narrow the gap while leaving qualitative conclusions unchanged.Source: §7 · p. 11
• Hierarchical merging performs a global minimum-weight-edge search at each step, adding sequential dependency across merge iterations.Source: §7 · p. 11
• At N ≈ 10^5, T ≈ 5×10^9 candidate pairs; exceeding single-GPU bitmask memory would require a multi-GPU or out-of-core extension.Source: §7 · p. 11

• Implicit constant-time pair indexing, two-pass bitmask-compacted edge construction, and thread coarsening reduce classifier execution time by up to 8484× across 14 datasets without loss of classification accuracy.Source: §8 · p. 11
• The proposed GPU-native clustering method uses an automatic elbow threshold, parallel Union-Find, and optional hierarchical merging; it is statistically competitive with DBSCAN on Dunn without a density-radius hyperparameter.Source: §8 · p. 11
• Future work includes multi-GPU and out-of-core extensions, energy-efficiency characterization, alternative cut-selection criteria, and comparison with multi-threaded CPU baselines.Source: §8 · p. 11