Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “random search”

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 217 records · Page 12

NEAR: Neural Embeddings for Amino acid Relationships

Protein language models (PLMs) have recently demonstrated potential to supplant classical protein database search methods based on sequence alignment, but are slower than common alignment-based tools and appear to be prone to a high rate of false labeling. Here, we present NEAR, a method based on neural representation learning that is designed to improve both speed and accuracy of search for likely homologs in a large protein sequence database. NEAR’s ResNet embedding model is trained using contrastive learning guided by trusted sequence alignments. It computes per-residue embeddings for target and query protein sequences, and identifies alignment candidates with a pipeline consisting of residue-level k-NN search and a simple neighbor aggregation scheme. Tests on a benchmark consisting of trusted remote homologs and randomly shuffled decoy sequences reveal that NEAR substantially improves accuracy relative to state-of-the-art PLMs, with lower memory requirements and faster embedding and search speed. While these results suggest that the NEAR model may be useful for standalone homology detection with increased sensitivity over standard alignment-based methods, in this manuscript we focus on a more straightforward analysis of the model’s value as a high-speed pre-filter for sensitive annotation. In that context, NEAR is at least 5x faster than the pre-filter currently used in the widely-used profile hidden Markov model (pHMM) search tool HMMER3, and also outperforms the pre-filter used in our fast pHMM tool, nail.

59 BASIC BIOLOGICAL SCIENCES↗

Random Testing and Model Checking: Building a Common Framework for Nondeterministic Exploration

Two popular forms of dynamic analysis, random testing and explicit-state software model checking, are perhaps best viewed as search strategies for exploring the state spaces introduced by nondeterminism in program inputs. We present an approach that enables this nondeterminism to be expressed in the SPIN model checker's PROMELA language, and then lets users generate either model checkers or random testers from a single harness for a tested C program. Our approach makes it easy to compare model checking and random testing for models with precisely the same input ranges and probabilities and allows us to mix random testing with model checking's exhaustive exploration of non-determinism. The PROMELA language, as intended in its design, serves as a convenient notation for expressing nondeterminism and mixing random choices with nondeterministic choices. We present and discuss a comparison of random testing and model checking. The results derive from using our framework to test a C program with an effectively infinite state space, a module in JPL's next Mars rover mission. More generally, we show how the ability of the SPIN model checker to call C code can be used to extend SPIN's features, and hope to inspire others to use the same methods to implement dynamic analyses that can make use of efficient state storage, matching, and backtracking.

dynamic analysis↗

B-Trees and Cache-Oblivious B-Trees with Different-Sized Atomic Keys

Most B-tree articles assume that all $\textit{N}$ keys have the same size $\textit{K}$, that $\textit{f = B/K}$ keys fit in a disk block, and therefore that the search cost is $O(\text{log}_{f+1}N) $ block transfers. When keys have variable size, B-tree operations have no nontrivial performance guarantees, however. This article provides B-tree-like performance guarantees on dictionaries that contain keys of different sizes in a model in which keys must be stored and compared as opaque objects. The resulting atomic-key dictionaries exhibit performance bounds in terms of the average key size and match the bounds when all keys are the same size. Atomic-key dictionaries can be built with minimal modification to the B-tree structure, simply by choosing the pivot keys properly. Further, this article describes both static and dynamic atomic-key dictionaries. In the static case, if there are $\textit{N}$ keys with average size $\textit{K}$, the search cost is $O(\lceil K/B\rceil \text{log}_{1 + \lceil K/B\rceil} N)$ expected transfers. It is not possible to transform these expected bounds into worst-case bounds. The cost to build the tree is $\textit{O(NK)}$ operations and $\textit{O(NK/B)}$ transfers if all keys are presented in sorted order. If not, the cost is the sorting cost. For the dynamic dictionaries, the amortized cost to insert a key $\textit{κ}$ of arbitrary length at an arbitrary rank is dominated by the cost to search for $\textit{κ}$. Specifically, the amortized cost to insert a key $\textit{κ}$ of arbitrary length and random rank is $O(\lceil K/B\rceil log_{1+ \lceil B/K\rceil } N + |κ|/B)$ transfers. A dynamic-programming algorithm is shown for constructing a search tree with minimal expected cost. This article also gives a cache-oblivious static atomic-key B-tree, which achieves the same asymptotic performance as the static B-tree dictionary, mentioned previously. A cache-oblivious data structure or algorithm is not parameterized by the block size $\textit{B}$ or memory size $\textit{M}$ in the memory hierarchy; rather, it is universal, working simultaneously for all possible values of $\textit{B}$ or $\textit{M}$. On a machine with block size $\textit{B}$, if there are $\textit{N}$ keys with average size $\textit{K}$, search operations costs $O(\lceil K/B \rceil log_{1+ \lceil B/K \rceil} N)$ block transfers in expectation. This cache-oblivious layout can be built in $\textit{O(N}\text{log}\textit{(NK))}$ processor operations.

97 MATHEMATICS AND COMPUTING↗

A Comparison of Techniques for Scheduling Fleets of Earth-Observing Satellites

Earth observing satellite (EOS) scheduling is a complex real-world domain representative of a broad class of over-subscription scheduling problems. Over-subscription problems are those where requests for a facility exceed its capacity. These problems arise in a wide variety of NASA and terrestrial domains and are .XI important class of scheduling problems because such facilities often represent large capital investments. We have run experiments comparing multiple variants of the genetic algorithm, hill climbing, simulated annealing, squeaky wheel optimization and iterated sampling on two variants of a realistically-sized model of the EOS scheduling problem. These are implemented as permutation-based methods; methods that search in the space of priority orderings of observation requests and evaluate each permutation by using it to drive a greedy scheduler. Simulated annealing performs best and random mutation operators outperform our squeaky (more intelligent) operator. Furthermore, taking smaller steps towards the end of the search improves performance.

Globus, Al↗

Radical Cystectomy Compared to Combined Modality Treatment for Muscle-Invasive Bladder Cancer: A Systematic Review and Meta-Analysis

Purpose: To perform a comprehensive comparison of overall survival (OS), disease-specific survival (DSS), progression-free survival (PFS), and treatment-related complications between radical cystectomy (RC) and combined modality treatment (CMT—radiation therapy, concurrent chemotherapy, and maximal transurethral resection of bladder tumor) in the setting of muscle-invasive bladder cancer. Methods and Materials: We searched 7 databases (PubMed, Scopus, EMBASE, Proquest, CINAHL, and (ClinicalTrials.gov)) for randomized, controlled trials and prospective and retrospective studies directly comparing RC with CMT from database inception to March 2016. We conducted meta-analyses evaluating OS, DSS, and PFS with hazard ratios (HRs) and 95% confidence intervals (CIs). Results: Nineteen studies evaluating 12,380 subjects were selected. For the 8 studies encompassing 9554 subjects eligible for meta-analyses, we found no difference in OS at 5 years (HR 0.96, favoring CMT, 95% CI 0.72-1.29; P=.778) or 10 years (HR 1.02, favoring cystectomy, 95% CI 0.73-1.42; P=.905). No difference was observed in DSS at 5 years (HR 0.83, favoring radiation, 95% CI 0.54-1.28; P=.390) or 10 years (HR 1.17, favoring cystectomy, 95% CI 0.89-1.55; P=.264), or PFS at 10 years (HR 0.85, favoring CMT, 95% CI 0.43-1.67; P=.639). The cystectomy arms had higher rates of early major complications, whereas rates of minor complications were similar between the 2 treatments. Conclusion: Current meta-analysis reveals no differences in OS, DSS, or PFS between RC and CMT. Further randomized, controlled trials are necessary to identify the optimal treatment for specific patients.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Quantum Search Approaches to Sampling-Based Motion Planning

In this paper, we present a novel formulation of traditional sampling-based motion planners as database-oracle structures that can be solved via quantum search algorithms. We consider two complementary scenarios: for simpler sparse environments, we formulate the Quantum Full Path Search Algorithm (q-FPS), which creates a superposition of full random path solutions, manipulates probability amplitudes with Quantum Amplitude Amplification (QAA), and quantum measures a single obstacle free full path solution. For dense unstructured environments, we formulate the Quantum Rapidly Exploring Random Tree algorithm, q-RRT, that creates quantum superpositions of possible parent-child connections, manipulates probability amplitudes with QAA, and quantum measures a single reachable state, which is added to a tree. As performance depends on the number of oracle calls and the probability of measuring good quantum states, we quantify how these errors factor into the probabilistic completeness properties of the algorithm. We then numerically estimate the expected number of database solutions to provide an approximation of the optimal number of oracle calls in the algorithm. We compare the q-RRT algorithm with a classical implementation and verify quadratic run-time speedup in the largest connected component of a 2D dense random lattice. We conclude by evaluating a proposed approach to limit the expected number of database solutions and thus limit the optimal number of oracle calls to a given number.

97 MATHEMATICS AND COMPUTING↗

Failure prediction and estimation of failure parameters

Machine-learning methods and apparatus are disclosed to determine frictional state or other parameters in an earthquake zone or other failing medium, using acoustic emission, seismic waves, or other detectable indicators of microscopic processes. Predictions of future failures are demonstrated in different regimes. A classifier is trained using time series of acoustic emission data along with historic data of frictional state or failure events. In disclosed examples, random forests and gradient boost trees are used, and grid-search or EGO procedures are used for hyperparameter tuning. Once trained, the classifier can be applied to testing or live data in order to assess a frictional state, assess seismic hazard, or make predictions regarding a future failure event. The technology has been developed in a double direct shear apparatus, but can be widely applied to seismic faults, other terrestrial failures, or failures in man-made structures. Variations are disclosed.

Johnson, Paul Allan↗

Subsurface stress criticality associated with fluid injection and determined using machine learning

Machine-learning methods and apparatus are disclosed to determine critical state or other parameters related to fluid-driven failure of a terrestrial locale impacted by anthropogenic activities such as hydraulic fracturing, hydrocarbon extraction, wastewater disposal, or geothermal harvesting. Acoustic emission, seismic waves, or other detectable indicators of microscopic processes are sensed. A classifier is trained using time series of microscopic data along with corresponding data of critical state or failure events. In disclosed examples, random forests and artificial neural networks are used, and grid-search or EGO procedures are used for hyperparameter tuning. Once trained, the classifier can be applied to live data from a fluid injection locale in order to assess a frictional state, assess seismic hazard, assess permeability, make predictions regarding a future fluid-driven failure event, or drive engineering solutions for mitigation or remediation. Variations are disclosed.

Johnson, Paul Allan↗

Randomized selection on the GPU

We implement here a fast and memory-sparing probabilistic top N selection algorithm on the GPU. To our knowledge, this is the first direct selection in the literature for the GPU. The algorithm proceeds via a probabilistic-guess-and-chcck process searching for the Nth element. It always gives a correct result and always terminates. The use of randomization reduces the amount of data that needs heavy processing, and so reduces the average time required for the algorithm. Probabilistic Las Vegas algorithms of this kind are a form of stochastic optimization and can be well suited to more general parallel processors with limited amounts of fast memory.

97 MATHEMATICS AND COMPUTING↗

ROPE: Recoverable Order-Preserving Embedding of Natural Language

We present a novel Recoverable Order-Preserving Embedding (ROPE) of natural language. ROPE maps natural language passages from sparse concatenated one-hot representations to distributed vector representations of predetermined fixed length. We use Euclidean distance to return search results that are both grammatically and semantically similar. ROPE is based on a series of random projections of distributed word embeddings. We show that our technique typically forms a dictionary with sufficient incoherence such that sparse recovery of the original text is possible. We then show how our embedding allows for efficient and meaningful natural search and retrieval on Microsoft’s COCO dataset and the IMDB Movie Review dataset.

97 MATHEMATICS AND COMPUTING↗

SU-G-TeP3-14: Three-Dimensional Cluster Model in Inhomogeneous Dose Distribution

Purpose: We aim to investigate 3D cluster formation in inhomogeneous dose distribution to search for new models predicting radiation tissue damage and further leading to new optimization paradigm for radiotherapy planning. Methods: The aggregation of higher dose in the organ at risk (OAR) than a preset threshold was chosen as the cluster whose connectivity dictates the cluster structure. Upon the selection of the dose threshold, the fractional density defined as the fraction of voxels in the organ eligible to be part of the cluster was determined according to the dose volume histogram (DVH). A Monte Carlo method was implemented to establish a case pertinent to the corresponding DVH. Ones and zeros were randomly assigned to each OAR voxel with the sampling probability equal to the fractional density. Ten thousand samples were randomly generated to ensure a sufficient number of cluster sets. A recursive cluster searching algorithm was developed to analyze the cluster with various connectivity choices like 1-, 2-, and 3-connectivity. The mean size of the largest cluster (MSLC) from the Monte Carlo samples was taken to be a function of the fractional density. Various OARs from clinical plans were included in the study. Results: Intensive Monte Carlo study demonstrates the inverse relationship between the MSLC and the cluster connectivity as anticipated and the cluster size does not change with fractional density linearly regardless of the connectivity types. An initially-slow-increase to exponential growth transition of the MSLC from low to high density was observed. The cluster sizes were found to vary within a large range and are relatively independent of the OARs. Conclusion: The Monte Carlo study revealed that the cluster size could serve as a suitable index of the tissue damage (percolation cluster) and the clinical outcome of the same DVH might be potentially different.

07 ISOTOPE AND RADIATION SOURCES↗

Search for Neutrino Bursts from Collapsing Stars by Means of the LVD and BUST Detectors

A long-term and stable operation of the LVD and BUST detectors in searches for neutrino bursts from gravitational star collapses is demonstrated, and a random origin of background pulses in the detectors is confirmed thereby. The experimental results obtained by means of the LSD and BUST detectors on February 23, 1987, are considered in detail. The probability for the possible backgroundmimicked coincidences of clusters of pulses recorded in the LSD detector at 2 : 52 UT with a group of correlations of pulses within 1 s between LSD and BUST in the interval from 1 : 45 to 3 : 45 UT is estimated. Also, coincidences of the background pulses in the LVD and BUST detectors over the period of about eight years are analyzed. The results obtained in this way give sufficient grounds to conclude that the cluster of pulses recorded by the LSD detector on February 23, 1987, at 2 : 52 UT and the coincidences of individual pulses in the LSD and BUST detectors are events associated with the gravitational collapse of SN 1987A.

79 ASTRONOMY AND ASTROPHYSICS↗

Coevolutionary Free Lunches

Recent work on the foundations of optimization has begun to uncover its underlying rich structure. In particular, the "No Free Lunch" (NFL) theorems [WM97] state that any two algorithms are equivalent when their performance is averaged across all possible problems. This highlights the need for exploiting problem-specific knowledge to achieve better than random performance. In this paper we present a general framework covering most search scenarios. In addition to the optimization scenarios addressed in the NFL results, this framework covers multi-armed bandit problems and evolution of multiple co-evolving agents. As a particular instance of the latter, it covers "self-play" problems. In these problems the agents work together to produce a champion, who then engages one or more antagonists in a subsequent multi-player game In contrast to the traditional optimization case where the NFL results hold, we show that in self-play there are free lunches: in coevolution some algorithms have better performance than other algorithms, averaged across all possible problems. However in the typical coevolutionary scenarios encountered in biology, where there is no champion, NFL still holds.

Wolpert, David H.↗

Coevolutionary Free Lunches

Recent work on the mathematical foundations of optimization has begun to uncover its rich structure. In particular, the "No Free Lunch" (NFL) theorems state that any two algorithms are equivalent when their performance is averaged across all possible problems. This highlights the need for exploiting problem-specific knowledge to achieve better than random performance. In this paper we present a general framework covering more search scenarios. In addition to the optimization scenarios addressed in the NFL results, this framework covers multi-armed bandit problems and evolution of multiple co-evolving players. As a particular instance of the latter, it covers "self-play" problems. In these problems the set of players work together to produce a champion, who then engages one or more antagonists in a subsequent multi-player game. In contrast to the traditional optimization case where the NFL results hold, we show that in self-play there are free lunches: in coevolution some algorithms have better performance than other algorithms, averaged across all possible problems. We consider the implications of these results to biology where there is no champion.

Wolpert, David H.↗

Terrestrial Single-Station Analog for Constraining the Martian Core and Deep Interior: Implications for InSight

We used a terrestrial single-station seismometer to quantify the uncertainty of InSight (INterior explorations using Seismic Investigations, Geodesy and Heat Transport) data for determining Martian core size. To mimic Martian seismicity, we formed a catalog using 917 terrestrial earthquakes, from which we randomly selected events. We stacked ScS amplitudes on modeled arrival times and searched for where ScS produced coherent seismic amplitudes. A core detection was defined by a coherent peak with small offset between predicted and user-selected arrival times. Iterating the detection algorithm with varying signal-to-noise (SNR) ranges and quantity of events determined the selection frequency of each model and quantified core depth uncertainty. Increasing the quantity of events reduced core depth uncertainty while increasing the recovery rate, while increasing event SNR had little effect. Including ScS2 multiples increased the recovery rate and reduced core depth uncertainty when we used low quantities of events. The most-frequent core depths varied by back azimuth, suggesting our method is sensitive to the presence of mantle heterogeneities. When we added 1° in source distance errors, core depth uncertainty increased by up to 11 km and recovery rates decreased by <5%. Altering epicentral distances by 25% added ~35 km of uncertainty and reduced recovery rates to <50% in some cases. From these experiments, we estimate that if InSight can detect five events with high location precision (<10% epicentral distance errors), that there is at least an 88% chance of core depth recovery using ScS alone with uncertainty in core depth approaching 18 km and decreasing as more events are located.

Marusiak, Angela G.↗

Terrestrial Single-Station Analog for Constraining the Martian Core and Deep Interior: Implications for InSight

We used a terrestrial single-station seismometer to quantify the uncertainty of InSight (INterior explorations using Seismic Investigations, Geodesy and Heat Transport) data for determining Martian core size. To mimic Martian seismicity, we formed a catalog using 917 terrestrial earthquakes, from which we randomly selected events. We stacked ScS amplitudes on modeled arrival times and searched for where ScS produced coherent seismic amplitudes. A core detection was defined by a coherent peak with small offset between predicted and user-selected arrival times. Iterating the detection algorithm with varying signal-to-noise (SNR) ranges and quantity of events determined the selection frequency of each model and quantified core depth uncertainty. Increasing the quantity of events reduced core depth uncertainty while increasing the recovery rate, while increasing event SNR had little effect. Including ScS2 multiples increased the recovery rate and reduced core depth uncertainty when we used low quantities of events. The most-frequent core depths varied by back azimuth, suggesting our method is sensitive to the presence of mantle heterogeneities. When we added 1° in source distance errors, core depth uncertainty increased by up to 11 km and recovery rates decreased by <5%. Altering epicentral distances by 25% added ~35 km of uncertainty and reduced recovery rates to <50% in some cases. From these experiments, we estimate that if InSight can detect five events with high location precision (< 10% epicentral distance errors), that there is at least an 88% chance of core depth recovery using ScS alone with uncertainty in core depth approaching 18 km and decreasing as more events are located.

Angela G Marusiak↗

Precision and Accuracy in PDV and VISAR

This is a technical report discussing our current level of understanding of a wide and varying distribution of uncertainties in velocity results from Photonic Doppler Velocimetry in its application to gas gun experiments. Using propagation of errors methods with statistical averaging of photon number fluctuation in the detected photocurrent and subsequent addition of electronic recording noise, we learn that the velocity uncertainty in VISAR can be written in closed form. For PDV, the non-linear frequency transform and peak fitting methods employed make propagation of errors estimates notoriously more difficult to write down in closed form expect in the limit of constant velocity and low time resolution (large analysis-window width). An alternative method of error propagation in PDV is to use Monte Carlo methods with a simulation of the time domain signal based on results from the spectral domain. A key problem for Monte Carlo estimation for an experiment is a correct estimate of that portion of the time-domain noise associated with the peak-fitting region-of-interesting in the spectral domain. Using short-time Fourier transformation spectral analysis and working with the phase dependent real and imaginary parts allows removal of amplitude-noise cross terms that invariably show up when working with correlation-based methods or FFT power spectra. Estimation of the noise associated with a given spectral region of interest is then possible. At this level of progress, we learn that Monte Carlo trials with random recording noise and initial (uncontrolled) phase yields velocity uncertainties that are not as large as those observed. In a search for additional noise sources, a speckleinterference modulation contribution with off axis rays was investigated, and was found to add a velocity variation beyond that from the recording noise (due to random interference between off axis rays), but in our experiments the speckle modulation precision was not as important as the recording noise precision. But from these investigations we do appreciate that the velocity-uncertainty itself has a wide distribution of values that varies with signal-amplitude modulation (is not a single value). To provide a rough rule of thumb for the velocity uncertainty, we computed the average of the relative standard deviation distributions from 60 recorded traces (with distributions of uncertainties roughly between 0.1 % to 1 % in each trace) and found a mean of the distribution of uncertainties for our experiments is not better than 0.4 % at an analysis window width of 5 ns (although for brief intervals it can be as good as 0.1 %). Further imagination and testing may be needed to reveal other possible hydrodynamics-related sources of velocity error in PDV.

47 OTHER INSTRUMENTATION↗

Search for the Heisenberg spin glass on rewired square lattices with antiferromagnetic interaction

Spin glass (SG) is a typical magnetic system with frozen random spin orientation at low temperatures. The system exhibits rich physical properties, such as infinite number of ground states, memory effect, and aging phenomena. There are two main ingredients considered to be pivotal for the existence of SG behavior, namely, frustration and randomness. For the canonical SG system, frustration is led by the presence of competing interaction between ferromagnetic (FM) and antiferromagnetic (AF) couplings. Previously, Bartolozzi et al. [Phys. Rev. B73, 224419 (2006)], reported the SG properties of the AF Ising spins on scale free network (SFN). It is a new type of SG, different from the canonical one which requires the presence of both FM and AF couplings. In this new system, frustration is purely caused by the topological factor and its randomness is related to the irregular connectvity. Recently, Surungan et. al. [Journal of Physics: Conference Series, 640, 012001 (2015)] reported SG bahavior of AF Heisenberg model on SFN. We further investigate this type of system by studying an AF Heisenberg model on rewired square lattices. We used Replica Exchange algorithm of Monte Carlo Method and calculated the SG order parameter to search for the existence of SG phase.

36 MATERIALS SCIENCE↗