Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Algorithms and data structure”

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 181 records · Page 10

A Synchronized Sensor Array for Remote Monitoring of Avian and Bat Interactions with Offshore Renewable Energy Facilities

Wind energy production in the U.S. is projected to increase to 35% of our nation’s energy by 2050. This substantial increase in the U.S. is only a portion of the global wind industry growth, as many countries strive to reduce greenhouse gas emissions. A major environmental concern and potential market barrier for expansion of wind energy is bird and bat mortality from impacts with turbine blades, towers, and nacelles. Carcass surveys are the standard protocol for quantifying mortality at onshore sites. This method is imperfect, however, due to survey frequency at remote sites, removal of carcasses by scavengers between surveys, searcher efficiency, and other biases as well as delays of days to weeks or more in obtaining information on collision events. Furthermore, carcass surveys are not feasible at offshore wind energy sites. Near-real-time detection and quantification of interaction rates is possible at both onshore and offshore wind facilities using an onboard, integrated sensor package with data transmitted to central processing centers. We developed and experimentally tested an array of sensors that continuously monitors for interactions (including impacts) of birds and bats with wind turbines. The synchronized array includes three sensor nodes: (1) vibration (accelerometers and contact microphones), (2) optical (visual and infrared spectrum cameras), and (3) bioacoustics (acoustic and ultrasonic microphones). Accelerometers and contact acoustic microphones are placed at the root of each blade to detect impact vibrations and sound waves propagating through the structure. On-board data processing algorithms using wavelet analysis detect impact signals exceeding background vibration. Stereo-visual and infrared cameras were placed on the nacelle to allow target tracking, distance, and size calculations. On-board image processing and target detection algorithms identify moving targets within the camera field of view. Bioacoustic recorders monitor vocalizations and echolocations to aid in identifying organisms involved in interactions. Data from all sensors are temporarily stored in ring (i.e., circular) buffers with a duration varying by sensor type. Detection of target presence or impact by any of the sensors can trigger the archiving of data from all buffers for transmission to a central data processing center for evaluation and post-processing. This mitigates the risk of “data mortgages” posed by continual recording and minimizes personnel time required to manually review event data. We first conducted individual component tests at laboratories and field sites in Corvallis and Newport, Oregon, and Seattle and Sequim, Washington. We conducted additional component tests on research wind turbines at the North American Wind Research and Training Center, Mesalands Community College (MCC; General Electric 1.5 MW turbine), New Mexico, and the National Wind Technology Center, National Renewable Energy Laboratory (NREL; Controls Advanced Research Turbines 3 [CART 3] 600 kW Westinghouse turbine), Colorado. We conducted fully integrated system tests at NREL in October 2014 and April 2015. We used only research wind turbines so that we could conduct controlled, experimentally generated impacts using empty and water-filled tennis balls shot from a compressed air cannon on the ground. The approx. 57-140 g tennis balls (depending on water content) were at the upper mass range for bats, but lower mass range for marine birds. Therefore, the ability to detect collisions of most seabirds is likely greater than our experiments demonstrate, but possibly lower for some bats depending on the background signal of a given turbine. Vibration data demonstrated that background signals of operating turbines varied markedly among the CART 3 under normal operation (greatest), GE (moderate), and CART 3 during idle rotation (generator not engaged; least). In total, we measured 63 experimental blade impacts on the two research turbines. Impaction detection was dependent on background signals, position of impact on the blade (a tip strike resulted in the strongest impact signal), and impact kinetics (velocity of ball and whether the ball struck the surface of the blade or the leading edge of the blade struck the ball). Overall detection percentage ranged from 100% for the “quietest” conditions (CART 3 idle rotation), down to 35% for the noisiest (CART 3 normal operation). Impact signals were detected from sensors on more than one blade (i.e., blades other than the blade struck) 50% - 75% of the time. Stereo imaging provided valuable metrics, but increased data processing and equipment cost. Given the cost of cameras with sufficient resolution for target identification, we suggest mounting cameras directly on the blades to continuously view the entire rotor swept area with the fewest number of cameras. Bioacoustic microphones provide taxonomic identification, as well as information on ambient noise levels. They also assist in identifying environmental conditions such as hail storms, high winds, thunder, lightning, etc., that may contribute to a collision or a false positive detection. We demonstrated a proof of concept for an integrated sensor array to detect and identify bird and bat collisions with wind turbines. The next phase of research and development for this system will miniaturize and integrate sensors from all three nodes into a single wireless package that can be attached directly to the blade. This next generation system would use all “smart” sensors capable of onboard data processing to drastically reduce data streams and processing time on a central computer. A provisional patent for the blade mounted system was submitted by Oregon State University and recorded by the U.S. Patent and Trademark Office (application no. 62313028). Eventually, technology and industry advances will allow this low cost monitoring system to be designed into materials during manufacturing so that all turbines could be monitored with either a subset or full suite of sensors. As standard equipment on all commercial turbines, the sensor suite would allow the industry to effectively monitor whether individual turbines were causing mortalities or not and under what circumstances. It would also provide real-time evaluation of mechanical and structural integrity of a turbine via vibration, image, and acoustic data streams, thereby permitting modifications in operation to limit environmental or mechanical damage.

17 WIND ENERGY↗

A Communication-Avoiding 3D LU Factorization Algorithm for Sparse Matrices

We propose a new algorithm to improve the strong scalability of right-looking sparse LU factorization on distributed memory systems. Our 3D sparse LU algorithm uses a three-dimensional MPI process grid, aggressively exploits elimination tree parallelism and trades off increased memory for reduced per-process communication. We also analyze the asymptotic improvements for planar graphs (e.g., from 2D grid or mesh domains) and certain non-planar graphs (specifically for 3D grids and meshes). For planar graphs with n vertices, our algorithm reduces communication volume asymptotically in n by a factor of O{log n} and latency by a factor of O{log n}. For non-planar cases, our algorithm can reduce the per-process communication volume by 3× and latency by O{n^1/3} times. In all cases, the memory needed to achieve these gains is a constant factor. We implemented our algorithm by extending the 2D data structure used in superLU. Our new 3D code achieves speedups up to 27× for planar graphs and up to 3.3× for non-planar graphs over the baseline 2D superLU when run on 24,000 cores of a Cray XC30.

Sao, Piyush↗

PDSLin User Guide

This document describes a software package which implements a parallel hybrid (direct/iterative) linear solver based on the Schur complement method for solving a general sparse linear system of equations. The package is named parallel domain decomposition Schur complement based linear solver, or PDSLin in short. We give a brief description of the algorithm, installation, calling sequences, and data structures of PDSLin.

97 MATHEMATICS AND COMPUTING↗

Labeled trees and the efficient computation of derivations

The effective parallel symbolic computation of operators under composition is discussed. Examples include differential operators under composition and vector fields under the Lie bracket. Data structures consisting of formal linear combinations of rooted labeled trees are discussed. A multiplication on rooted labeled trees is defined, thereby making the set of these data structures into an associative algebra. An algebra homomorphism is defined from the original algebra of operators into this algebra of trees. An algebra homomorphism from the algebra of trees into the algebra of differential operators is then described. The cancellation which occurs when noncommuting operators are expressed in terms of commuting ones occurs naturally when the operators are represented using this data structure. This leads to an algorithm which, for operators which are derivations, speeds up the computation exponentially in the degree of the operator. It is shown that the algebra of trees leads naturally to a parallel version of the algorithm.

Grossman, Robert↗

Automated digital motion-video abstraction - A fuzzy measure approach

This paper addresses a solution to the problem of scene estimation of motion video data in the fuzzy set theoretic framework. Using fuzzy image feature extractors, a new algorithm is developed to compute the change of information in each of two successive frames to classify scenes. This classification process of raw input visual data can be used to establish structure for correlation. The algorithm attempts to fulfill the need for non-linear, frame-accurate access to video data for applications such as video editing and visual document archival/retrieval systems in multimedia environments.

Leigh, Albert B.↗

Certification trails for data structures

Certification trails are a recently introduced and promising approach to fault detection and fault tolerance. The applicability of the certification trail technique is significantly generalized. Previously, certification trails had to be customized to each algorithm application; trails appropriate to wide classes of algorithms were developed. These certification trails are based on common data-structure operations such as those carried out using these sets of operations such as those carried out using balanced binary trees and heaps. Any algorithms using these sets of operations can therefore employ the certification trail method to achieve software fault tolerance. To exemplify the scope of the generalization of the certification trail technique provided, constructions of trails for abstract data types such as priority queues and union-find structures are given. These trails are applicable to any data-structure implementation of the abstract data type. It is also shown that these ideals lead naturally to monitors for data-structure operations.

Sullivan, Gregory F.↗

Development of advanced acreage estimation methods

The development of an accurate and efficient algorithm for analyzing the structure of MSS data, the application of the Akaiki information criterion to mixture models, and a research plan to delineate some of the technical issues and associated tasks in the area of rice scene radiation characterization are discussed. The AMOEBA clustering algorithm is refined and documented.

Guseman, L. F., Jr.↗

Clinical Natural Language Processing for Radiation Oncology: A Review and Practical Primer

Natural language processing (NLP), which aims to convert human language into expressions that can be analyzed by computers, is one of the most rapidly developing and widely used technologies in the field of artificial intelligence. Natural language processing algorithms convert unstructured free text data into structured data that can be extracted and analyzed at scale. In medicine, this unlocking of the rich, expressive data within clinical free text in electronic medical records will help untap the full potential of big data for research and clinical purposes. Recent major NLP algorithmic advances have significantly improved the performance of these algorithms, leading to a surge in academic and industry interest in developing tools to automate information extraction and phenotyping from clinical texts. Thus, these technologies are poised to transform medical research and alter clinical practices in the future. Radiation oncology stands to benefit from NLP algorithms if they are appropriately developed and deployed, as they may enable advances such as automated inclusion of radiation therapy details into cancer registries, discovery of novel insights about cancer care, and improved patient data curation and presentation at the point of care. However, challenges remain before the full value of NLP is realized, such as the plethora of jargon specific to radiation oncology, nonstandard nomenclature, a lack of publicly available labeled data for model development, and interoperability limitations between radiation oncology data silos. Successful development and implementation of high quality and high value NLP models for radiation oncology will require close collaboration between computer scientists and the radiation oncology community. Here, we present a primer on artificial intelligence algorithms in general and NLP algorithms in particular; provide guidance on how to assess the performance of such algorithms; review prior research on NLP algorithms for oncology; and describe future avenues for NLP in radiation oncology research and clinics.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Development of a Genetic Algorithm to Automate Clustering of a Dependency Structure Matrix

Much technology assessment and organization design data exists in Microsoft Excel spreadsheets. Tools are needed to put this data into a form that can be used by design managers to make design decisions. One need is to cluster data that is highly coupled. Tools such as the Dependency Structure Matrix (DSM) and a Genetic Algorithm (GA) can be of great benefit. However, no tool currently combines the DSM and a GA to solve the clustering problem. This paper describes a new software tool that interfaces a GA written as an Excel macro with a DSM in spreadsheet format. The results of several test cases are included to demonstrate how well this new tool works.

Rogers, James L.↗

STUDIES IN ASTRONOMICAL TIME SERIES ANALYSIS. VI. BAYESIAN BLOCK REPRESENTATIONS

This paper addresses the problem of detecting and characterizing local variability in time series and other forms of sequential data. The goal is to identify and characterize statistically significant variations, at the same time suppressing the inevitable corrupting observational errors. We present a simple nonparametric modeling technique and an algorithm implementing it-an improved and generalized version of Bayesian Blocks-that finds the optimal segmentation of the data in the observation interval. The structure of the algorithm allows it to be used in either a real-time trigger mode, or a retrospective mode. Maximum likelihood or marginal posterior functions to measure model fitness are presented for events, binned counts, and measurements at arbitrary times with known error distributions. Problems addressed include those connected with data gaps, variable exposure, extension to piecewise linear and piecewise exponential representations, multivariate time series data, analysis of variance, data on the circle, other data modes, and dispersed data. Simulations provide evidence that the detection efficiency for weak signals is close to a theoretical asymptotic limit derived by Arias-Castro et al. In the spirit of Reproducible Research all of the code and data necessary to reproduce all of the figures in this paper are included as supplementary material.

79 ASTRONOMY AND ASTROPHYSICS↗

Accelerating Time-Varying Hardware Volume Rendering Using TSP Trees and Color-Based Error Metrics

This paper describes a new hardware volume rendering algorithm for time-varying data. The algorithm uses the Time-Space Partitioning (TSP) tree data structure to identify regions within the data that have spatial or temporal coherence. By using this coherence, the rendering algorithm can improve performance when the volume data is larger than the texture memory capacity by decreasing the amount of textures required. This coherence can also allow improved speed by appropriately rendering flat-shaded polygons instead of textured polygons, and by not rendering transparent regions. To reduce the polygonization overhead caused by the use of the hierarchical data structure, we introduce an optimization method using polygon templates. The paper also introduces new color-based error metrics, which more accurately identify coherent regions compared to the earlier scalar-based metrics. By showing experimental results from runs using different data sets and error metrics, we demonstrate that the new methods give substantial improvements in volume rendering performance.

Ellsworth, David↗

GPU-accelerated multitiered iterative phasing algorithm for fluctuation X-ray scattering

The multitiered iterative phasing (MTIP) algorithm is used to determine the biological structures of macromolecules from fluctuation scattering data. It is an iterative algorithm that reconstructs the electron density of the sample by matching the computed fluctuation X-ray scattering data to the external observations, and by simultaneously enforcing constraints in real and Fourier space. This paper presents the first ever MTIP algorithm acceleration efforts on contemporary graphics processing units (GPUs). The Compute Unified Device Architecture (CUDA) programming model is used to accelerate the MTIP algorithm on NVIDIA GPUs. The computational performance of the CUDA-based MTIP algorithm implementation outperforms the CPU-based version by an order of magnitude. Furthermore, the Heterogeneous-Compute Interface for Portability (HIP) runtime APIs are used to demonstrate portability by accelerating the MTIP algorithm across NVIDIA and AMD GPUs.

97 MATHEMATICS AND COMPUTING↗

Studies in Astronomical Time Series Analysis. VI. Bayesian Block Representations

This paper addresses the problem of detecting and characterizing local variability in time series and other forms of sequential data. The goal is to identify and characterize statistically significant variations, at the same time suppressing the inevitable corrupting observational errors. We present a simple nonparametric modeling technique and an algorithm implementing it-an improved and generalized version of Bayesian Blocks [Scargle 1998]-that finds the optimal segmentation of the data in the observation interval. The structure of the algorithm allows it to be used in either a real-time trigger mode, or a retrospective mode. Maximum likelihood or marginal posterior functions to measure model fitness are presented for events, binned counts, and measurements at arbitrary times with known error distributions. Problems addressed include those connected with data gaps, variable exposure, extension to piece- wise linear and piecewise exponential representations, multivariate time series data, analysis of variance, data on the circle, other data modes, and dispersed data. Simulations provide evidence that the detection efficiency for weak signals is close to a theoretical asymptotic limit derived by [Arias-Castro, Donoho and Huo 2003]. In the spirit of Reproducible Research [Donoho et al. (2008)] all of the code and data necessary to reproduce all of the figures in this paper are included as auxiliary material.

signal detection↗

Confidentiality-preserving machine learning algorithms for soft-failure detection in optical communication networks

Automated fault management is at the forefront of next-generation optical communication networks. The increase in complexity of modern networks has triggered the need for programmable and software-driven architectures to support the operation of agile and self-managed systems. In these scenarios, the European Telecommunications Standards Institute zero-touch network and service management approach is imperative. The need for machine learning algorithms to process the large volume of telemetry data brings safety concerns as distributed cloud-computing solutions become the preferred approach for deploying reliable communication network automation. This paper’s contribution is twofold. First, we propose a simple yet effective method to guarantee the confidentiality of the telemetry data based on feature scrambling. The method allows the operation of third-party computational services without direct access to the full content of the collected data. Additionally, the effectiveness of four unsupervised machine learning algorithms for soft-failure detection is evaluated when applied to the scrambled telemetry data. The methods are based on factor analysis, principal component analysis, nonlinear principal component analysis, and singular value decomposition. Most dimensionality reduction algorithms have the common property that they can maintain similar levels of fault classification performance while hiding the data structure from unauthorized access. Evaluations of the proposed algorithms demonstrate this capability.

97 MATHEMATICS AND COMPUTING↗

Timely Reporting of Heavy Hitters Using External Memory

Given an input stream S of size N, a Φ-heavy hitter is an item that occurs at least ΦN times in S. The problem of finding heavy-hitters is extensively studied in the database literature. In this work, we study a real-time heavy-hitters variant in which an element must be reported shortly after we see its T = Φ N-th occurrence (and hence it becomes a heavy hitter). We call this the Timely Event Detection (TED) Problem. The TED problem models the needs of many real-world monitoring systems, which demand accurate (i.e., no false negatives) and timely reporting of all events from large, high-speed streams with a low reporting threshold (high sensitivity). Like the classic heavy-hitters problem, solving the TED problem without false-positives requires large space (Ω (N) words). Thus in-RAM heavy-hitters algorithms typically sacrifice accuracy (i.e., allow false positives), sensitivity, or timeliness (i.e., use multiple passes). We show how to adapt heavy-hitters algorithms to external memory to solve the TED problem on large high-speed streams while guaranteeing accuracy, sensitivity, and timeliness. Our data structures are limited only by I/O-bandwidth (not latency) and support a tunable tradeoff between reporting delay and I/O overhead. With a small bounded reporting delay, our algorithms incur only a logarithmic I/O overhead. We implement and validate our data structures empirically using the Firehose streaming benchmark. Multi-threaded versions of our structures can scale to process 11M observations per second before becoming CPU bound. In comparison, a naive adaptation of the standard heavy-hitters algorithm to external memory would be limited by the storage device’s random I/O throughput, i.e., ≈100K observations per second.

97 MATHEMATICS AND COMPUTING↗

Protein folds vs. protein folding: Differing questions, different challenges

We report protein fold prediction using deep-learning artificial intelligence (AI) has transformed the field of protein structure prediction. By combining physical and geometric constraints—and especially patterns extracted from the Protein Data Bank —these machine learning algorithms can predict protein structures at or near atomic resolution and do so in seconds. Today, these computational methods have now solved more than 200 million protein structures, which are accessible from the AlphaFold Protein Structure Database. This accomplishment seems all the more remarkable because few thought it possible or saw it coming. Deservedly, deep-learning AI was named Science magazine’s 2021 “breakthrough of the year”. Clearly, deep-learning AI represents a major advance in protein fold prediction.

54 ENVIRONMENTAL SCIENCES↗

A single-tree algorithm to compute the Euclidean minimum spanning tree on GPUs

Computing the Euclidean minimum spanning tree (Emst) is a computationally demanding step of many algorithms. While work-efficient serial and multithreaded algorithms for computing Emst are known, designing an efficient GPU algorithm is challenging due to a complex branching structure, data dependencies, and load imbalances. In this paper, we propose a single-tree $Bor\mathring{u}vka$-based algorithm for computing Emst on GPUs. We use an efficient nearest neighbor algorithm and reduce the number of the required distance calculations by avoiding traversing subtrees with leaf nodes in the same component. The developed algorithms are implemented in a performance portable way using ArborX, an open-source geometric search library based on the Kokkos framework. We evaluate the proposed algorithm on various 2D and 3D datasets, show and compare it with the current state-of-the-art open-source CPU implementations. We demonstrate 4-24 × speedup over the fastest multi-threaded implementation. We prove the portability of our implementation by providing results on a variety of hardware: AMD EPYC 7763, Nvidia A100 and AMD MI250X. We show scalability of the implementation, computing Emst for 37 million 3D cosmological dataset in under a 0.5 second on a single A100 Nvidia GPU.

Prokopenko, Andrey↗