Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Merge tree”

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 37 records · Page 2

An improved classification tree analysis of high cost modules based upon an axiomatic definition of complexity

Identification of high cost modules has been viewed as one mechanism to improve overall system reliability, since such modules tend to produce more than their share of problems. A decision tree model was used to identify such modules. In this current paper, a previously developed axiomatic model of program complexity is merged with the previously developed decision tree process for an improvement in the ability to identify such modules. This improvement was tested using data from the NASA Software Engineering Laboratory.

Tian, Jianhui↗

Convergence Rates for Empirical Estimation of Binary Classification Bounds

Bounding the best achievable error probability for binary classification problems is relevant to many applications including machine learning, signal processing, and information theory. Many bounds on the Bayes binary classification error rate depend on information divergences between the pair of class distributions. Recently, the Henze–Penrose (HP) divergence has been proposed for bounding classification error probability. We consider the problem of empirically estimating the HP-divergence from random samples. We derive a bound on the convergence rate for the Friedman–Rafsky (FR) estimator of the HP-divergence, which is related to a multivariate runs statistic for testing between two distributions. The FR estimator is derived from a multicolored Euclidean minimal spanning tree (MST) that spans the merged samples. We obtain a concentration inequality for the Friedman–Rafsky estimator of the Henze–Penrose divergence. We validate our results experimentally and illustrate their application to real datasets.

97 MATHEMATICS AND COMPUTING↗

Scalable Contour Tree Computation by Data Parallel Peak Pruning

As data sets grow to exascale, automated data analysis and visualization are increasingly important, to intermediate human understanding and to reduce demands on disk storage via in situ analysis. Trends in architecture of high performance computing systems necessitate analysis algorithms to make effective use of combinations of massively multicore and distributed systems. One of the principal analytic tools is the contour tree, which analyses relationships between contours to identify features of more than local importance. Unfortunately, the predominant algorithms for computing the contour tree are explicitly serial, and founded on serial metaphors, which has limited the scalability of this form of analysis. While there is some work on distributed contour tree computation, and separately on hybrid GPU-CPU computation, there is no efficient algorithm with strong formal guarantees on performance allied with fast practical performance. Furthermore, we report the first shared SMP algorithm for fully parallel contour tree computation, with formal guarantees of O(lg V lg t) parallel steps and O(V lg V) work for data with V samples and t contour tree supernodes, and implementations with more than 30× parallel speed up on both CPU using TBB and GPU using Thrust and up 70× speed up compared to the serial sweep and merge algorithm.

97 MATHEMATICS AND COMPUTING↗

An automated approach to the design of decision tree classifiers

The classification of large dimensional data sets arising from the merging of remote sensing data with more traditional forms of ancillary data is considered. Decision tree classification, a popular approach to the problem, is characterized by the property that samples are subjected to a sequence of decision rules before they are assigned to a unique class. An automated technique for effective decision tree design which relies only on apriori statistics is presented. This procedure utilizes a set of two dimensional canonical transforms and Bayes table look-up decision rules. An optimal design at each node is derived based on the associated decision table. A procedure for computing the global probability of correct classfication is also provided. An example is given in which class statistics obtained from an actual LANDSAT scene are used as input to the program. The resulting decision tree design has an associated probability of correct classification of .76 compared to the theoretically optimum .79 probability of correct classification associated with a full dimensional Bayes classifier. Recommendations for future research are included.

Argentiero, P.↗

Merging IceSAT GLAS and Terra MODIS Data in Order to Derive Forest Type Specific Tree Heights in the Central Siberian Boreal Forest

Mapping of boreal forest's type, biomass, and other structural parameters are critical for understanding of the boreal forest's significance in the carbon cycle, its response to and impact on global climate change. We believe the nature of the forest structure information available from MISR and GLAS can be used to help identify forest type, age class, and estimate above ground biomass levels beyond that now possible with MODIS alone. The ground measurements will be used to develop relationships between remote sensing observables and forest characteristics and provide new information for understanding forest changes with respect to environmental change. Lidar is a laser altimeter that determines the distance from the instrument to the physical surface by measuring the time elapsed between the pulse emission and the reflected return. Other studies have shown that the returned signal may identify multiple returns originating from trees, building and other objects and permits the calculation of their height. Studies using field data have shown that lidar data can provide estimates of structural parameters such as biomass, stand volume and leaf area index and allows remarkable differentiation between primary and secondary forest. NASA's IceSAT Geoscience Laser Altimeter System (GLAS) was launched in January 2003 and collected data during February and September of that year. This study used data acquired over our study sites in central Siberia to examine the GLAS signal as a source of forest height and other structural characteristics. The purpose of our Siberia project is to improve forest cover maps and produce above-ground biomass maps of the boreal forest in Northern Eurasia from MODIS by incorporating structural information inherent in the Terra MISR and ICESAT Geoscience Laser Altimeter System (GLAS) instruments. A number of forest cover classifications exist for the boreal forest. We believe the limiting factor in these products is the lack of structural information, particularly in the vertical dimension. The emphasis of this project is to improve upon satellite maps of boreal forest structure parameters (i.e. height and biomass) using temporal, multi-angle, and vertical profile information of GLAS data. The existing and near future lidar data is useful for demonstrating these techniques and pursuing current estimates. Future lidar missions may be several years in the future, so we will work other new data sets that may aide in biomass estimates such as ALOS PALSAR We will continue this work to produce an accurate map of current above ground forest phytomass/carbon storage possible for the study area. We plan to develop, test, and integrate remote sensing methods for extracting forest canopy structure measures. We are compiling our field measurements and will compare them with the remote sensing methods where possible. We also be able to produce a realistic error bound on the remotely sensed carbon estimates.

Ranson, K. Jon↗

A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm

Consider a scalar field f : M → R, where M is a triangulated simplicial mesh in R d . A level set, or contour, at value v is a connected component of f –1 (v). As v is changed, these contours change topology, merge into each other, or split. Contour trees are concise representations of f that track this contour behavior. The vertices of these trees are the critical points of f, where the gradient is zero. The edges represent changes in the topology of contours. It is a fundamental data structure in data analysis and visualization, and there is significant previous work (both theoretical and practical) on algorithms for constructing contour trees. Suppose M has n vertices, N facets, and t critical points. A classic result of Carr, Snoeyink, and Axen (2000) gives an algorithm that takes O(n log n+Nα(N)) time (where α(·) is the inverse Ackermann function). A further improvement to O(t log t + N) time was given by Chiang et al. All these algorithms involve a global sort of the critical points, a significant computational bottleneck. Unfortunately, lower bounds of Ω(t log t) also exist. We present the first algorithm that can avoid the global sort and has a refined time complexity that depends on the contour tree structure. Intuitively, if the tree is short and fat, we get significant improvements in running time. For a partition of the contour tree into a set of descending paths, P, our algorithm runs in O($\Sigma$ pϵP |p| log |p| + tα(t) + N). This is at most O(t log D + N), where D is the diameter of the contour tree. Moreover, it is O(tα(t) + N) for balanced trees, a significant improvement over the previous complexity. Our algorithm requires numerous ideas: partitioning the contour tree into join and split trees, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. There is a crucial use of a family of binomial heaps to maintain priorities, ensuring that any comparison made is between comparable nodes of the contour tree. We also prove lower bounds showing that the $\Sigma$ pϵP |p| log |p| complexity is inherent to computing contour trees.

97 MATHEMATICS AND COMPUTING↗

Extended Subadiabatic Layer in Simulations of Overshooting Convection

We present numerical simulations of hydrodynamic overshooting convection in local Cartesian domains. We find that a substantial fraction of the lower part of the convection zone (CZ) is stably stratified according to the Schwarzschild criterion while the enthalpy flux is outward directed. This occurs when the heat conduction profile at the bottom of the CZ is smoothly varying, based either on a Kramers-like opacity prescription as a function of temperature and density or a static profile of a similar shape. We show that the subadiabatic layer arises due to nonlocal energy transport by buoyantly driven downflows in the upper parts of the CZ. Analysis of the force balance of the upflows and downflows confirms that convection is driven by cooling at the surface. We find that the commonly used prescription for the convective enthalpy flux being proportional to the negative entropy gradient does not hold in the stably stratified layers where the flux is positive. We demonstrate the existence of a non-gradient contribution to the enthalpy flux, which is estimated to be important throughout the convective layer. A quantitative analysis of downflows indicates a transition from a tree-like structure where smaller downdrafts merge into larger ones in the upper parts to a structure in the deeper parts where a height-independent number of strong downdrafts persist. This change of flow topology occurs when a substantial subadiabatic layer is present in the lower part of the CZ.

79 ASTRONOMY AND ASTROPHYSICS↗

Wide Range SET Pulse Measurement

A method for measuring a wide range of SET pulses is demonstrated. Use of dynamic logic, faster than ordinary CMOS, allows capture of short pulses. A weighted binning of SET lengths allows measurement of a wide range of pulse lengths with compact circuitry. A pulse-length-conservative pulse combiner tree routes SETs from combinational logic to the measurement circuit, allowing SET measurements in circuits that cannot easily be arranged in long chains. The method is applied to add-multiplex combinational logic, and to an array of NFET routing switches, at .35 micron. Pulses are captured in a chain of Domino Logic AND gates. Propagation through the chain is frozen on the trailing edge by dropping low the second "enable" input to the AND gates. Capacitive loading is increased in the latter stages to create an approximately logarithmic weighted binning, so that a broad range of pulse lengths can be captured with a 10 stage capture chain. Simulations show pulses can be captured which are 1/5th the length of those typically captured with leading edge triggered latch methods, and less than the length of those captured with a trailing edge latch method. After capture, the pulse pattern is transferred to an SEU protected shift register for readout. 64 instances of each of two types of logic are used as targets. One is a full adder with a 4 to 1 mux on its inputs. The other is a 4 x 4 NFET routing matrix. The outputs are passed through buffered XNOR comparators to identify pulses, which are merged in a buffered not-nand (OR) tree designed to avoid pulse absorption as much as possible. The output from each of the two test circuits are input into separate pulse measurement circuits. Test inputs were provided so that the circuit could be bench tested and calibrated. A third SET measurement circuit with no inputs was used to judge the contribution from direct hits on the measurement circuit. Heavy ions were used with an LET range from 12 to 176. At LET of 21 and below, the very small number of SETs were not significantly higher in the test over the control circuits. At higher LET the test circuit SETs are one or two orders of magnitude greater than for the control circuit. The NFET circuit produces more and slightly longer SETs as expected. But the differences do not appear to be significant enough to modify strategies now used to avoid capture of SETs in chips such as FPGAs. Complete data and graphs will be in the full paper / presentation. In the summary figure below left, NOCL is the reference circuit without any input, and number of stages triggered is plotted. Simulation at right shows the smallest pulse captured (stage 2) at about 300 ps. Our conclusion is that the method is promising, but that improvements in the merge network are desirable before applying in a deep submicron process

Shuler, Robert L.↗

Shape Estimation for Elongated Deformable Object using B-spline Chained Multiple Random Matrices Model

In this paper, a B-spline chained multiple random matrix models (RMMs) representation is proposed to model geometric characteristics of an elongated deformable object. The hyper degrees of freedom structure of the elongated deformable object make its shape estimation challenging. Based on the likelihood function of the proposed B-spline chained multiple RMMs, an expectation-maximization (EM) method is derived to estimate the shape of the elongated deformable object. A split and merge method based on the Euclidean minimum spanning tree (EMST) is proposed to provide initialization for the EM algorithm. The proposed algorithm is evaluated for the shape estimation of the elongated deformable objects in scenarios, such as the static rope with various configurations (including configurations with intersection), the continuous manipulation of a rope and a plastic tube, and the assembly of two plastic tubes. The execution time is computed and the accuracy of the shape estimation results is evaluated based on the comparisons between the estimated width values and its ground-truth, and the intersection over union (IoU) metric.

Gang Yao↗

The Global LAnd Surface Satellite (GLASS) evapotranspiration product Version 5.0: Algorithm development and preliminary validation

An accurate estimation of spatially and temporally continuous global terrestrial evapotranspiration (ET) is essential in the assessment of surface energy, water and carbon cycles. The Global LAnd Surface Satellite (GLASS) ET product Version 4.0 (v4.0) based on the Bayesian model averaging (BMA) method was generated to estimate global terrestrial ET. However, certain uncertainty for the GLASS ET product v4.0 limits its application. In this study, we introduced the deep neural networks (DNN) merging framework to improve terrestrial ET estimation for GLASS ET product Version 5.0 (v5.0) generation by integrating five satellite-derived ET products [Moderate Resolution Imaging Spectroradiometer (MODIS) ET product (MOD16), Shuttleworth–Wallace dual-source ET product (SW), Priestley–Taylor-based ET product (PT-JPL), modified satellite-based Priestley–Taylor ET product (MS-PT) and simple hybrid ET product (SIM)]. We compared the performance of DNN method against other merging methods, including GLASS ET algorithm v4.0 (BMA), the gradient boosting regression tree (GBRT) method and the random forest (RF) method, based on 195 global eddy covariance (EC) flux towers covering observations from 2000 through 2015. Validations indicated that the DNN had the highest accuracy among four merging methods across different land cover types, yielding the highest average determination coefficients (R 2 , 0.62), root-mean-squared-error (RMSE, 24.1 W/m 2 ) and Kling–Gupta efficiency (KGE, 0.77) with a of 99% confidence interval. Compared with GLASS ET algorithm v4.0, the DNN improved on the R 2 by approximately 7% (p < 0.01) and the KGE by 10%. Based on the DNN, we then generated 8-day GLASS ET product v5.0 globally with a 1 km spatial resolution from 2001 to 2015 driven by GLASS vegetation and surface net radiation (R n ) datasets and Modern-Era Retrospective Analysis for Research and Applications, Version 2 (MERRA2) datasets. Finally, this global terrestrial ET product provides a valuable dataset for monitoring regional and global water resources and environmental changes.

54 ENVIRONMENTAL SCIENCES↗

Evaluation of Programming Language-Aware Diffs for Improving Developer Productivity

As the number of supported platforms for SNL software increases, so do the testing requirements. This increases the total time spent between when a developer submits code for testing, and when tests are completed. This in turn leads developers to hold off submitting code for testing, meaning that when code is ready for testing there's a lot more of it. This increases the likelihood of merge conflicts which the developer must resolve by hand -- because someone else touched the files near the lines the developer touched. Current text-based diff tools often have trouble resolving conflicts in these cases. Work in Europe and Japan has demonstrated that, using programming language aware diff tools (e.g., using the abstract syntax tree (AST) a compiler might generate) can reduce the manual labor necessary to resolve merge conflicts. These techniques can detect code blocks which have moved, as opposed than current text-based diff tools, which only detect insertions / deletions of text blocks. In this study, we evaluate one such tool, GumTree, and see how effective it is as a replacement for traditional text-based diff approaches.

97 MATHEMATICS AND COMPUTING↗

Building Halo Merger Trees from the Q Continuum Simulation

Cosmological N-body simulations rank among the most computationally intensive efforts today. A key challenge is the analysis of structure, substructure, and the merger history for many billions of compact particle clusters, called halos. Effectively representing the merging history of halos is essential for many galaxy formation models used to generate synthetic sky catalogs, an important application of modern cosmological simulations. Generating realistic mock catalogs requires computing the halo formation history from simulations with large volumes and billions of halos over many time steps, taking hundreds of terabytes of analysis data. We present fast parallel algorithms for producing halo merger trees and tracking halo substructure from a single-level, density-based clustering algorithm. Merger trees are created from analyzing the halo-particle membership function in adjacent snapshots, and substructure is identified by tracking the "cores" of merging halos - sets of particles near the halo center. Core tracking is performed after creating merger trees and uses the relationships found during tree construction to associate substructures with hosts. The algorithms are implemented with MPI and evaluated on a Cray XK7 supercomputer using up to 16,384 processes on data from HACC, a modern cosmological simulation framework. We present results for creating merger trees from 101 analysis snapshots taken from the Q Continuum, a large volume, high mass resolution, cosmological simulation evolving half a trillion particles.

79 ASTRONOMY AND ASTROPHYSICS↗

Efficient Encoding and Rendering of Time-Varying Volume Data

Visualization of time-varying volumetric data sets, which may be obtained from numerical simulations or sensing instruments, provides scientists insights into the detailed dynamics of the phenomenon under study. This paper describes a coherent solution based on quantization, coupled with octree and difference encoding for visualizing time-varying volumetric data. Quantization is used to attain voxel-level compression and may have a significant influence on the performance of the subsequent encoding and visualization steps. Octree encoding is used for spatial domain compression, and difference encoding for temporal domain compression. In essence, neighboring voxels may be fused into macro voxels if they have similar values, and subtrees at consecutive time steps may be merged if they are identical. The software rendering process is tailored according to the tree structures and the volume visualization process. With the tree representation, selective rendering may be performed very efficiently. Additionally, the I/O costs are reduced. With these combined savings, a higher level of user interactivity is achieved. We have studied a variety of time-varying volume datasets, performed encoding based on data statistics, and optimized the rendering calculations wherever possible. Preliminary tests on workstations have shown in many cases tremendous reduction by as high as 90% in both storage space and inter-frame delay.

CODING↗

Constructing high-fidelity halo merger trees in abacussummit

ABSTRACT Tracking the formation and evolution of dark matter haloes is a critical aspect of any analysis of cosmological N-body simulations. In particular, the mass assembly of a halo and its progenitors, encapsulated in the form of its merger tree, serves as a fundamental input for constructing semi-analytic models of galaxy formation and, more generally, for building mock catalogues that emulate galaxy surveys. We present an algorithm for constructing halo merger trees from abacussummit, the largest suite of cosmological N-body simulations performed to date consisting of nearly 60 trillion particles, and which has been designed to meet the Cosmological Simulation Requirements of the Dark Energy Spectroscopic Instrument (DESI) survey. Our method tracks the cores of haloes to determine associations between objects across multiple time slices, yielding lists of halo progenitors and descendants for the several tens of billions of haloes identified across the entire suite. We present an application of these merger trees as a means to enhance the fidelity of abacussummit halo catalogues by flagging and ‘merging’ haloes deemed to exhibit non-monotonic past merger histories. We show that this cleaning technique identifies portions of the halo population that have been deblended due to choices made by the halo finder, but which could have feasibly been part of larger aggregate systems. We demonstrate that by cleaning halo catalogues in this post-processing step, we remove potentially unphysical features in the default halo catalogues, leaving behind a more robust halo population that can be used to create highly accurate mock galaxy realizations from abacussummit.

79 ASTRONOMY AND ASTROPHYSICS↗

Software for Checking Statecharts

HiVy is a software tool set that enables verification through model checking of designs represented as finite-state machines or statecharts. HiVy provides automated translation of (1) statecharts created by use of the MathWorks Stateflow program to (2) Promela, the input language of the Spin model checker, which can then be used to verify, or trace logical errors in, distributed software systems. HiVy can operate directly on Stateflow models, or its abstract syntax of hierarchical sequential automata (HSA) can be used independently as an intermediate format for translation to Promela. In a typical design application, HiVy parses and reformats Stateflow model file data using the programs SfParse and sf2hsa, respectively. If the parsing effort is successful, an abstract syntax tree is delivered into a file named with the extension .hsa. If the design comprises several model files, they may be merged into one .hsa file before translation into Promela. Stateflow scope is preserved, and name clashes are avoided in the merge process. The HiVy program hsa2pr translates the model from the intermediate HSA format into Promela. Additionally, HiVy provides through translation a list of all statechart model propositions that are the means for formalizing linear temporal logic (LTL) properties about the model for Spin verification.

Pingree, Paula↗

DeepSAT: A Deep Learning Approach to Tree-Cover Delineation in 1-m NAIP Imagery for the Continental United States

High resolution tree cover classification maps are needed to increase the accuracy of current land ecosystem and climate model outputs. Limited studies are in place that demonstrates the state-of-the-art in deriving very high resolution (VHR) tree cover products. In addition, most methods heavily rely on commercial softwares that are difficult to scale given the region of study (e.g. continents to globe). Complexities in present approaches relate to (a) scalability of the algorithm, (b) large image data processing (compute and memory intensive), (c) computational cost, (d) massively parallel architecture, and (e) machine learning automation. In addition, VHR satellite datasets are of the order of terabytes and features extracted from these datasets are of the order of petabytes. In our present study, we have acquired the National Agriculture Imagery Program (NAIP) dataset for the Continental United States at a spatial resolution of 1-m. This data comes as image tiles (a total of quarter million image scenes with ~60 million pixels) and has a total size of ~65 terabytes for a single acquisition. Features extracted from the entire dataset would amount to ~8-10 petabytes. In our proposed approach, we have implemented a novel semi-automated machine learning algorithm rooted on the principles of "deep learning" to delineate the percentage of tree cover. Using the NASA Earth Exchange (NEX) initiative, we have developed an end-to-end architecture by integrating a segmentation module based on Statistical Region Merging, a classification algorithm using Deep Belief Network and a structured prediction algorithm using Conditional Random Fields to integrate the results from the segmentation and classification modules to create per-pixel class labels. The training process is scaled up using the power of GPUs and the prediction is scaled to quarter million NAIP tiles spanning the whole of Continental United States using the NEX HPC supercomputing cluster. An initial pilot over the state of California spanning a total of 11,095 NAIP tiles covering a total geographical area of 163,696 sq. miles has produced true positive rates of around 88 percent for fragmented forests and 74 percent for urban tree cover areas, with false positive rates lower than 2 percent for both landscapes.

Imagery↗

A High Performance Computing Approach to Tree Cover Delineation in 1-m NAIP Imagery Using a Probabilistic Learning Framework

Tree cover delineation is a useful instrument in deriving Above Ground Biomass (AGB) density estimates from Very High Resolution (VHR) airborne imagery data. Numerous algorithms have been designed to address this problem, but most of them do not scale to these datasets, which are of the order of terabytes. In this paper, we present a semi-automated probabilistic framework for the segmentation and classification of 1-m National Agriculture Imagery Program (NAIP) for tree-cover delineation for the whole of Continental United States, using a High Performance Computing Architecture. Classification is performed using a multi-layer Feedforward Backpropagation Neural Network and segmentation is performed using a Statistical Region Merging algorithm. The results from the classification and segmentation algorithms are then consolidated into a structured prediction framework using a discriminative undirected probabilistic graphical model based on Conditional Random Field, which helps in capturing the higher order contextual dependencies between neighboring pixels. Once the final probability maps are generated, the framework is updated and re-trained by relabeling misclassified image patches. This leads to a significant improvement in the true positive rates and reduction in false positive rates. The tree cover maps were generated for the whole state of California, spanning a total of 11,095 NAIP tiles covering a total geographical area of 163,696 sq. miles. The framework produced true positive rates of around 88% for fragmented forests and 74% for urban tree cover areas, with false positive rates lower than 2% for both landscapes. Comparative studies with the National Land Cover Data (NLCD) algorithm and the LiDAR canopy height model (CHM) showed the effectiveness of our framework for generating accurate high-resolution tree-cover maps.

Segments↗

Pinacate-gran Desierto Region, Mexico: SIR-A Data Analysis

Radar images (SIR-A) from the Columbia space shuttle were used to assess the radar returns of terrain shaped by volcanic, aeolian, and fluvial processes in northwest Sonora. Field studies and photointerpretation show that sand dunes are poorly imaged by SIR-A, in contrast to SEASAT, evidently a consequence of the greater SIR-A incidence angle; star dunes are visible only as small bright spots representing merging arms at dune apices which may act as corner reflectors. Desert grasses and bushes (approx. 2 m high) have little effect on radar brightness. Only larger trees with woody trunks approx. 0.5 m across are effective radar reflectors; their presence contributes to radar bright zones along some arroyos. The radar brightness of lava flows decreases with surface roughness and presence of mantling windblown sediments and weathering products; however, old uplifted (faulted) flows are of equal brightness to fresh, unmantled aa flows. Maar craters display circular patterns of varying radar brightness which represent a combination of geometry, slope, and distribution of surface materials. Some radar bright rings in the Pinacates resemble craters on radar but are observed to be playas encircled by trees.

Christensen, P.↗