Search NASA⌕ Search

SEARCH · Search NASA

Results for “hierarchical algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 91 records · Page 5

Hierarchical Linear Regression (Rev. 1)

We describe an algorithm for making inferences in a hierarchical linear model. The model allows different slopes and intercepts for different groups, and ties together the different slopes by representing them as samples from a higher level distribution. (The intercepts are treated as statistically independent.) Our model and code permit many options for the variance of this hierarchical distribution for the slopes, including gamma distributions on the precision, t-distributions on the standard error, pooled slopes (all equal), and independent slopes. The algorithm is described in the paper; an implementation of the algorithm in R is available on request.

97 MATHEMATICS AND COMPUTING↗

Extending a Tandem Mass Spectral Library to Include MS{sup 2} Spectra of Fragment Ions Produced In-Source and MS{sup n} Spectra

Tandem mass spectral library searching is finding increased use as an effective means of determining chemical identity in mass spectrometry-based omics studies. We previously reported on constructing a tandem mass spectral library that includes spectra for multiple precursor ions for each analyte. Here we report our method for expanding this library to include MS{sup 2} spectra of fragment ions generated during the ionization process (in-source fragment ions) as well as MS{sup 3} and MS{sup 4} spectra. These can assist the chemical identification process. A simple density-based clustering algorithm was used to cluster all significant precursor ions from MS{sup 1} scans for an analyte acquired during an infusion experiment. The MS{sup 2} spectra associated with these precursor ions were grouped into the same precursor clusters. Subsequently, a new top-down hierarchical divisive clustering algorithm was developed for clustering the spectra from fragmentation of ions in each precursor cluster, including the MS{sup 2} spectra of the original precursors and of the in-source fragments as well as the MS{sup n} spectra. This algorithm starts with all the spectra of one precursor in one cluster and then separates them into sub-clusters of similar spectra based on the fragment patterns. Herein, we describe the algorithms and spectral evaluation methods for extending the library. The new library features were demonstrated by searching the high resolution spectra of E. coli extracts against the extended library, allowing identification of compounds and their in-source fragment ions in a manner that was not possible before. .

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

TU-C-17A-01: A Data-Based Development for Pratical Pareto Optimality Assessment and Identification

Purpose: To develop an efficient Pareto optimality assessment scheme to support plan comparison and practical determination of best-achievable practical treatment plan goals. Methods: Pareto efficiency reflects the tradeoffs among competing target coverage and normal tissue sparing in multi-criterion optimization (MCO) based treatment planning. Assessing and understanding Pareto optimality provides insightful guidance for future planning. However, current MCO-driven Pareto estimation makes relaxed assumptions about the Pareto structure and insufficiently account for practical limitations in beam complexity, leading to performance upper bounds that may be unachievable. This work proposed an alternative data-driven approach that implicitly incorporates the practical limitations, and identifies the Pareto frontier subset by eliminating dominated plans incrementally using the Edgeworth Pareto hull (EPH). The exactness of this elimination process also permits the development of a hierarchical procedure for speedup when the plan cohort size is large, by partitioning the cohort and performing elimination in each subset before a final aggregated elimination. The developed algorithm was first tested on 2D and 3D where accuracy can be reliably assessed. As a specific application, the algorithm was applied to compare systematic plan quality for lower head-and-neck, amongst 4 competing treatment modalities. Results: The algorithm agrees exactly with brute-force pairwise comparison and visual inspection in low dimensions. The hierarchical algorithm shows sqrt(k) folds speedup with k being the number of data points in the plan cohort, demonstrating good efficiency enhancement for heavy testing tasks. Application to plan performance comparison showed superiority of tomotherapy plans for the lower head-and-neck, and revealed a potential nonconvex Pareto frontier structure. Conclusion: An accurate and efficient scheme to identify Pareto frontier from a plan cohort has been developed. This implementation would guide generating good yet practically achievable plan quality goals for further planning. The observation of a systematic performance bias and a nonconvex Pareto frontier warrants further investigation.

60 APPLIED LIFE SCIENCES↗

Hierarchical Control of Megawatt-Scale Charging Stations for Electric Trucks with Distributed Energy Resources

Electrifying medium- and heavy-duty trucks is critical to decarbonizing the transportation sector. Energy needs of electric trucks will likely require megawatt-scale charging stations, which could significantly stress the electric distribution grid. Distributed energy resources (DER) can alleviate this stress and reduce charging costs with proper management. To that end, this work develops a hierarchical predictive control algorithm for future multi-port megawatt-scale charging stations that can provide real-time energy management for stations, decide charging rates, dispatch energy storage system (ESS), and provide grid voltage support. We integrate three algorithmic components: (i) an energy management optimization (EMO) that provides supervisory control to DER assets and charging loads at minute scale, (ii) a real-time energy management system (RT-EMS) that heuristically compensates for fast disturbances at sub-second scale, and (iii) a model predictive control (MPC)-based battery management system (BMS) that communicates future charging demands to the EMO, to manage the overall megawatt-scale site. Additionally, validation in a controller hardware-in-the-loop (CHIL) environment shows that the hierarchical controller can reduce the total energy consumption from the grid by approximately 28% compared to an uncontrolled case for the station configuration in this paper, without impacting charging time.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations

In this work, we present a fast and approximate multifrontal solver for large-scale sparse linear systems arising from finite-difference, finite-volume or finite-element discretization of high-frequency wave equations. The proposed solver leverages the butterfly algorithm and its hierarchical matrix extension for compressing and factorizing large frontal matrices via graph-distance guided entry evaluation or randomized matrix-vector multiplication-based schemes. Complexity analysis and numerical experiments demonstrate $\mathcal{O}(N\log^2 N)$ computation and $\mathcal{O}(N)$ memory complexity when applied to an $N\times N$ sparse system arising from 3D high-frequency Helmholtz and Maxwell problems.

97 MATHEMATICS AND COMPUTING↗

Sparse Approximate Multifrontal Factorization with Composite Compression Methods

This article presents a fast and approximate multifrontal solver for large sparse linear systems. In a recent work by Liu et al., we showed the efficiency of a multifrontal solver leveraging the butterfly algorithm and its hierarchical matrix extension, HODBF (hierarchical off-diagonal butterfly) compression to compress large frontal matrices. The resulting multifrontal solver can attain quasi-linear computation and memory complexity when applied to sparse linear systems arising from spatial discretization of high-frequency wave equations. To further reduce the overall number of operations and especially the factorization memory usage to scale to larger problem sizes, in this article we develop a composite multifrontal solver that employs the HODBF format for large-sized fronts, a reduced-memory version of the nonhierarchical block low-rank format for medium-sized fronts, and a lossy compression format for small-sized fronts. This allows us to solve sparse linear systems of dimension up to 2.7 × larger than before and leads to a memory consumption that is reduced by 70% while ensuring the same execution time. The code is made publicly available in GitHub.

97 MATHEMATICS AND COMPUTING↗

QUANTIFYING OBSERVATIONAL PROJECTION EFFECTS USING MOLECULAR CLOUD SIMULATIONS

The physical properties of molecular clouds are often measured using spectral-line observations, which provide the only probes of the clouds' velocity structure. It is hard, though, to assess whether and to what extent intensity features in position-position-velocity (PPV) space correspond to 'real' density structures in position-position-position (PPP) space. In this paper, we create synthetic molecular cloud spectral-line maps of simulated molecular clouds, and present a new technique for measuring the reality of individual PPV structures. Using a dendrogram algorithm, we identify hierarchical structures in both PPP and PPV space. Our procedure projects density structures identified in PPP space into corresponding intensity structures in PPV space and then measures the geometric overlap of the projected structures with structures identified from the synthetic observation. The fractional overlap between a PPP and PPV structure quantifies how well the synthetic observation recovers information about the three-dimensional structure. Applying this machinery to a set of synthetic observations of CO isotopes, we measure how well spectral-line measurements recover mass, size, velocity dispersion, and virial parameter for a simulated star-forming region. By disabling various steps of our analysis, we investigate how much opacity, chemistry, and gravity affect measurements of physical properties extracted from PPV cubes. For the simulations used here, which offer a decent, but not perfect, match to the properties of a star-forming region like Perseus, our results suggest that superposition induces a ∼40% uncertainty in masses, sizes, and velocity dispersions derived from {sup 13}CO (J = 1-0). As would be expected, superposition and confusion is worst in regions where the filling factor of emitting material is large. The virial parameter is most affected by superposition, such that estimates of the virial parameter derived from PPV and PPP information typically disagree by a factor of ∼2. This uncertainty makes it particularly difficult to judge whether gravitational or kinetic energy dominate a given region, since the majority of virial parameter measurements fall within a factor of two of the equipartition level α ∼ 2.

79 ASTRONOMY AND ASTROPHYSICS↗

Machine learning a bond order potential model to study thermal transport in WSe 2 nanostructures

Here, nanostructures of transition metal di-chalcogenides (TMDCs) exhibit exotic thermal, chemical and electronic properties, enabling diverse applications from thermoelectrics and catalysis to nanoelectronics. The thermal properties of these nanoscale TMDCs are of particular interest for thermoelectric applications. Thermal transport studies on nanotubes and nanoribbons remain intractable to first principles calculations whereas existing classical molecular models treat the two chalcogen layers in a monolayer with different atom types; this imposes serious limitations in studying multi-layered TMDCs and dynamical phenomena such as nucleation and growth. Here, we overcome these limitations using machine learning (ML) and introduce a bond order potential (BOP) trained against first principles training data to capture the structure, dynamics, and thermal transport properties of a model TMDC such as WSe 2 . The training is performed using a hierarchical objective genetic algorithm workflow to accurately describe the energetics, as well as thermal and mechanical properties of a free-standing sheet. As a representative case study, we perform molecular dynamics simulations using the ML-BOP model to study the structure and temperature-dependent thermal conductivity of WSe 2 tubes and ribbons of different chiralities. We observe slightly higher thermal conductivities along the armchair direction than zigzag for WSe 2 monolayers but the opposite effect for nanotubes, especially of smaller diameters. We trace the origin of these differences to the anisotropy in thermal transport and the restricted momentum selection rules for phonon–phonon Umpklapp scattering. The developed ML-BOP model is of broad interest and will facilitate studies on nucleation and growth of low dimensional WSe 2 structures as well as their transport properties for thermoelectric and thermal management applications.

36 MATERIALS SCIENCE↗

THE HERSCHEL EXPLOITATION OF LOCAL GALAXY ANDROMEDA (HELGA). VI. THE DISTRIBUTION AND PROPERTIES OF MOLECULAR CLOUD ASSOCIATIONS IN M31

In this paper we present a catalog of giant molecular clouds (GMCs) in the Andromeda (M31) galaxy extracted from the Herschel Exploitation of Local Galaxy Andromeda (HELGA) data set. GMCs are identified from the Herschel maps using a hierarchical source extraction algorithm. We present the results of this new catalog and characterize the spatial distribution and spectral energy properties of its clouds based on the radial dust/gas properties found by Smith et al. A total of 326 GMCs in the mass range 10{sup 4}-10{sup 7} M {sub ☉} are identified; their cumulative mass distribution is found to be proportional to M {sup –2.34}, in agreement with earlier studies. The GMCs appear to follow the same correlation of cloud mass to L {sub CO} observed in the Milky Way. However, comparison between this catalog and interferometry studies also shows that the GMCs are substructured below the Herschel resolution limit, suggesting that we are observing associations of GMCs. Following Gordon et al., we study the spatial structure of M31 by splitting the observed structure into a set of spiral arms and offset rings. We fit radii of 10.3 and 15.5 kpc to the two most prominent rings. We then fit a logarithmic spiral with a pitch angle of 8.°9 to the GMCs not associated with either ring. Last, we comment on the effects of deprojection on our results and investigate the effect different models for M31's inclination will have on the projection of an unperturbed spiral arm system.

79 ASTRONOMY AND ASTROPHYSICS↗

TU-C-17A-04: BEST IN PHYSICS (THERAPY) - A Supervised Framework for Automatic Contour Assessment for Radiotherapy Planning of Head- Neck Cancer

Purpose: Precise contour delineation of tumor targets and critical structures from CT simulations is essential for accurate radiotherapy (RT) treatment planning. However, manual and automatic delineation processes can be error prone due to limitations in imaging techniques and individual anatomic variability. Tedious and laborious manual verification is hence needed. This study develops a general framework for automatically assessing RT contours for head-neck cancer patients using geometric attribute distribution models (GADMs). Methods: Geometric attributes (centroid and volume) were computed from physician-approved RT contours of 29 head-neck patients. Considering anatomical correlation between neighboring structures, the GADM for each attribute was trained to characterize intra- and interpatient structure variations using principal component analysis. Each trained GADM was scalable and deformable, but constrained by the principal attribute variations of the training contours. A new hierarchical model adaptation algorithm was utilized to assess the RT contour correctness for a given patient. Receiver operating characteristic (ROC) curves were employed to evaluate and tune system parameters for the training models. Results: Experiments utilizing training and non-training data sets with simulated contouring errors were conducted to validate the framework performance. Promising assessment results of contour normality/abnormality for the training contour-based data were achieved with excellent accuracy (0.99), precision (0.99), recall (0.83), and F-score (0.97), while corresponding values of 0.84, 0.96, 0.83, and 0.9 were achieved for the non-training data. Furthermore, the areas under the ROC curves were above 0.9, validating the accuracy of this test. Conclusion: The proposed framework can reliably identify contour normality/abnormality based upon intra- and inter-structure constraints derived from clinically-approved contours. It also allows physicians to analytically determine the system parameters to fit various clinic requirements (e.g. as-low-as-possible false positives). It has great potential for improving RT work flow. More geometric attributes and training sets will be investigated to improve framework performance in the future.

60 APPLIED LIFE SCIENCES↗

Implementing and evaluating a Gaussian mixture framework for identifying gene function from TnSeq data

The rapid acceleration of microbial genome sequencing increases opportunities to understand bacterial gene function. Unfortunately, only a small proportion of genes have been studied. Recently, TnSeq has been proposed as a cost-effective, highly reliable approach to predict gene functions as a response to changes in a cell’s fitness before-after genomic changes. However, major questions remain about how to best determine whether an observed quantitative change in fitness represents a meaningful change. To address the limitation, we develop a Gaussian mixture model framework for classifying gene function from TnSeq experiments. In order to implement the mixture model, we present the Expectation-Maximization algorithm and a hierarchical Bayesian model sampled using Stan’s Hamiltonian Monte-Carlo sampler. We compare these implementations against the frequentist method used in current TnSeq literature. From simulations and real data produced by E.coli TnSeq experiments, we show that the Bayesian implementation of the Gaussian mixture framework provides the most consistent classification results.

Li, Kevin↗

Data-driven cyber attack detection and mitigation for decentralized wide-area protection and control in smart grids

Modern power systems have already evolved into complicated cyber physical systems (CPS), often referred to as smart grids, due to the continuous expansion of the electrical infrastructure, the augmentation of the number of heterogeneous system components and players, and the consequential application of a diversity of information and telecommunication technologies to facilitate the Wide Area Monitoring, Protection and Control (WAMPAC) of the day-to-day power system operation. Because of the reliance on cyber technologies, WAMPAC, among other critical functions, is prone to various malicious cyber attacks. Successful cyber attacks, especially those sabotage the operation of Bulk Electric System (BES), can cause great financial losses and social panics. Application of conventional IT security solutions is indispensable, but it often turns out to be insufficient to mitigate sophisticated attacks that deploy zero-day vulnerabilities or social engineering tactics. To further improve the resilience of the operation of smart grids when facing cyber attacks, it is desirable to make the WAMPAC functions per se capable of detecting various anomalies automatically, carrying out adaptive activity adjustments in time and thus staying unimpaired even under attack. Most of the existing research efforts attempt to achieve this by adding novel functional modules, such as model-based anomaly detectors, to the legacy centralized WAMPAC functions. In contrast, this dissertation investigates the application of data-driven algorithms in cyber attack detection and mitigation within a decentralized architecture aiming at improving the situational awareness and self-adaptiveness of WAMPAC. First part of the research focuses on the decentralization of System Integrity Protection Scheme (SIPS) with Multi-Agent System (MAS), within which the data-driven anomaly detection and optimal adaptive load shedding are further explored. An algorithm named as Support Vector Machine embedded Layered Decision Tree (SVMLDT) is proposed for the anomaly detection, which provides satisfactory detection accuracy as well as decision-making interpretability. The adaptive load shedding is carried out by every agent individually with dynamic programming. The load shedding relies on the load profile propagation among peer agents and the attack adaptiveness is accomplished by maintaining the historical mean of load shedding proportion. Load shedding only takes place after the consensus pertaining to the anomaly detection is achieved among all interconnected agents and it serves the purpose of mitigating certain cyber attacks. The attack resilience of the decentralized SIPS is evaluated using IEEE 39 bus model. It is shown that, unlike the traditional centralized SIPS, the proposed solution is able to carry out the remedial actions under most Denial of Service (DoS) attacks. The second part investigates the clustering based anomalous behavior detection and peer-assisted mitigation for power system generation control. To reduce the dimensionality of the data, three metrics are designed to interpret the behavior conformity of generator within the same balancing area. Semi-supervised K-means clustering and a density sensitive clustering algorithm based on Hierarchical DBSCAN (HDBSCAN) are both applied in clustering in the 3D feature space. Aiming to mitigate the cyber attacks targeting the generation control commands, a peer-assisted strategy is proposed. When the control commands from control center is detected as anomalous, i.e. either missing or the payload of which have been manipulated, the generating unit utilizes the peer data to infer and estimate a new generation adjustment value as replacement. Linear regression is utilized to obtain the relation of control values received by different generating units, Moving Target Defense (MTD) is adopted during the peer selection and 1-dimensional clustering is performed with the inferred control values, which are followed by the final control value estimation. The mitigation strategy proposed requires that generating units can communicate with each other in a peer-to-peer manner. Evaluation results suggest the efficacy of the proposed solution in counteracting data availability and data integrity attacks targeting the generation controls. However, the strategy stays effective only if less than half of the generating units are compromised and it is not able to mitigate cyber attacks targeting the measurements involved in the generation control.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Algorithmic Patterns for $$\mathcal {H}$$-Matrices on Many-Core Processors

In this work, we consider the reformulation of hierarchical ( \(\mathcal {H}\) ) matrix algorithms for many-core processors with a model implementation on graphics processing units (GPUs). \(\mathcal {H}\) matrices approximate specific dense matrices, e.g., from discretized integral equations or kernel ridge regression, leading to log-linear time complexity in dense matrix–vector products. The parallelization of \(\mathcal {H}\) matrix operations on many-core processors is difficult due to the complex nature of the underlying algorithms. While previous algorithmic advances for many-core hardware focused on accelerating existing \(\mathcal {H}\) matrix CPU implementations by many-core processors, we here aim at totally relying on that processor type. As main contribution, we introduce the necessary parallel algorithmic patterns allowing to map the full \(\mathcal {H}\) matrix construction and the fast matrix–vector product to many-core hardware. In this work, crucial ingredients are space filling curves, parallel tree traversal and batching of linear algebra operations. The resulting model GPU implementation hmglib is the, to the best of the authors knowledge, first entirely GPU-based Open Source \(\mathcal {H}\) matrix library of this kind. We investigate application examples as present in kernel ridge regression, Gaussian Process Regression and kernel-based interpolation. In this context, an in-depth performance analysis and a comparative performance study against a standard multi-core CPU \(\mathcal {H}\) matrix library highlights profound speedups of our many-core parallel approach.

97 MATHEMATICS AND COMPUTING↗

MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization

Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank factors W and H, for the given input matrix A, such that A≈WH. NMF is a useful tool for many applications in different domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of efficient parallel algorithms to solve the problem for big data sets. The main contribution of this work is a new, high-performance parallel computational framework for a broad class of NMF algorithms that iteratively solves alternating non-negative least squares (NLS) subproblems for W and H. It maintains the data and factor matrices in memory (distributed across processors), uses MPI for interprocessor communication, and, in the dense case, provably minimizes communication costs (under mild assumptions). The framework is flexible and able to leverage a variety of NMF and NLS algorithms, including Multiplicative Update, Hierarchical Alternating Least Squares, and Block Principal Pivoting. Our implementation allows us to benchmark and compare different algorithms on massive dense and sparse data matrices of size that spans from few hundreds of millions to billions. We demonstrate the scalability of our algorithm and compare it with baseline implementations, showing significant performance improvements. The code and the datasets used for conducting the experiments are available online.

2D↗

Hierarchical fractional-step approximations and parallel kinetic Monte Carlo algorithms

We present a mathematical framework for constructing and analyzing parallel algorithms for lattice kinetic Monte Carlo (KMC) simulations. The resulting algorithms have the capacity to simulate a wide range of spatio-temporal scales in spatially distributed, non-equilibrium physiochemical processes with complex chemistry and transport micro-mechanisms. Rather than focusing on constructing exactly the stochastic trajectories, our approach relies on approximating the evolution of observables, such as density, coverage, correlations and so on. More specifically, we develop a spatial domain decomposition of the Markov operator (generator) that describes the evolution of all observables according to the kinetic Monte Carlo algorithm. This domain decomposition corresponds to a decomposition of the Markov generator into a hierarchy of operators and can be tailored to specific hierarchical parallel architectures such as multi-core processors or clusters of Graphical Processing Units (GPUs). Based on this operator decomposition, we formulate parallel Fractional step kinetic Monte Carlo algorithms by employing the Trotter Theorem and its randomized variants; these schemes, (a) are partially asynchronous on each fractional step time-window, and (b) are characterized by their communication schedule between processors. The proposed mathematical framework allows us to rigorously justify the numerical and statistical consistency of the proposed algorithms, showing the convergence of our approximating schemes to the original serial KMC. The approach also provides a systematic evaluation of different processor communicating schedules. We carry out a detailed benchmarking of the parallel KMC schemes using available exact solutions, for example, in Ising-type systems and we demonstrate the capabilities of the method to simulate complex spatially distributed reactions at very large scales on GPUs. Finally, we discuss work load balancing between processors and propose a re-balancing scheme based on probabilistic mass transport methods.

97 MATHEMATICS AND COMPUTING↗

DEDICATED FILTER FOR DEFECTS CLUSTERING IN RADIOGRAPHIC IMAGE

Defect clusters such as linear or clustered porosity are in some cases even more important than single flaws. This paper presents two methods of defect clustering and algorithm for calculation of distances between flaws in digital radiographic image. Dedicated lookup table based filter is used for calculation of distances between objects in the specified range. For defect clustering two functions were developed. First one is based on MMD (Minimum Mean Distance) algorithm. Second one uses hierarchical procedures for clustering defects of various types, shapes and size.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

SIGHT: Stacked Integration of Geospatial Hierarchical Typologies for Inferring Building Characteristics

Building characteristics are often absent in building stock datasets, particularly in regions most vulnerable to climate change and requiring effective disaster management strategies. Traditional machine learning approaches, while widely used to predict building attributes, typically neglect the spatial context of the data, leading to less accurate and reliable outcomes. To address these challenges, this paper introduces a novel algorithm, the Stacked Integration of Geospatial Hierarchical Typologies. This algorithm adapts a meta-learning framework to incorporate geospatial context into the predictive modeling process. We demonstrate the utility of the algorithm through two primary use cases: building use type classification and building height prediction. The algorithm consistently achieved or exceeded a 0.94 macro average F1 score across five geographically distinct countries for building use type classification. For building height prediction, it accurately predicted heights with a root mean square error of 3.01 in a comprehensive study using roughly 3.6 million buildings in Japan. These results underscore the benefits of integrating spatial hierarchies into machine learning models, enhancing both predictive accuracy and reliability in geospatial modeling. This work introduces a new algorithm to address the pervasive data sparsity issue in existing building stock datasets.

Adams, Daniel [ORNL] (ORCID:0000000196950577)↗

PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU

This paper introduces Pandora, a parallel algorithm for computing dendrograms, the hierarchical cluster trees for single linkage clustering (SLC). Current parallel approaches construct dendrograms by partitioning a minimum spanning tree and removing edges. However, they struggle with skewed, hard-to-parallelize real-world dendrograms. Consequently, computing dendrograms is the sequential bottleneck in HDBSCAN*[21], a popular SLC variant. Pandora uses recursive tree contraction to address this limitation. Pandora contracts nodes to construct progressively smaller trees. It computes the smallest contracted dendrogram and expands it by inserting contracted edges. This recursive strategy is highly parallel, skew-independent, work-optimal, and well-suited for GPUs and multicores. We develop a performance portable implementation of Pandora in Kokkos[31] and evaluate its performance on multicore CPUs and multi-vendor GPUs (e.g., Nvidia, AMD) for dendrogram construction in HDBSCAN*. Multithreaded Pandora is 2.2x faster than the current best-multithreaded implementation. Our GPU version achieves 6-20x speedup on AMD GPUs and 10-37x on NVIDIA GPUs over multithreaded Pandora. Pandora removes HDBSCAN*’s sequential bottleneck, greatly boosting efficiency, particularly with GPUs.

Sao, Piyush↗