Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “clustering 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 325 records · Page 18
All sourcesNASA NTRSDOE OSTI
NASA NTRS2019

ASCot, the NASA Analogy Software Cost Tool Suite: expanding our estimation horizons

The NASA Analogy Software Costing Tool Suite (ASCoT) consists of a cluster-based analogy estimator for estimating software development effort, a K-Nearest Neighbors (KNN) analogy estimator for estimating effort and delivered lines of code, a simple regression-based cost estimating relationship (CER) model that estimates cost in dollars, and a probabilistic version of COCOMO II. In this paper we document the analogy algorithms as well as summarize the results of the performance of the KNN and the principle components (PCA) cluster analogy models. KNN performance is assessed by varying the number of inputs and number of neighbors. Four different clustering methods: K-means, Spectral Clustering, Hierarchical Clustering, and Principle Components Analysis (PCA), and their respective evaluation criterion are described in detail. The comparative performance of all four estimation models is assessed using magnitude of relative error (MRE) measurements.

Menzies, Tim↗
NASA NTRS1999

SAGE: The Self-Adaptive Grid Code

The multi-dimensional self-adaptive grid code, SAGE, is an important tool in the field of computational fluid dynamics (CFD). It provides an efficient method to improve the accuracy of flow solutions while simultaneously reducing computer processing time. Briefly, SAGE enhances an initial computational grid by redistributing the mesh points into more appropriate locations. The movement of these points is driven by an equal-error-distribution algorithm that utilizes the relationship between high flow gradients and excessive solution errors. The method also provides a balance between clustering points in the high gradient regions and maintaining the smoothness and continuity of the adapted grid, The latest version, Version 3, includes the ability to change the boundaries of a given grid to more efficiently enclose flow structures and provides alternative redistribution algorithms.

Davies, Carol B.↗
NASA NTRS1992

An analysis of the structure of gamma ray burst time histories

If gamma-ray bursts (GRB) arise from a small number of distinctly different physical phenomena, then this might be revealed by a clustering of time profile characteristics into a small number of groups. A 'spike' counting algorithm was applied to 107 GRB profiles. Graphs of spike frequency and spike amplitude versus burst intensity and duration are presented. So far, no evidence of grouping is seen.

Lestrade, John Patrick↗
NASA NTRS1993

A revised catalog of CfA1 galaxy groups in the Virgo/Great Attractor flow field

A new identification of groups and clusters in the CfA1 Catalog of Huchra et al. is presented, using a percolation algorithm to identify density enhancements. It is shown that in the resulting catalog, contamination by interlopers is significantly reduced. The Schechter luminosity function is redetermined, including the Malmquist bias.

Nolthenius, Richard↗
NASA NTRS2000

Dynamic Load-Balancing for Distributed Heterogeneous Computing of Parallel CFD Problems

The developed methodology is aimed at improving the efficiency of executing block-structured algorithms on parallel, distributed, heterogeneous computers. The basic approach of these algorithms is to divide the flow domain into many sub- domains called blocks, and solve the governing equations over these blocks. Dynamic load balancing problem is defined as the efficient distribution of the blocks among the available processors over a period of several hours of computations. In environments with computers of different architecture, operating systems, CPU speed, memory size, load, and network speed, balancing the loads and managing the communication between processors becomes crucial. Load balancing software tools for mutually dependent parallel processes have been created to efficiently utilize an advanced computation environment and algorithms. These tools are dynamic in nature because of the chances in the computer environment during execution time. More recently, these tools were extended to a second operating system: NT. In this paper, the problems associated with this application will be discussed. Also, the developed algorithms were combined with the load sharing capability of LSF to efficiently utilize workstation clusters for parallel computing. Finally, results will be presented on running a NASA based code ADPAC to demonstrate the developed tools for dynamic load balancing.

Ecer, A.↗
NASA NTRS2004

Proceedings from the 2nd International Symposium on Formation Flying Missions and Technologies

Topics discussed include: The Stellar Imager (SI) "Vision Mission"; First Formation Flying Demonstration Mission Including on Flight Nulling; Formation Flying X-ray Telescope in L2 Orbit; SPECS: The Kilometer-baseline Far-IR Interferometer in NASA's Space Science Roadmap Presentation; A Tight Formation for Along-track SAR Interferometry; Realization of the Solar Power Satellite using the Formation Flying Solar Reflector; SIMBOL-X : Formation Flying for High-Energy Astrophysics; High Precision Optical Metrology for DARWIN; Close Formation Flight of Micro-Satellites for SAR Interferometry; Station-Keeping Requirements for Astronomical Imaging with Constellations of Free-Flying Collectors; Closed-Loop Control of Formation Flying Satellites; Formation Control for the MAXIM Mission; Precision Formation Keeping at L2 Using the Autonomous Formation Flying Sensor; Robust Control of Multiple Spacecraft Formation Flying; Virtual Rigid Body (VRB) Satellite Formation Control: Stable Mode-Switching and Cross-Coupling; Electromagnetic Formation Flight (EMFF) System Design, Mission Capabilities, and Testbed Development; Navigation Algorithms for Formation Flying Missions; Use of Formation Flying Small Satellites Incorporating OISL's in a Tandem Cluster Mission; Semimajor Axis Estimation Strategies; Relative Attitude Determination of Earth Orbiting Formations Using GPS Receivers; Analysis of Formation Flying in Eccentric Orbits Using Linearized Equations of Relative Motion; Conservative Analytical Collision Probabilities for Orbital Formation Flying; Equations of Motion and Stability of Two Spacecraft in Formation at the Earth/Moon Triangular Libration Points; Formations Near the Libration Points: Design Strategies Using Natural and Non-Natural Ares; An Overview of the Formation and Attitude Control System for the Terrestrial Planet Finder Formation Flying Interferometer; GVE-Based Dynamics and Control for Formation Flying Spacecraft; GNC System Design for a New Concept of X-Ray Distributed Telescope; GNC System for the Deployment and Fine Control of the DARWIN Free-Flying Interferometer; Formation Algorithm and Simulation Testbed; and PLATFORM: A Formation Flying, RvD and Robotic Validation Test-bench.

Source record↗
NASA NTRS1989

Image segmentation by iterative parallel region growing and splitting

The spatially constrained clustering (SCC) iterative parallel region-growing technique is applied to image analysis. The SCC algorithm is implemented on the massively parallel processor at NASA Goddard. Most previous region-growing approaches have the drawback that the segmentation produced depends on the order in which portions of the image are processed. The ideal solution to this problem (merging only the single most similar pair of spatially adjacent regions in the image in each iteration) becomes impractical except for very small images, even on a massively parallel computer. The SCC algorithm overcomes these problems by performing, in parallel, the best merge within each of a set of local, possibly overlapping, subimages. A region-splitting stage is also incorporated into the algorithm, but experiments show that region splitting generally does not improve segmentation results. The SCC algorithm has been tested on various imagery data, and test results for a Landsat TM image are summarized.

Tilton, James C.↗
NASA NTRS1993

A revised catalog of CfA galaxy groups in the Virgo/Great Attractor flow field

A new identification of groups and clusters in the CfAl Catalog of Huchra, et al. (1983) is presented, using a percolation algorithm to identify density enhancements. The procedure differs from that of the original Geller and Huchra (1983; GH) catalog in several important respects; galaxy distances are calculated from the Virgo-Great Attractor flow model of Faber and Burnstein (1988), the adopted distance linkage criteria is only approx. 1/4 as large as in the Geller and Huchra catalog, the sky link relation is taken from Nolthenius and White (1987), correction for interstellar extinction is included, and 'by-hand' adjustments to group memberships are made in the complex regions of Virgo/Coma I/Ursa Major and Coma/A1367 (to allow for varying group velocity dispersions and to trim unphysical 'spider arms'). Since flow model distances are poorly determined in these same regions, available distances from the IR Tully-Fisher planetary nebula luminosity function and surface brightness resolution methods are adopted if possible.

Nolthenius, Richard↗
NASA NTRS1998

High Performance Parallel Architectures

Traditional remote sensing instruments are multispectral, where observations are collected at a few different spectral bands. Recently, many hyperspectral instruments, that can collect observations at hundreds of bands, have been operational. Furthermore, there have been ongoing research efforts on ultraspectral instruments that can produce observations at thousands of spectral bands. While these remote sensing technology developments hold great promise for new findings in the area of Earth and space science, they present many challenges. These include the need for faster processing of such increased data volumes, and methods for data reduction. Dimension Reduction is a spectral transformation, aimed at concentrating the vital information and discarding redundant data. One such transformation, which is widely used in remote sensing, is the Principal Components Analysis (PCA). This report summarizes our progress on the development of a parallel PCA and its implementation on two Beowulf cluster configuration; one with fast Ethernet switch and the other with a Myrinet interconnection. Details of the implementation and performance results, for typical sets of multispectral and hyperspectral NASA remote sensing data, are presented and analyzed based on the algorithm requirements and the underlying machine configuration. It will be shown that the PCA application is quite challenging and hard to scale on Ethernet-based clusters. However, the measurements also show that a high- performance interconnection network, such as Myrinet, better matches the high communication demand of PCA and can lead to a more efficient PCA execution.

El-Ghazawi, Tarek↗
NASA NTRS2009

A Local Scalable Distributed Expectation Maximization Algorithm for Large Peer-to-Peer Networks

This paper offers a local distributed algorithm for expectation maximization in large peer-to-peer environments. The algorithm can be used for a variety of well-known data mining tasks in a distributed environment such as clustering, anomaly detection, target tracking to name a few. This technology is crucial for many emerging peer-to-peer applications for bioinformatics, astronomy, social networking, sensor networks and web mining. Centralizing all or some of the data for building global models is impractical in such peer-to-peer environments because of the large number of data sources, the asynchronous nature of the peer-to-peer networks, and dynamic nature of the data/network. The distributed algorithm we have developed in this paper is provably-correct i.e. it converges to the same result compared to a similar centralized algorithm and can automatically adapt to changes to the data and the network. We show that the communication overhead of the algorithm is very low due to its local nature. This monitoring algorithm is then used as a feedback loop to sample data from the network and rebuild the model when it is outdated. We present thorough experimental results to verify our theoretical claims.

Bhaduri, Kanishka↗
NASA NTRS1992

Fuzzy Set Methods for Object Recognition in Space Applications

Progress on the following four tasks is described: (1) fuzzy set based decision methodologies; (2) membership calculation; (3) clustering methods (including derivation of pose estimation parameters), and (4) acquisition of images and testing of algorithms.

Keller, James M.↗
NASA NTRS2000

Performance Assessment of OVERFLOW on Distributed Computing Environment

The aerodynamic computer code, OVERFLOW, with a multi-zone overset grid feature, has been parallelized to enhance its performance on distributed and shared memory paradigms. Practical application benchmarks have been set to assess the efficiency of code's parallelism on high-performance architectures. The code's performance has also been experimented with in the context of the distributed computing paradigm on distant computer resources using the Information Power Grid (IPG) toolkit, Globus. Two parallel versions of the code, namely OVERFLOW-MPI and -MLP, have developed around the natural coarse grained parallelism inherent in a multi-zonal domain decomposition paradigm. The algorithm invokes a strategy that forms a number of groups, each consisting of a zone, a cluster of zones and/or a partition of a large zone. Each group can be thought of as a process with one or multithreads assigned to it and that all groups run in parallel. The -MPI version of the code uses explicit message-passing based on the standard MPI library for sending and receiving interzonal boundary data across processors. The -MLP version employs no message-passing paradigm; the boundary data is transferred through the shared memory. The -MPI code is suited for both distributed and shared memory architectures, while the -MLP code can only be used on shared memory platforms. The IPG applications are implemented by the -MPI code using the Globus toolkit. While a computational task is distributed across multiple computer resources, the parallelism can be explored on each resource alone. Performance studies are achieved with some practical aerodynamic problems with complex geometries, consisting of 2.5 up to 33 million grid points and a large number of zonal blocks. The computations were executed primarily on SGI Origin 2000 multiprocessors and on the Cray T3E. OVERFLOW's IPG applications are carried out on NASA homogeneous metacomputing machines located at three sites, Ames, Langley and Glenn. Plans for the future will exploit the distributed parallel computing capability on various homogeneous and heterogeneous resources and large scale benchmarks. Alternative IPG toolkits will be used along with sophisticated zonal grouping strategies to minimize the communication time across the computer resources.

Djomehri, M. Jahed↗
NASA NTRS2011

Compact near-IR and mid-IR cavity ring down spectroscopy device

This invention relates to a compact cavity ring down spectrometer for detection and measurement of trace species in a sample gas using a tunable solid-state continuous-wave mid-infrared PPLN OPO laser or a tunable low-power solid-state continuous wave near-infrared diode laser with an algorithm for reducing the periodic noise in the voltage decay signal which subjects the data to cluster analysis or by averaging of the interquartile range of the data.

Miller, J. Houston↗
NASA NTRS2017

Interpretable Categorization of Heterogeneous Time Series Data

We analyze data from simulated aircraft encounters to validate and inform the development of a prototype aircraft collision avoidance system. The high-dimensional and heterogeneous time series dataset is analyzed to discover properties of near mid-air collisions (NMACs) and categorize the NMAC encounters. Domain experts use these properties to better organize and understand NMAC occurrences. Existing solutions either are not capable of handling high-dimensional and heterogeneous time series datasets or do not provide explanations that are interpretable by a domain expert. The latter is critical to the acceptance and deployment of safety-critical systems. To address this gap, we propose grammar-based decision trees along with a learning algorithm. Our approach extends decision trees with a grammar framework for classifying heterogeneous time series data. A context-free grammar is used to derive decision expressions that are interpretable, application-specific, and support heterogeneous data types. In addition to classification, we show how grammar-based decision trees can also be used for categorization, which is a combination of clustering and generating interpretable explanations for each cluster. We apply grammar-based decision trees to a simulated aircraft encounter dataset and evaluate the performance of four variants of our learning algorithm. The best algorithm is used to analyze and categorize near mid-air collisions in the aircraft encounter dataset. We describe each discovered category in detail and discuss its relevance to aircraft collision avoidance.

Drones↗
NASA NTRS2006

UWB Tracking Algorithms: AOA and TDOA

Ultra-Wideband (UWB) tracking prototype systems are currently under development at NASA Johnson Space Center for various applications on space exploration. For long range applications, a two-cluster Angle of Arrival (AOA) tracking method is employed for implementation of the tracking system; for close-in applications, a Time Difference of Arrival (TDOA) positioning methodology is exploited. Both AOA and TDOA are chosen to utilize the achievable fine time resolution of UWB signals. This talk presents a brief introduction to AOA and TDOA methodologies. The theoretical analysis of these two algorithms reveal the affecting parameters impact on the tracking resolution. For the AOA algorithm, simulations show that a tracking resolution less than 0.5% of the range can be achieved with the current achievable time resolution of UWB signals. For the TDOA algorithm used in close-in applications, simulations show that the (sub-inch) high tracking resolution is achieved with a chosen tracking baseline configuration. The analytical and simulated results provide insightful guidance for the UWB tracking system design.

Ni, Jianjun David↗
NASA NTRS2024

Smallsat 2024 - Starling Cubesat Swarm Technology Demonstration Flight Results

The Starling swarm of four 6U CubeSats launched in July 2023 to test four key technologies to enable future swarm missions: 1) Mobile Ad-Hoc Networking (MANET) over a crosslink radio network 2) Autonomous onboard decision-making for operations 3) Optical-based absolute and relative navigation 4) Autonomous maneuver planning and execution The Starling team implemented the Better Approach to Mobile Ad-hoc Networking (B.A.T.M.A.N.) protocol to automatically manage the crosslink network of four satellites. The B.A.T.M.A.N. protocol uses a decentralized approach to managing a multi-hop mesh network of devices, in this case, a satellite swarm. The four satellites were able to successfully establish a network at multiple data rates and demonstrate file transfer and command issuance between spacecraft over the network. Starling incorporated Distributed Spacecraft Autonomy's (DSA) software to demonstrate onboard decision-making. The DSA software takes L1/L2 band GPS measurements and uses them to estimate the relative Total Electron Count (TEC) in the ionosphere. The onboard software then determines if there are any features of interest and provides that information to the other satellites over the crosslink network. The swarm of satellites then reaches a consensus on the optimal TEC observation strategy and adjusts its measurement collection tactics autonomously. The Starling Formation-Flying Optical Experiment (StarFOX), produced by Stanford's Space Rendezvous Laboratory, uses the onboard star trackers to collect images of the other swarm spacecraft and produce angles-only navigation estimates. This system is envisioned to be valuable in applications in which Global Navigation Satellite Systems (GNSS) are not available, such as in cis-lunar or deep space. StarFOX successfully applied its algorithms to multiple simultaneous spacecraft targets using the star tracker imagery. Finally, Starling used Emergent Space's Cluster Flight Application (CFA) software suite for the Reconfiguration and Orbit Maintenance Experiments Onboard (ROMEO) demonstration of autonomously planning and executing propulsive maneuvers. Large swarms will need to be able to maintain formation requirements with minimal operator involvement, especially as the size of the swarm scales up. Results from the ROMEO experiment are presented. Starling is funded by the Small Spacecraft Technology (SST) program out of NASA's Space Technology Mission Directorate (STMD).

distributed systems↗
NASA NTRS1995

Stereo-Based Region-Growing using String Matching

We present a novel stereo algorithm based on a coarse texture segmentation preprocessing phase. Matching is performed using a string comparison. Matching sub-strings correspond to matching sequences of textures. Inter-scanline clustering of matching sub-strings yields regions of matching texture. The shape of these regions yield information concerning object's height, width and azimuthal position relative to the camera pair. Hence, rather than the standard dense depth map, the output of this algorithm is a segmentation of objects in the scene. Such a format is useful for the integration of stereo with other sensor modalities on a mobile robotic platform. It is also useful for localization; the height and width of a detected object may be used for landmark recognition, while depth and relative azimuthal location determine pose. The algorithm does not rely on the monotonicity of order of image primitives. Occlusions, exposures, and foreshortening effects are not problematic. The algorithm can deal with certain types of transparencies. It is computationally efficient, and very amenable to parallel implementation. Further, the epipolar constraints may be relaxed to some small but significant degree. A version of the algorithm has been implemented and tested on various types of images. It performs best on random dot stereograms, on images with easily filtered backgrounds (as in synthetic images), and on real scenes with uncontrived backgrounds.

Mandelbaum, Robert↗
NASA NTRS1990

SIAM Conference on Parallel Processing for Scientific Computing, 4th, Chicago, IL, Dec. 11-13, 1989, Proceedings

Attention is given to such topics as an evaluation of block algorithm variants in LAPACK and presents a large-grain parallel sparse system solver, a multiprocessor method for the solution of the generalized Eigenvalue problem on an interval, and a parallel QR algorithm for iterative subspace methods on the CM2. A discussion of numerical methods includes the topics of asynchronous numerical solutions of PDEs on parallel computers, parallel homotopy curve tracking on a hypercube, and solving Navier-Stokes equations on the Cedar Multi-Cluster system. A section on differential equations includes a discussion of a six-color procedure for the parallel solution of elliptic systems using the finite quadtree structure, data parallel algorithms for the finite element method, and domain decomposition methods in aerodynamics. Topics dealing with massively parallel computing include hypercube vs. 2-dimensional meshes and massively parallel computation of conservation laws. Performance and tools are also discussed.

Dongarra, Jack↗