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.

SourceResearch connectionFrom yearThrough year

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

At least 55 records · Page 3

All sources NASA NTRS DOE OSTI

NASA NTRS1994

Multivariate statistical analysis software technologies for astrophysical research involving large data bases

We developed a package to process and analyze the data from the digital version of the Second Palomar Sky Survey. This system, called SKICAT, incorporates the latest in machine learning and expert systems software technology, in order to classify the detected objects objectively and uniformly, and facilitate handling of the enormous data sets from digital sky surveys and other sources. The system provides a powerful, integrated environment for the manipulation and scientific investigation of catalogs from virtually any source. It serves three principal functions: image catalog construction, catalog management, and catalog analysis. Through use of the GID3* Decision Tree artificial induction software, SKICAT automates the process of classifying objects within CCD and digitized plate images. To exploit these catalogs, the system also provides tools to merge them into a large, complete database which may be easily queried and modified when new data or better methods of calibrating or classifying become available. The most innovative feature of SKICAT is the facility it provides to experiment with and apply the latest in machine learning technology to the tasks of catalog construction and analysis. SKICAT provides a unique environment for implementing these tools for any number of future scientific purposes. Initial scientific verification and performance tests have been made using galaxy counts and measurements of galaxy clustering from small subsets of the survey data, and a search for very high redshift quasars. All of the tests were successful, and produced new and interesting scientific results. Attachments to this report give detailed accounts of the technical aspects for multivariate statistical analysis of small and moderate-size data sets, called STATPROG. The package was tested extensively on a number of real scientific applications, and has produced real, published results.

Djorgovski, S. George↗

NASA NTRS1994

Multivariate Statistical Analysis Software Technologies for Astrophysical Research Involving Large Data Bases

We developed a package to process and analyze the data from the digital version of the Second Palomar Sky Survey. This system, called SKICAT, incorporates the latest in machine learning and expert systems software technology, in order to classify the detected objects objectively and uniformly, and facilitate handling of the enormous data sets from digital sky surveys and other sources. The system provides a powerful, integrated environment for the manipulation and scientific investigation of catalogs from virtually any source. It serves three principal functions: image catalog construction, catalog management, and catalog analysis. Through use of the GID3* Decision Tree artificial induction software, SKICAT automates the process of classifying objects within CCD and digitized plate images. To exploit these catalogs, the system also provides tools to merge them into a large, complex database which may be easily queried and modified when new data or better methods of calibrating or classifying become available. The most innovative feature of SKICAT is the facility it provides to experiment with and apply the latest in machine learning technology to the tasks of catalog construction and analysis. SKICAT provides a unique environment for implementing these tools for any number of future scientific purposes. Initial scientific verification and performance tests have been made using galaxy counts and measurements of galaxy clustering from small subsets of the survey data, and a search for very high redshift quasars. All of the tests were successful and produced new and interesting scientific results. Attachments to this report give detailed accounts of the technical aspects of the SKICAT system, and of some of the scientific results achieved to date. We also developed a user-friendly package for multivariate statistical analysis of small and moderate-size data sets, called STATPROG. The package was tested extensively on a number of real scientific applications and has produced real, published results.

Djorgovski, S. G.↗

NASA NTRS1991

Video Pipeline Tree For Scan Conversion Of Triangles

Scenes containing many polygons generated in real time. Video pipeline subsystem having branched structure performs scan conversion of polygons in images generated by computers. New subsystem divides polygons into triangles, each of which processed rapidly in parallel, modular fashion and merged into image.

Robinett, Warren↗

DOE OSTI2020

Geometry-Driven Detection, Tracking and Visual Analysis of Viscous and Gravitational Fingers

Viscous and gravitational flow instabilities cause a displacement front to break up into finger-like fluids. The detection and evolutionary analysis of these fingering instabilities are critical in multiple scientific disciplines such as fluid mechanics and hydrogeology. However, previous detection methods of the viscous and gravitational fingers are based on density thresholding, which provides limited geometric information of the fingers. The geometric structures of fingers and their evolution are important yet little studied in the literature. In this work, we explore the geometric detection and evolution of the fingers in detail to elucidate the dynamics of the instability. Additionally, we propose a ridge voxel detection method to guide the extraction of finger cores from three-dimensional (3D) scalar fields. After skeletonizing finger cores into skeletons, we design a spanning tree based approach to capture how fingers branch spatially from the finger skeletons. Finally, we devise a novel geometric-glyph augmented tracking graph to study how the fingers and their branches grow, merge, and split over time. Feedback from earth scientists demonstrates the usefulness of our approach to performing spatio-temporal geometric analyses of fingers.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2007

Program Merges SAR Data on Terrain and Vegetation Heights

X/P Merge is a computer program that estimates ground-surface elevations and vegetation heights from multiple sets of data acquired by the GeoSAR instrument [a terrain-mapping synthetic-aperture radar (SAR) system that operates in the X and bands]. X/P Merge software combines data from X- and P-band digital elevation models, SAR backscatter magnitudes, and interferometric correlation magnitudes into a simplified set of output topographical maps of ground-surface elevation and tree height.

Siqueira, Paul↗

NASA NTRS2000

A Tool for Automatic Data Distribution for CFD Applications on Structured Grids

Development of HPF versions of NPB and ARC3D has shown that HPF provides an efficient, concise way to express parallelism and to organize data traffic. The use of HPF, as noted in the papers, requires an intimate knowledge of the applications and a detailed analysis of data affinity, data movement, and data granularity. To simplify and accelerate the task of developing HPF versions of existing CFD applications we have designed and implemented ADAPT (Automatic Data Alignment and Placement Tool). ADAPT analyzes a CFD application working on a single structured grid and generates HPF TEMPLATE, (RE)DISTRIBUTION, ALIGNMENT, and INDEPENDENT directives. The directives can be generated on the nest level, subroutine level, application level, or on the application interface level. ADAPT annotates an existing CFD FORTRAN application, performing computations on single or multiple grids. On each grid the application is considered as a sequence of operators, each applied to a set of variables defined in a particular grid domain. ADAPT automatically detects implicit operators (i.e., having data dependences) and explicit operators (without data dependences). For parallelization of an explicit operator ADAPT creates a template for the operator domain, aligns arrays used in the operator with the template, distributes the template, and declares the loops over the distributed dimensions as INDEPENDENT. For parallelization of an implicit operator, the distribution of the operator's domain should be consistent with the operator's dependences. Any dependence between sections distributed on different processors would preclude parallelization if the compiler does not have an ability to pipeline computations. If a data distribution is "orthogonal" to the dependences of an implicit operator, then the loop which implements the operator can be declared as INDEPENDENT. ADAPT starts with an analysis of array index expressions of the loop nests. For each pair of arrays referenced in an assignment statement, it generates an arc in the alignment graph and annotates it with an affinity relation. The template, alignment, and distribution directives for a particular loop nest are then derived from a transitive closure of the affinity relation. A compromise of data distributions in different nests and subroutines is achieved by merging annotated alignment graphs for adjacent nests/stibroutine calls in the nest/call graph of the application in the process called distribution lifting. ADAPT has been implemented as a C++ program running in conjunction with a parallelization tool called CAPTools. ADAPT uses the parse tree, interprocedural analysis and application database generated by CAPTools. It also uses the Directed Graph class, initially implemented in p2d2 (parallel debugger oi distributed programs), and some other classes supporting symbolic computations. ADAPT uses data distribution techniques described. ADAPT was tested with ARC3D and the FT benchmark and has demonstrated a code performance within a factor of 1.5 of handwritten versions.

Frumkin, Michael↗

NASA NTRS2003

A Dynamic Optimization Technique for Siting the NASA-Clark Atlanta Urban Rain Gauge Network (NCURN)

NASA satellites and ground instruments have indicated that cities like Atlanta, Georgia may create or alter rainfall. Scientists speculate that the urban heat island caused by man-made surfaces in cities impact the heat and wind patterns that form clouds and rainfall. However, more conclusive evidence is required to substantiate findings from satellites. NASA, along with scientists at Clark Atlanta University, are implementing a dense, urban rain gauge network in the metropolitan Atlanta area to support a satellite validation program called Studies of PRecipitation Anomalies from Widespread Urban Landuse (SPRAWL). SPRAWL will be conducted during the summer of 2003 to further identify and understand the impact of urban Atlanta on precipitation variability. The paper provides an. overview of SPRAWL, which represents one of the more comprehensive efforts in recent years to focus exclusively on urban-impacted rainfall. The paper also introduces a novel technique for deploying rain gauges for SPRAWL. The deployment of the dense Atlanta network is unique because it utilizes Geographic Information Systems (GIS) and Decision Support Systems (DSS) to optimize deployment of the rain gauges. These computer aided systems consider access to roads, drainage systems, tree cover, and other factors in guiding the deployment of the gauge network. GIS and DSS also provide decision-makers with additional resources and flexibility to make informed decisions while considering numerous factors. Also, the new Atlanta network and SPRAWL provide a unique opportunity to merge the high-resolution, urban rain gauge network with satellite-derived rainfall products to understand how cities are changing rainfall patterns, and possibly climate.

Shepherd, J. Marshall↗

NASA NTRS1990

Nonaxisymmetric instabilities in a slender torus - Two- and three-dimensional simulations

Nonaxisymmetric instabilities in accretion disks are investigated in terms of the slender, non-self-gravitating, ideal fluid torus model. Nonlinear simulations are carried out in two and tree dimensions, using Cartesian-grid finite differencing. The fastest growing instability is the principal mode. This mode saturates with the formation of ellipsoidal density distributions, designated as 'planets'. The simulations provide evidence for nonlinear mode-mode coupling. When several wavenumbers m are unstable, multiple 'planets' form that subsequently merge. Sources of numerical error are examined, and the effects are contrasted with those of the physical instability. The same qualitative evolution is seen in both the two- and the three-dimensional simulations, even though strict vertical hydrostatic equilibrium is no longer rigorously maintained after mode saturation.

Hawley, John F.↗

NASA NTRS2009

Stereo Vision Based Terrain Mapping for Off-Road Autonomous Navigation

Successful off-road autonomous navigation by an unmanned ground vehicle (UGV) requires reliable perception and representation of natural terrain. While perception algorithms are used to detect driving hazards, terrain mapping algorithms are used to represent the detected hazards in a world model a UGV can use to plan safe paths. There are two primary ways to detect driving hazards with perception sensors mounted to a UGV: binary obstacle detection and traversability cost analysis. Binary obstacle detectors label terrain as either traversable or non-traversable, whereas, traversability cost analysis assigns a cost to driving over a discrete patch of terrain. In uncluttered environments where the non-obstacle terrain is equally traversable, binary obstacle detection is sufficient. However, in cluttered environments, some form of traversability cost analysis is necessary. The Jet Propulsion Laboratory (JPL) has explored both approaches using stereo vision systems. A set of binary detectors has been implemented that detect positive obstacles, negative obstacles, tree trunks, tree lines, excessive slope, low overhangs, and water bodies. A compact terrain map is built from each frame of stereo images. The mapping algorithm labels cells that contain obstacles as no-go regions, and encodes terrain elevation, terrain classification, terrain roughness, traversability cost, and a confidence value. The single frame maps are merged into a world map where temporal filtering is applied. In previous papers, we have described our perception algorithms that perform binary obstacle detection. In this paper, we summarize the terrain mapping capabilities that JPL has implemented during several UGV programs over the last decade and discuss some challenges to building terrain maps with stereo range data.

passive perception↗

NASA NTRS2003

A Fast Implementation of the ISOCLUS Algorithm

Unsupervised clustering is a fundamental building block in numerous image processing applications. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method. The algorithm is given a set of n data points in d-dimensional space, an integer k indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute the coordinates of a set of cluster centers in d-space, such that those centers minimize the mean squared distance from each data point to its nearest center. This clustering algorithm is similar to another well-known clustering method, called k-means. One significant feature of ISOCLUS over k-means is that the actual number of clusters reported might be fewer or more than the number supplied as part of the input. The algorithm uses different heuristics to determine whether to merge lor split clusters. As ISOCLUS can run very slowly, particularly on large data sets, there has been a growing .interest in the remote sensing community in computing it efficiently. We have developed a faster implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the k-means algorithm of Kanungo, et al. They showed that, by using a kd-tree data structure for storing the data, it is possible to reduce the running time of k-means. We have adapted this method for the ISOCLUS algorithm, and we show that it is possible to achieve essentially the same results as ISOCLUS on large data sets, but with significantly lower running times. This adaptation involves computing a number of cluster statistics that are needed for ISOCLUS but not for k-means. Both the k-means and ISOCLUS algorithms are based on iterative schemes, in which nearest neighbors are calculated until some convergence criterion is satisfied. Each iteration requires that the nearest center for each data point be computed. Naively, this requires O(kn) time, where k denotes the current number of centers. Traditional techniques for accelerating nearest neighbor searching involve storing the k centers in a data structure. However, because of the iterative nature of the algorithm, this data structure would need to be rebuilt with each new iteration. Our approach is to store the data points in a kd-tree data structure. The assignment of points to nearest neighbors is carried out by a filtering process, which successively eliminates centers that can not possibly be the nearest neighbor for a given region of space. This algorithm is significantly faster, because large groups of data points can be assigned to their nearest center in a single operation. Preliminary results on a number of real Landsat datasets show that our revised ISOCLUS-like scheme runs about twice as fast.

Memarsadeghi, Nargess↗

DOE OSTI2018

Persistent Octrees for Parallel Mesh Refinement Through Non-Volatile Byte-Addressable Memory

We report that octree-based mesh adaptation has enabled simulations of complex physical phenomena. Existing meshing algorithms were proposed with the assumption that computer memory is volatile. Consequently, for failure recovery, the in-core algorithms need to save memory states as snapshots with slow file I/Os. The out-of-core algorithms store octants on disks for persistence. However, neither of them was designed to leverage unique characteristics of non-volatile byte-addressable memory (NVBM). In this paper, we propose a novel data structure Distributed Persistent Merged octree (DPM-octree) for both meshing and in-memory storage of persistent octrees using NVBM. It is a multi-version data structure and can recover from failures using its earlier persistent version stored in NVBM. In addition, we design a feature-directed sampling approach to help dynamically transform the DPM-octree layout for reducing NVBM-induced memory write latency. DPM-octree uses parity trees which are created using erasure coding and stored in NVBM to support low-latency in-memory octant recovery after data loss. DPM-octree has been successfully integrated with Gerris software for simulation of fluid dynamics. Finally, our experimental results with real-world scientific workloads show that DPM-octree scales up to 1.1 billion mesh elements with 1000 processors on the Titan supercomputer.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

A New Member of the Milky Way’s Family Tree: Characterizing the Pontus Merger of Our Galaxy

We study the Pontus structure—a recently discovered merger that brought in ~7 globular clusters in the course of the hierarchical buildup of the Milky Way’s halo. Here, we analyze the stellar population of Pontus and examine (1) its phase-space distribution using the ESA/Gaia data set, (2) its metallicity and chemical abundances (i.e., [Fe/H], [ α /Fe], [Mg/Fe], and [Al/Fe]) using the spectroscopic catalog of APOGEE DR17, and (3) the color–magnitude diagram that shows interesting features, including a possibly double horizontal branch and a small population of blue stragglers. In sum, the Pontus stars show some unique properties that suggest they likely originated from the merging of an independent satellite galaxy; however, future analysis will shed more light on the true nature of this structure. This chemodynamical analysis of Pontus stars is another step forward in our bigger quest to characterize all the merging events of our Milky Way.

79 ASTRONOMY AND ASTROPHYSICS↗

DOE OSTI2021

An automated procedure built on MTEX for reconstructing deformation twin hierarchies from electron backscattered diffraction datasets of heavily twinned microstructures

Here we present a set of algorithms built on the MTEX and MATLAB graph toolboxes for automatic reconstruction of deformation twin hierarchies from Electron Backscatter Diffraction (EBSD) datasets with a focus on developing methods for heavily twinned microstructures (twin fractions >0.5). The algorithms address key issues arising at large strains, mainly: missing twin relationships, grouping of heavily deformed grain fragments into families of similar orientation originating from a single initial grain, identification of parent fragments for large twin volume fractions, and classification of families having twin relationships with multiple families. To facilitate the development of these algorithms, large-grained ultra-high purity α-Ti deformed in compression along two directions is investigated. Graphs are utilized to handle non-local geometric merging and to represent relationships throughout the reconstruction process. When determining if a grain fragment is from the undeformed microstructure, the combined metrics of the fragment's orientation volume fraction in the initial texture and the directed graph centrality measure of out-closeness (the number of nodes reached in a graph from a given node) are essential. To address automation in reconstructing the sequence of twinning and relating fragments originating from a single grain in the initial microstructure, the twin family tree is formulated as a minimum spanning tree emanating from the initial grain family. A scheme constructing the distances associated with twin relationship comprising the spanning tree is developed, and a novel quasi-directional Prim spanning tree algorithm is used to determine the twin family tree. The procedure is demonstrated to significantly improve the level of automation in reconstructing twin hierarchies in heavily twinned microstructure compared to other methodologies in literature. The procedure can readily be applied to analyses of twinning in metals, as well as provide an approach for routinely extracting twin statistics at larger deformation levels than previously possible. Significantly, the procedure is demonstrated to be capable of identifying third generation twinning in α-Ti microstructures.

36 MATERIALS SCIENCE↗

NASA NTRS2018

Variables Influencing RNAV STAR Adherence

In this study we investigated how variables in the aviation domain impact adherence levels of aircraft flying area navigation arrivals with optimized profile descents (RNAV OPDs) (RNAV STARs: aRea NAVigation Standard Terminal Arrival Routes). Variable categories were: weather, aircraft, procedure, and traffic. Non-adherence events analyzed were: miss above, miss below, skip before merge, and skip after merge. Miss below and miss above describe when a flight does not comply vertically with a procedure. Skips refer to a flight leaving a procedure, then returning. Findings of this work reveal that vertical events are most impacted by altitude restriction size, steepness of flight paths, and merging routes. Lateral events were impacted by merging flight conflicts, number of speed restrictions, and the flow rate of the arrival traffic. This study helps increase understanding of how the system is functioning and identifies where procedures are not flexible enough to handle the variability in normal operations.major airports, procedure design, and recommendations for future work.

RNAV OPD↗

DOE OSTI2016

Predicting defect behavior in B2 intermetallics by merging ab initio modeling and machine learning

We present a combination of machine learning and high throughput calculations to predict the points defects behavior in binary intermetallic (A-B) compounds, using as an example systems with the cubic B2 crystal structure (with equiatomic AB stoichiometry). To the best of our knowledge, this work is the first application of machine learning-models for point defect properties. High throughput first principles density functional calculations have been employed to compute intrinsic point defect energies in 100 B2 intermetallic compounds. The systems are classified into two groups: (i) those for which the intrinsic defects are antisites for both A and B rich compositions, and (ii) those for which vacancies are the dominant defect for either or both composition ranges. The data was analyzed by machine learning-techniques using decision tree, and full and reduced multiple additive regression tree (MART) models. Among these three schemes, a reduced MART (r-MART) model using six descriptors (formation energy, minimum and difference of electron densities at the Wigner-Seitz cell boundary, atomic radius difference, maximal atomic number and maximal electronegativity) presents the highest fit (98 %) and predictive (75 %) accuracy. This model is used to predict the defect behavior of other B2 compounds, and it is found that 45 % of the compounds considered feature vacancies as dominant defects for either A or B rich compositions (or both). The ability to predict dominant defect types is important for the modeling of thermodynamic and kinetic properties of intermetallic compounds, and the present results illustrate how this information can be derived using modern tools combining high throughput calculations and data analytics.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2003

A Fast Implementation of the ISOCLUS Algorithm

Unsupervised clustering is a fundamental tool in numerous image processing and remote sensing applications. For example, unsupervised clustering is often used to obtain vegetation maps of an area of interest. This approach is useful when reliable training data are either scarce or expensive, and when relatively little a priori information about the data is available. Unsupervised clustering methods play a significant role in the pursuit of unsupervised classification. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method. The algorithm is given a set of n data points (or samples) in d-dimensional space, an integer k indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute a set of cluster centers in d-space. Although there is no specific optimization criterion, the algorithm is similar in spirit to the well known k-means clustering method in which the objective is to minimize the average squared distance of each point to its nearest center, called the average distortion. One significant feature of ISOCLUS over k-means is that clusters may be merged or split, and so the final number of clusters may be different from the number k supplied as part of the input. This algorithm will be described in later in this paper. The ISOCLUS algorithm can run very slowly, particularly on large data sets. Given its wide use in remote sensing, its efficient computation is an important goal. We have developed a fast implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the k-means algorithm, the filtering algorithm, by Kanungo et al.. They showed that, by storing the data in a kd-tree, it was possible to significantly reduce the running time of k-means. We have adapted this method for the ISOCLUS algorithm. For technical reasons, which are explained later, it is necessary to make a minor modification to the ISOCLUS specification. We provide empirical evidence, on both synthetic and Landsat image data sets, that our algorithm's performance is essentially the same as that of ISOCLUS, but with significantly lower running times. We show that our algorithm runs from 3 to 30 times faster than a straightforward implementation of ISOCLUS. Our adaptation of the filtering algorithm involves the efficient computation of a number of cluster statistics that are needed for ISOCLUS, but not for k-means.

Memarsadeghi, Nargess↗

NASA NTRS2013

Development of Hybrid Product Breakdown Structure for NASA Ground Systems

The Product Breakdown Structure is traditionally a method of identification of the products of a project in a tree structure. It is a tool used to assess, plan, document, and display the equipment requirements for a project. It is part of a product based planning technique, and attempts to break down all components of a project in as much detail as possible, so that nothing is overlooked. The PBS for ground systems at the Kennedy Space Center is being developed to encompass the traditional requirements including the alignment of facility, systems, and components to the organizational hierarchy. The Ground Operations Product Breakdown Structure is a hybrid in nature in that some aspects of a work breakdown structure will be incorporated and merged with the Architecture Concept of Operations, Master Subsystem List, customer interface, and assigned management responsibility. The Ground Operations Product Breakdown Structure needs to be able to identify the flexibility of support differing customers (internal and external) usage of ground support equipment within the Kennedy Space Center launch and processing complex. The development of the Product Breakdown Structure is an iterative activity Initially documenting the organization hierarchy structure and relationships. The Product Breakdown Structure identifies the linkage between the customer program requirements, allocation of system resources, development of design goals, and identification logistics products. As the Product Breakdown Structure progresses the incorporation of the results of requirement planning for the customer occurs identifying facility needs and systems. The mature Product Breakdown Structure is baselined with a hierarchical drawing, the Product Breakdown Structure database, and an associated document identifying the verification of the data through the life cycle of the program/product line. This paper will document, demonstrate, and identify key aspects of the life cycle of a Hybrid Product Breakdown Structure. The purpose is to show how a project management and system engineering approach can be utilized for providing flexible customer service in an evolving manned space flight launch processing environment.

Monaghan, Mark W.↗

NASA NTRS2013

Development of Hybrid Product Breakdown Structure for NASA Ground Systems

Monaghan, Mark W.↗