Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “theoretical and computational techniques”

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 757 records · Page 42
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

27 AlNMR chemical shift of Al(OH)$^{-}_{4}$ calculated from first principles: Assessment of error cancellation in chemically distinct reference and target systems

Predicting accurate nuclear magnetic resonance chemical shieldings relies upon cancellation of different types of errors between the theoretically calculated shielding constant of the analyte of interest and the reference. Often, the intrinsic error in computed shieldings due to basis sets, approximations in the Hamiltonian, description of the wave function, and dynamic effects is nearly identical between the analyte and reference, yet if the electronic structure or sensitivity to local environment differs dramatically, this cannot be taken for granted. Detailed prior work has examined the octahedral trivalent cation Al(H 2 O)$^{3+}_{6}$, accounting for ab initio intrinsic errors. However, the use of this species as a reference for the chemically distinct tetrahedral anion Al(OH)$^{-}_{4}$ requires an understanding of how these errors cancel, in order to define the limits of accurately predicting 27 Al chemical shielding in Al(OH)$^{-}_{4}$. In this work, we estimate the absolute shielding of the 27 Al nucleus in Al(OH)$^{-}_{4}$ at the coupled cluster level (515.1± 5.3 ppm). Shielding sensitivity to the choice of method approximation and atomic basis sets used has been evaluated. Solvent and thermal effects are assessed through ensemble averaging techniques using ab-initio molecular dynamics. The contribution of each type of intrinsic error is assessed for the Al(H 2 O)$^{3+}_{6}$ and Al(OH)$^{-}_{4}$ ions, revealing significant differences that fundamentally hamper the ability to accurately calculate the 27 Al chemical shift of Al(OH)$^{-}_{4}$ from first principles.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2022

Predicting Phonon-Induced Spin Decoherence from First Principles: Colossal Spin Renormalization in Condensed Matter

Developing a microscopic understanding of spin decoherence is essential to advancing quantum technologies. Electron spin decoherence due to atomic vibrations (phonons) plays a special role as it sets an intrinsic limit to the performance of spin-based quantum devices. Two main sources of phonon-induced spin decoherence—the Elliott-Yafet and Dyakonov-Perel mechanisms—have distinct physical origins and theoretical treatments. Here, we show calculations that unify their modeling and enable accurate predictions of spin relaxation and precession in semiconductors. We compute the phonon-dressed vertex of the spin-spin correlation function with a treatment analogous to the calculation of the anomalous electron magnetic moment in QED. We find that the vertex correction provides a giant renormalization of the electron spin dynamics in solids, greater by many orders of magnitude than the corresponding correction from photons in vacuum. Finally, our Letter demonstrates a general approach for quantitative analysis of spin decoherence in materials, advancing the quest for spin-based quantum technologies.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2024

Exploring the Feasibility of INCONEL® ALLOY 740H® for Power Plant Headers: Integrating Machine Learning with Computational Fluid Dynamics (CFD)

This keynote presentation explores the behavior of headers—essential components of pipeline systems—using ANSYS simulation software and machine learning techniques. The study aims to predict the thermal and mechanical performance of headers under diverse conditions through both steady-state and transient simulations. We investigate critical parameters such as heat transfer coefficient, fluid velocity, and temperature to optimize header design. Conducted as part of a DOE project led by NCAT in collaboration with UNC Charlotte, this research encompasses multiple key topics. The initial section focuses on the behavior of header systems under steady-state conditions using ANSYS simulation. It underscores the importance of headers in industrial infrastructure, especially in the energy sector, and examines the implications of material selection and flow direction on heat transfer dynamics. Methodologically, we employ Computational Fluid Dynamics (CFD) analysis through ANSYS, detailing the development of models, material properties, geometry specifications, boundary conditions, and meshing strategies. Our simulations explore various operational parameters, including temperature and mass flow rates, crucial for predicting heat transfer coefficients and enhancing header design. Results from the study include parametric investigations into mesh sensitivity, viscosity model evaluations, and the effects of heat transfer locations, all validated against theoretical calculations. We conclude with insights on mesh optimization, the suitability of viscosity models, and recommendations for future research aimed at improving header system efficiency and sustainability in industrial applications.

20 FOSSIL-FUELED POWER PLANTS↗
NASA NTRS2007

Efficient Implementation of an Optimal Interpolator for Large Spatial Data Sets

Interpolating scattered data points is a problem of wide ranging interest. A number of approaches for interpolation have been proposed both from theoretical domains such as computational geometry and in applications' fields such as geostatistics. Our motivation arises from geological and mining applications. In many instances data can be costly to compute and are available only at nonuniformly scattered positions. Because of the high cost of collecting measurements, high accuracy is required in the interpolants. One of the most popular interpolation methods in this field is called ordinary kriging. It is popular because it is a best linear unbiased estimator. The price for its statistical optimality is that the estimator is computationally very expensive. This is because the value of each interpolant is given by the solution of a large dense linear system. In practice, kriging problems have been solved approximately by restricting the domain to a small local neighborhood of points that lie near the query point. Determining the proper size for this neighborhood is a solved by ad hoc methods, and it has been shown that this approach leads to undesirable discontinuities in the interpolant. Recently a more principled approach to approximating kriging has been proposed based on a technique called covariance tapering. This process achieves its efficiency by replacing the large dense kriging system with a much sparser linear system. This technique has been applied to a restriction of our problem, called simple kriging, which is not unbiased for general data sets. In this paper we generalize these results by showing how to apply covariance tapering to the more general problem of ordinary kriging. Through experimentation we demonstrate the space and time efficiency and accuracy of approximating ordinary kriging through the use of covariance tapering combined with iterative methods for solving large sparse systems. We demonstrate our approach on large data sizes arising both from synthetic sources and from real applications.

Memarsadeghi, Nargess↗
DOE OSTI2023

Quantum error mitigation by Pauli check sandwiching

Abstract We describe and analyze an error mitigation technique that uses multiple pairs of parity checks to detect the presence of errors. Each pair of checks uses one ancilla qubit to detect a component of the error operator and represents one layer of the technique. We build on the results on extended flag gadgets and put it on a firm theoretical foundation. We prove that this technique can recover the noiseless state under the assumption of noise not affecting the checks. The method does not incur any encoding overhead and instead chooses the checks based on the input circuit. We provide an algorithm for obtaining such checks for an arbitrary target circuit. Since the method applies to any circuit and input state, it can be easily combined with other error mitigation techniques. We evaluate the performance of the proposed methods using extensive numerical simulations on 1850 random input circuits composed of Clifford gates and non-Clifford single-qubit rotations, a class of circuits encompassing most commonly considered variational algorithm circuits. We observe average improvements in fidelity of 34 percentage points with six layers of checks.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

DSPS: Differentiable stellar population synthesis

ABSTRACT Models of stellar population synthesis (SPS) are the fundamental tool that relates the physical properties of a galaxy to its spectral energy distribution (SED). In this paper, we present DSPS: a python package for SPS. All of the functionality in DSPS is implemented natively in the JAX library for automatic differentiation, and so our predictions for galaxy photometry are fully differentiable, and directly inherit the performance benefits of JAX, including portability onto GPUs. DSPS also implements several novel features, such as i) a flexible empirical model for stellar metallicity that incorporates correlations with stellar age, ii) support for the Diffstar model that provides a physically-motivated connection between the star formation history of a galaxy (SFH) and the mass assembly of its underlying dark matter halo. We detail a set of theoretical techniques for using autodiff to calculate gradients of predictions for galaxy SEDs with respect to SPS parameters that control a range of physical effects, including SFH, stellar metallicity, nebular emission, and dust attenuation. When forward modelling the colours of a synthetic galaxy population, we find that DSPS can provide a factor of 5 speed-up over standard SPS codes on a CPU, and a factor of 300-400 on a modern GPU. When coupled with gradient-based techniques for optimization and inference, DSPS makes it practical to conduct expansive likelihood analyses of simulation-based models of the galaxy–halo connection that fully forward model galaxy spectra and photometry.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2021

A multi-dimensional Child–Langmuir law for any diode geometry

While prior theoretical studies of multi-dimensional space-charge limited current (SCLC) assumed emission from a small patch on infinite electrodes, none have considered emission from an entire finite electrode. In this paper, we apply variational calculus (VC) and conformal mapping, which have previously been used to derive analytic solutions for SCLC density (SCLCD) for nonplanar one-dimensional geometries, to obtain mathematical relationships for any multi-dimensional macroscopic diode with finite cathode and anode. We first derive a universal mathematical relationship between space-charge limited potential and vacuum potential for any diode and apply this technique to determine SCLCD for an eccentric spherical diode. We then apply VC and the Schwartz–Christoffel transformation to derive an exact equation for SCLCD in a general two-dimensional planar geometry with emission from a finite emitter. Particle-in-cell simulations using VSim agreed within 4%–13% for a range of ratios of emitter width to gap distance using the thinnest electrodes practical for the memory constraints of our hardware, with the difference partially attributed to the theory's assumption of infinitesimally thin electrodes. After generalizing this approach to determine SCLCD for any orthogonal diode as a function of only the vacuum capacitance and vacuum potential, we derive an analytical formulation of the three-dimensional Child–Langmuir law for finite parallel rectangular and disk geometries. These results demonstrate the utility for calculating SCLCD for any diode geometry using vacuum capacitance and vacuum potential, which are readily obtainable for many diode geometries, to guide experiment and simulation development.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Supernova neutrino signals based on long-term axisymmetric simulations

ABSTRACT We study theoretical neutrino signals from core-collapse supernova (CCSN) computed using axisymmetric CCSN simulations that cover the post-bounce phase up to ∼4 s. We provide basic quantities of the neutrino signals such as event rates, energy spectra, and cumulative number of events at some terrestrial neutrino detectors, and then discuss some new features in the late phase that emerge in our models. Contrary to popular belief, neutrino emissions in the late phase are not always steady, but rather have temporal fluctuations, the vigour of which hinges on the CCSN model and neutrino flavour. We find that such temporal variations are not primarily driven by proto-neutron star convection, but by fallback accretion in exploding models. We assess the detectability of these temporal variations, and find that IceCube is the most promising detector with which to resolve them. We also update fitting formulae first proposed in our previous paper for which the total neutrino energy emitted at the CCSN source is estimated from the cumulative number of events in each detector. This will be a powerful technique with which to analyse real observations, particularly for low-statistics data.

79 ASTRONOMY AND ASTROPHYSICS↗
NASA NTRS1992

Global electric field determination in the Earth's outer magnetosphere using charged particles

Although many properties of the Earth's magnetosphere have been measured and quantified in the past 30 years since it was discovered, one fundamental (for a zeroeth order magnetohydrodynamic (MHD) equilibrium) measurement was made infrequently and with poor spatial coverage: the global electric field. This oversight is in part due to the difficulty of measuring a plasma electric field, and in part due to the difficulty of measuring a plasma electric field, and in part due to the neglect of theorists. However, there is renewed interest in the convection electric field, since it has been realized that it is vital for understanding many aspects of the magnetosphere: the global MHD equilibrium, reconnection rates, Region 2 Birkeland currents, magnetosphere-ionosphere coupling, ring current and radiation belt transport, substorm injections, acceleration mechanisms, etc. Unfortunately the standard experimental methods have not been able to synthesize a global field (excepting the pioneering work of McIlwain's geostationary models), and we are left with an overly simplistic theoretical field, the Volland-Stern electric field mode. Again, single point measurements of the plasma pause were used to infer the appropriate amplitudes of the model, parameterized by Kp (Maynard & Chen, JGR 1975). Although this result was never intended to be the definitive electric field model, it has gone nearly unchanged for 15 years. However, the data sets being taken today require a great deal more accuracy than can be provided by the Volland-Stern model. Nor has the variability of the electric field shielding been properly addressed, although effects of penetrating magnetospheric electric fields has been seen in mid- and low-latitude ionospheric data sets. The growing interests in substorm dynamics also requires a much better assessment of the electric fields responsible for particle injections. Thus, we proposed and developed algorithms for extracting electric fields from particle data taken in the earth's magnetosphere. As a test of the effectiveness of these techniques, we analyzed data taken by the AMPTE/CCE spacecraft in equatorial orbit between 1984-1988. Some analytic tools had to be developed before construction of computer algorithms, and they are discussed.

Eastman, T.↗
NASA NTRS1999

Progress of Cometary Science in the Past 100 Years

Enormous strides made by cometary science during the 20th century defy any meaningful comparison of its state 100 years ago and now. The great majority of the subfields enjoying much attention nowadays did not exist in the year 1900. Dramatic developments, especially in the past 30-50 years, have equally affected observational and theoretical studies of comets. The profound diversification of observing techniques has been documented by the ever widening limits on the electromagnetic spectrum covered. While the time around 1900 marked an early period of slow and painful experimentation with photographic methods in cometary studies, observations of comets from the x-ray region to the radio waves have by now become routine. Many of the new techniques, and all those involved with the wavelengths shorter than about 300 nm, were made possible by another major breakthrough of this century - observing from space. Experiments on dedicated Earth-orbiting satellites as well as several deep-space probes have provided fascinating new information on the nature and makeup of comets. In broader terms, much of the progress has been achieved thanks to fundamental discoveries and major advances in electronics, whose applications resulted in qualitatively new instruments (e.g. radiotelescopes) and sensors or detectors (e.g. CCD arrays). The most universal effect on the entire cometary science, from observing to data handling to quantitative interpretations, has been, as in any other branch of science, due to the introduction of electronic computers, with their processing capabilities not only unheard of, but literally unimaginable, in the age of classical desk calculators. As if all this should not be enough, the today's generations of comet scientists have, in addition, been blessed with nature's highly appreciated cooperation. Indeed, in the span of a dozen years, between 1985 and 1997, we were privileged to witness four remarkable cometary events: (i) a return of Halley's celebrated comet; (ii) the impact of an extensively fragmented comet Shoemaker-Levy 9 into Jupiter - a once-in-a-millenium episode; (iii) a closeup, appearance of a small but very active Earth-approaching comet Hyakutake; and (iv) an unforgettable celestial show of comet Hale-Bopp, one of the brightest and the most massive comets ever observed. We have been - and for many years to come will be - harvesting scientifically lucrative findings based on the flood of data accumulated during observational campaigns organized for these and other recent objects. Our understanding of cometary phenomena will continue to grow as observing techniques are further being improved and as more sophisticated theories are being developed. Recent accomplishments achieved in the rapidly expanding field of comets are certain to stimulate the members of this astronomical community in their quest for new discoveries in the 21st century!

Sekanina, Zdenek↗
DOE OSTI2025

On-shell recursion and holomorphic HQET for heavy quark hadronic resonances

We develop a new theoretical framework for the treatment of heavy quark (HQ) resonances within heavy quark effective theory (HQET). This framework uses on-shell recursion techniques to express the resonant amplitude as a product of on-shell subamplitudes, which allows one to employ a form-factor representation of the hadronic matrix elements and to obtain an HQ expansion, but at the price of introducing complex momenta. We construct a generalized “holomorphic HQET” onto which such complex-momentum matrix elements can be matched, and we show that PT symmetry ensures the Isgur-Wise functions (and the perturbative corrections) become holomorphic functions of the complex recoil parameter with real coefficients. They are thus an analytic continuation of the standard HQET description. This framework admits a HQ hadron (strong decay) width expansion. At second order, we show it is compatible with data for the B12∗$$ {B}_{1(2)}^{\left(\ast \right)} $$ and D12∗$$ {D}_{1(2)}^{\left(\ast \right)} $$ HQ doublets. Taking the B¯→D1∗1−→Dπlν$$ \overline{B}\to \left({D}_1^{\ast}\left({1}^{-}\right)\to D\pi \right) l u $$ system as an example, we compute the holomorphic HQET expansion to first order, as well as the complex-momentum on-shell subamplitudes. A toy numerical study of the resulting differential rates demonstrates that this framework generates HQ resonance lineshapes with large tails, resembling those seen in data.

Manzari, Claudio Andrea↗
DOE OSTI2022

Qubit Assignment Using Time Reversal

As quantum computers with large numbers of qubits become increasingly available, experiments executed on a given device may not utilize all available qubits. In this case, the outcome of executing a quantum program will depend on the ability to efficiently select a subset of high-performing physical qubits. For any given quantum program and device there are many ways to assign physical qubits for execution of the program, and assignments will differ in performance due to the variability in quality across qubits and entangling operations on a single device. Evaluating the performance of each assignment using fidelity estimation introduces significant experimental overhead and will be infeasible for many applications, while relying on standard device benchmarks provides incomplete information about the performance of any specific program. Furthermore, the number of possible assignments grows combinatorially in the number of qubits on the device and in the program, motivating the use of heuristic optimization techniques. We demonstrate a practical solution to the problem of qubit assignment by using simulated annealing with a cost function based on the Loschmidt echo, a diagnostic that measures the reversibility of a quantum process. We provide theoretical justification for this choice of cost function by demonstrating that the optimal qubit assignment coincides with the optimal qubit assignment based on state fidelity in the weak error limit, and we provide experimental justification using diagnostics performed on Google’s superconducting qubit devices. We then establish the performance of simulated annealing for qubit assignment using classical simulations of noisy devices as well as optimization experiments performed on a quantum processor. Our results demonstrate that the use of Loschmidt echoes and simulated annealing provides a scalable and flexible approach to optimizing qubit assignment on near-term hardware.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRSDate not supplied

Improved GEO Derived LW Broadband Fluxes for the Edition5 CERES SYN1Deg Data Product

The NASA Clouds and the Earth's Radiant Energy System (CERES) project provides over 24 years of accurately observed top-of-the-atmosphere (TOA) and surface flux data record for climate monitoring and diagnostic studies. The major level-3 data products include SSF1deg, SYN1deg, FluxByCldTyp, and EBAF data. The CERES SYN1deg product provides 1° gridded observed TOA fluxes and computed surface fluxes based on hourly GEO clouds and derived broadband TOA fluxes. The hourly GEO derived fluxes fill in the temporal gaps between the Terra and Aqua CERES observations. In order to maintain a climate quality dataset the GEO cloud and flux retrievals are consistent over the record. The CERES project is preparing for Edition 5 product providing an opportunity to improve the GEO flux retrieval algorithms. To achieve this, the GEO satellite channel radiances are calibrated against the Aqua-MODIS calibration reference. For SW the GEO channel radiances are then converted to broadband radiances using empirical and theoretical models. The SW broadband radiances are then converted to fluxes using the same CERES angular directional models. For LW the GEO channel radiances are directly converted to LW fluxes utilizing empirical models. The resulting GEO derived broadband fluxes are then normalized to the CERES fluxes regionally by regressing the instantaneous coincident flux pairs. The normalized GEO fluxes are then tied to the CERES instrument calibration, which is very stable over time. This study will attempt to improve the GEO derived LW fluxes based on machine learning technique for the future Edition5 SYN1deg data product.

Moguo Sun↗
NASA NTRS2004

New optical scheme for a polarimetric-based glucose sensor

A new optical scheme to detect glucose concentration in the aqueous humor of the eye is presented. The ultimate aim is to apply this technique in designing a new instrument for, routinely and frequently, noninvasively monitoring blood glucose levels in diabetic patients without contact (no index matching) between the eye and the instrument. The optical scheme exploits the Brewster reflection of circularly polarized light off of the lens of the eye. Theoretically, this reflected linearly polarized light on its way to the detector is expected to rotate its state of polarization, owing to the presence of glucose molecules in the aqueous humor of a patient's eye. An experimental laboratory setup based on this scheme was designed and tested by measuring a range of known concentrations of glucose solutions dissolved in water. (c) 2004 Society of Photo-Optical Instrumentation Engineers.

Evaluation Studies↗
NASA NTRS2011

Test-Anchored Vibration Response Predictions for an Acoustically Energized Curved Orthogrid Panel with Mounted Components

rich body of vibroacoustic test data was recently generated at Marshall Space Flight Center for component-loaded curved orthogrid panels typical of launch vehicle skin structures. The test data were used to anchor computational predictions of a variety of spatially distributed responses including acceleration, strain and component interface force. Transfer functions relating the responses to the input pressure field were generated from finite element based modal solutions and test-derived damping estimates. A diffuse acoustic field model was applied to correlate the measured input sound pressures across the energized panel. This application quantifies the ability to quickly and accurately predict a variety of responses to acoustically energized skin panels with mounted components. Favorable comparisons between the measured and predicted responses were established. The validated models were used to examine vibration response sensitivities to relevant modeling parameters such as pressure patch density, mesh density, weight of the mounted component and model form. Convergence metrics include spectral densities and cumulative root-mean squared (RMS) functions for acceleration, velocity, displacement, strain and interface force. Minimum frequencies for response convergence were established as well as recommendations for modeling techniques, particularly in the early stages of a component design when accurate structural vibration requirements are needed relatively quickly. The results were compared with long-established guidelines for modeling accuracy of component-loaded panels. A theoretical basis for the Response/Pressure Transfer Function (RPTF) approach provides insight into trends observed in the response predictions and confirmed in the test data. The software developed for the RPTF method allows easy replacement of the diffuse acoustic field with other pressure fields such as a turbulent boundary layer (TBL) model suitable for vehicle ascent. Structural responses using a TBL model were demonstrated, and wind tunnel tests have been proposed to anchor the predictions and provide new insight into modeling approaches for this environment. Finally, design load factors were developed from the measured and predicted responses and compared with those derived from traditional techniques such as historical Mass Acceleration Curves and Barrett scaling methods for acreage and component-loaded panels.

Frady, Gregory P.↗
DOE OSTI2025

Desmearing small-angle scattering data by central moment expansions of instrument resolution

This study introduces an enhanced numerical technique tailored specifically for refining 1D small-angle scattering (SAS) intensity profiles affected by smearing. Our primary objective is to address the resolution blurring commonly encountered in SAS data, particularly in systems with clearly defined correlation peaks whose spread aligns with the width of the resolution function at corresponding Q positions. Unlike previous approaches that expanded the SAS intensity using central moment expansion, the new method focuses on expanding the resolution function itself, thus eliminating artificial oscillations observed in smeared spectra due to limitations inherent in our earlier algorithm. This method is straightforward to implement, computationally efficient and consistently performs well in numerical benchmarking. To illustrate its effectiveness, we present a case study of a lamellar phase characterized by distinct peaks in its small-angle neutron scattering intensities.

central moment expansions↗
DOE OSTI2025

ORNL Design Engineering Library: Validated Thermoelectric Digital Twins

Radioisotope thermoelectric generators (RTGs) serve a crucial role in supplying thermal and electrical energy for reliable and long-duration power in remote and extreme environments. The thermal energy is provided by the decay of radioisotopes and is converted into electrical energy using the steady-state thermoelectric process by exploiting the Seebeck effect. Maintaining a thermal gradient through the material is necessary to drive current production. Modern predictive multi-physics tools are able to effectively describe the complex and strongly coupled phenomena needed for accurate model-based system engineering efforts needed to develop higher performing RTGs. Experimental validation of model simulations is essential to confirm the accuracy, reliability, and applicability of predictive multiphysics tools. Validation fosters confidence among users, helps meet regulatory requirements, and contributes to the ongoing improvement of simulation techniques, ultimately leading to better, safer, and more efficient designs and processes. Validated models can then be used as digital twins and can be interrogated to understand and quantify the performance gaps between theoretical and physical systems. These insights can be used to build higher performing systems.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗
DOE OSTI2021

Scalable Pattern Matching in Metadata Graphs via Constraint Checking

Pattern matching is a fundamental tool for answering complex graph queries. Unfortunately, existing solutions have limited capabilities: They do not scale to process large graphs and/or support only a restricted set of search templates or usage scenarios. Moreover, the algorithms at the core of the existing techniques are not suitable for today’s graph processing infrastructures relying on horizontal scalability and shared-nothing clusters, as most of these algorithms are inherently sequential and difficult to parallelize. In this article we present an algorithmic pipeline that bases pattern matching on constraint checking. The key intuition is that each vertex and edge participating in a match has to meet a set of constraints implicitly specified by the search template. These constraints can be verified independently and typically are less expensive to compute than searching the full template. The pipeline we propose generates these constraints and iterates over them to eliminate all the vertices and edges that do not participate in any match, thus reducing the background graph to a subgraph that is the union of all template matches—the complete set of all vertices and edges that participate in at least one match. Additional analysis can be performed on this annotated, reduced graph, such as full match enumeration, match counting, or computing vertex/edge centrality. Furthermore, a vertex-centric formulation for constraint checking algorithms exists, and this makes it possible to harness existing high-performance, vertex-centric graph processing frameworks. This technique (i) enables highly scalable pattern matching in metadata (labeled) graphs; (ii) supports arbitrary patterns with 100% precision; (iii) enables tradeoffs between precision and time-to-solution, while always selects all vertices and edges that participate in matches, thus offering 100% recall; and (iv) supports a set of popular data analytics scenarios. We implement our approach on top of HavoqGT, an open-source asynchronous graph processing framework, and demonstrate its advantages through strong and weak scaling experiments on massive scale real-world (up to 257 billion edges) and synthetic (up to 4.4 trillion edges) labeled graphs, respectively, and at scales (1,024 nodes / 36,864 cores), orders of magnitude larger than used in the past for similar problems. This article serves two purposes: First, it synthesises the knowledge accumulated during a long-term project. Second, it presents new system features, usage scenarios, optimizations, and comparisons with related work that strengthen the confidence that pattern matching based on iterative pruning via constraint checking is an effective and scalable approach in practice. The new contributions include the following: (i) We demonstrate the ability of the constraint checking approach to efficiently support two additional search scenarios that often emerge in practice, interactive incremental search and exploratory search. (ii) We empirically compare our solution with two additional state-of-the-art systems, Arabsque and TriAD. (iii) We show the ability of our solution to accommodate a more diverse range of datasets with varying properties, e.g., scale, skewness, label distribution, and match frequency. (iv) We introduce or extend a number of system features (e.g., work aggregation, load balancing, and the ability to cap the generated traffic) and design optimizations and demonstrate their advantages with respect to improving performance and scalability. (v) We present bottleneck analysis and insights into artifacts that influence performance. (vi) We present a theoretical complexity argument that motivates the performance gains we observe.

97 MATHEMATICS AND COMPUTING↗