Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “sequential optimal design”

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.

137 records · Page 8
All sourcesNASA NTRSDOE OSTI
DOE OSTI2025

Energy efficiency in industrial drying: A hybrid ultrasonic system with a novel dynamic optimization framework

Drying processes are among the most energy-consuming operations in industrial and manufacturing settings, demanding strategic selection, design, and control for enhanced efficiency. Advancing drying technologies is critical for improving sustainability, lowering energy use, reducing carbon emissions, and minimizing waste. This study explores two innovative strategies aimed at transforming drying processes into sustainable, low-carbon systems by reducing energy consumption, minimizing waste, and maintaining a strong emphasis on preserving product quality. The first strategy showcases a sub-pilot scale hybrid ultrasonic-convective dryer for agrifood products. This technology, powered by electricity (process electrification), integrates non-thermal ultrasonic dehydration with convective heating and is presented as a sustainable and energy-efficient solution that enhances eco-friendly practices. The second strategy involves introducing and implementing a novel, multiobjective, mixed integer dynamic optimization technique to determine the optimal time-dependent process parameter values for the drying operation. This optimization technique yields operating conditions that are piecewise constant in time aiming to maximize the energy efficiency of the hybrid ultrasonic-convective dryer while ensuring strict adherence to product quality constraints. By adopting the hybrid ultrasonic-convective dryer, a notable 35% improvement in energy efficiency was achieved compared to conventional hot-air drying systems for drying apple slices. The proposed optimization framework further enhanced energy efficiency by nearly 14% over the most efficient process on the identical testbed, under static operating conditions. The reported enhancements have been experimentally validated. Regarding drying time (thereby improving production yield), the developed hybrid ultrasonic-convective dryer demonstrates as much as a 41% reduction in total processing time, which is further optimized by an additional 10% using our proposed optimization framework. The research outcomes have profound implications for the design and operation of drying systems, encompassing crucial aspects such as process electrification, cost-effectiveness, energy savings, time efficiency, product yield, product quality, and process automation.

Dynamic optimization↗
DOE OSTI2020

Mechanistic Understanding and Rational Design of Quantum Dot/Mediator Interfaces for Efficient Photon Upconversion

The semiconductor-nanocrystal-sensitized, three-component upconversion system has made great strides over the past 5 years. The three components (i.e., triplet photosensitizer, mediator, and emitter) each play critical roles in determining the input and output photon energy and overall quantum efficiency (QE). The nanocrystal photosensitizer converts the absorbed photon into singlet excitons and then triplet excitons via intersystem crossing. The mediator accepts the triplet exciton via either direct Dexter-type triplet energy transfer (TET) or sequential charge transfer (CT) while extending the exciton lifetime. Through a second triplet energy-transfer step from the mediator to the emitter, the latter is populated in its lowest excited triplet state. Triplet–triplet annihilation (TTA) between two triplet emitters generates the emitter in its bright singlet state, which then emits the upconverted photon. Quantum dots (QD) have a tunable band gap, large extinction coefficient, and small singlet–triplet energy losses compared to metal–ligand charge-transfer complexes. This high triplet exciton yield makes QDs good candidates for photosensitizers. In terms of driving triplet energy transfer, the triplet energy of the mediator should be slightly lower than the triplet exciton energy of the QD sensitizer for a downhill energy landscape with minimal energy loss. The same energy cascade is also required for the transfer from the mediator to the emitter. Lastly, the triplet energy of the emitter must be slightly larger than one-half of its singlet energy to ensure that TTA is exothermic. Optimization of the sensitizer, mediator, and emitter will lead to an increase in the anti-Stokes shift and the total quantum efficiency. Evaluating each individual step’s efficiency and kinetics is necessary for the understanding of the limiting factors in existing systems.

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

Laser Powder Directed Energy Deposition of Steels for Nuclear Applications

This comprehensive investigation examines the structure–property relationships in two nuclear alloy systems—Alloy 709 (A709) austenitic stainless steel and Grade 92 (G-92) ferritic/martensitic (F/M) steel—manufactured via directed energy deposition (DED) for sodium-cooled fast reactor applications. This study establishes the fundamental mechanisms for controlling microstructures for optimizing the mechanical performance of additively manufactured nuclear materials through systematic heat treatment optimization and multiscale characterization. As-deposited A709 steel develops a complex multiscale strengthening architecture consisting of a fine cellular solidification structure with diameter of 2-3 µm within10–50 µm grains, elevated dislocation densities from rapid thermal cycling, and grain boundary precipitates that activate concurrent Hall–Petch, dislocation, and precipitation hardening mechanisms to achieve exceptional properties [yield strength (YS): 603 MPa, ultimate tensile strength (UTS): 844 MPa, Vickers hardness: 220 HV] that achieve a 44% superior strength compared to that of the wrought material. Heat treatments produce different results. Solution annealing (SA) dissolves the cellular structure and reduces the hardness to 190 HV. Precipitation treatment (PT) keeps the cellular structure but adds carbides, allowing the hardness to reach 205 HV. The best approach combines both treatments (SA+PT) and creates uniform precipitate distributions with M 23 C 6 carbides at the grain boundaries and MX carbonitrides in the matrix, achieving a hardness of 195 HV. However, directional differences persist, with a 12%–15% strength variation between orientations due to the inherited layered microstructural architecture that survives aggressive heat treatment. While tensile testing at 550°C demonstrates 40%–50% thermal softening with dynamic strain aging, DED A709 steel still maintains a 71% higher YS than that of the wrought material. Ion irradiation studies (100–400 dpa) of DED A709 steel reveal progressive radiation damage with increasing void density and radiation-induced segregation causing nickel enrichment and chromium depletion, which will ultimately compromise mechanical properties. As-deposited G-92 exhibits exceptional strength (UTS: 1650–1700 MPa, 430 HV) through a complex microstructure containing both ferrite and martensite phases, a high geometrically necessary dislocation (GND) density (17.04×10 14 /m 2 ), and fine carbides. Heat treatments create distinct changes. Normalizing produces fresh martensite with the highest hardness (460 HV) and an increased GND density (20.23×10 14 /m 2 ). Tempering develops dual precipitation systems and reduces the hardness to 290 HV. The optimal approach uses sequential normalizing plus tempering, achieving balanced properties with the lowest hardness (250 HV) and a reduced GND density (11.01×10 14 /m 2 ). A processing-dependent anisotropy is observed: horizontal specimens achieve superior ductile behavior, while vertical specimens exhibit brittle failure. A tempering heat treatment successfully mitigates this anisotropic behavior by transforming the hard martensitic as-deposited structure into tempered martensite enabling both horizontal and vertical specimens to exhibit similar stress–strain characteristics with visible necking behavior. Remarkably, testing at 550°C reveals a reversal in the anisotropy, where as-deposited specimens achieve near isotropy with superior thermal stability (a 15%–20% strength reduction), while tempered specimens develop an orientation dependence with a 25%–30% strength reduction. Both alloy systems demonstrate that DED processing creates specimens with a superior strength through refined microstructural features, though with distinct strengthening mechanisms—austenitic through cellular structures and precipitates versus F/M through phase transformations and precipitates. Heat treatment optimization requires alloy-specific approaches, with A709 benefiting from controlled precipitation while G-92 requires careful phase transformation control. The results show that DED manufacturing can produce nuclear materials with exceptional performance, but directional effects and temperature-dependent behavior must be carefully considered for reactor component design and qualification.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗
DOE OSTI2022

An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services

Many transit agencies operating paratransit and microtransit services have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to significant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse—our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗
DOE OSTI2026

Temperature‐Dependent Crystallization in Two‐Step Perovskite Deposition Revealed by In Situ GIWAXS and Machine Learning‐Guided Analysis

The performance and stability of perovskite solar cells are strongly governed by the crystallization behavior of their active layer. In two-step sequential deposition, early-stage film formation plays a decisive role in determining final phase purity and device quality. Guided by a data-driven analysis of nearly 39 000 devices in the FAIR perovskite database, we identified solvent-mediated quenching and thermal processing as key variables affecting power conversion efficiency (PCE), particularly in two-step fabrication. Here, to investigate these effects in real time, we designed and implemented a custom-built, temperature-controlled spin-coating system, enabling precise thermal modulation during precursor deposition. Using this platform, we performed in situ GIWAXS measurements to study the crystallization dynamics of FA 0.5 MA 0.5 PbI 3 films over a temperature range of 30°C–90°C. Our results reveal a non-monotonic relationship between spin-coating temperature and α-phase formation, governed by the interplay between precursor interdiffusion, PbI 2 crystallinity, and δ-phase suppression. The custom thermal control enabled us to isolate and quantify these competing effects during the earliest stages of film formation, providing mechanistic insight into how spin-coating temperature governs both phase purity and kinetic pathways in two-step perovskite systems. Temperature-dependent SEM and photovoltaic device measurements further demonstrate that early-stage crystallization pathways directly translate into differences in morphology, charge-transport continuity, and device performance. These findings inform targeted strategies for optimizing deposition protocols to balance rapid nucleation, phase stability, and device performance.

Saadawy, Ahmed [King Fahd University of Petroleum ↗
DOE OSTI2025

Light-induced electron spin qubit coherences in the purple bacteria reaction center protein

Photosynthetic reaction center proteins (RCs) provide ideal model systems for studying quantum entanglement between multiple spins, a quantum mechanical phenomenon wherein the properties of the entangled particles become inherently correlated. Following light-generated sequential electron transfer, RCs generate spin-correlated radical pairs (SCRPs), also referred to as entangled spin qubit (radical) pairs (SQPs). Understanding and controlling coherence mechanisms in SCRP/SQPs is important for realizing practical uses of electron spin qubits in quantum sensing applications. The bacterial RC (bRC) provides an experimental system for exploring quantum effects in the SCRP P 865 + Q A − , where P 865 , a special pair of bacteriochlorophylls, is the primary donor, and Q A is the primary quinone acceptor. In this study, we focus on understanding how local molecular environments and isotopic substitution, particularly deuteration, influence spin coherence times (T M ). Using high-frequency electron paramagnetic resonance (EPR) spectroscopy, we observed that the local environment surrounding P 865 and Q A plays a significant role in determining T M . Our findings show that while deuteration led to a modest increase in T M , particularly at low temperatures, but the effect was substantially smaller than predicted by classical nuclear spin diffusion alone. This result is in contrast to our previous study of the photosystem I (PSI) RC, where no increase in T M was observed upon deuteration. Theoretical modeling identified several methyl groups at key distances from the spin centers of both bRC and PSI, and methyl group tunneling at low temperatures has been previously suggested as a mechanism for enhanced spin decoherence. Additionally, our study revealed a strong dependence of spin coherence on the orientation of the external magnetic field, highlighting the influence of the protein microenvironment on spin dynamics. In conclusion, these results offer new insights for optimizing coherence times in quantum system design for quantum information science and sensing applications.

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

LOCOMOTIVES - Comprehensive Impact and Cost Assessment Framework of Carbon Lowering Approaches for the US Rail Freight System

The goal of this project is to develop a tool to aid railroads and other stakeholders assess and approach the decarbonization of freight rail operations by identifying new, viable low-carbon energy storage and conversion systems for future locomotive systems and how they should be deployed on the existing US freight rail network. In the first quarter, the project focused on collecting data, establishing a simulation workflow, and engaging industry through the creation of the Industry Advisory Board (IAB). In the second quarter, the project focused on selecting fuel pathways and powertrain technologies, setting performance targets, conducting a techno-economic analyses, and developing the simulation framework that would serve as the backbone of the future toolhead. The third quarter involved developing an industry-oriented interactive dashboard powered by a five-step sequential framework, as well as holding industry advisory board meetings as per the initial technology-to-market plan. In the remaining project quarters, the NUFRIEND dashboard were fine-tuned with the help of IAB member feedback and in-depth scenario analyses were conducted to support the techno-economic analysis of energy sources. Additionally, dashboard documentation, project insights, and open-source code on GitHub were prepared and released. Throughout the project, the team completed testing and analysis of all model components, integrated all initial test scenarios, and conducted stakeholder engagement. Lower-carbon drop-in fuels can be deployed as admixtures and are considered uniform across the network at a desired penetration rate, while hydrogen and battery-electric technology deployment poses a more complex problem as they require significant investments to be made in the siting of refueling/charging facilities and the replacement of locomotive fleets. Thus, strategies for locating and sizing refueling/charging facilities on a railroad’s network to meet their energy demands were developed to inform deployment decisions. To address this challenge, the Northwestern University Freight Rail Infrastructure & Energy Network Decarbonization (NUFRIEND) framework presents a five-step sequential framework to select O-D paths, locate facilities, reroute flows, size facilities, and evaluate the deployment for alternative energy sources that require locomotive powertrains to be converted and new refueling infrastructure to be deployed. The NUFRIEND Framework is an industry-oriented tool for simulating the deployment of new energy technologies across the US freight rail network. The framework provides a comprehensive network-level optimization and scenario simulation tool for decarbonizing the freight rail sector, addressing the uncertainties surrounding technological developments by supporting sensitivity analyses for different operational and technological parameters through a transparent and flexible input module. It offers practical alternatives to diesel locomotives and can be applied for any railroad considering the specific network structure and freight demand, outputting evaluation metrics for the associated emissions and costs relative to diesel operations. A number of relevant simulation scenarios were run and analyzed for key insights on the value of different alternative technologies for freight rail decarbonization. The project developments and findings have been presented at numerous conferences and events.

08 HYDROGEN↗
DOE OSTI2022

Reinforcement Learning for feedback-enabled cyber resilience

The rapid growth in the number of devices and their connectivity has enlarged the attack surface and made cyber systems more vulnerable. As attackers become increasingly sophisticated and resourceful, mere reliance on traditional cyber protection, such as intrusion detection, firewalls, and encryption, is insufficient to secure the cyber systems. Cyber resilience provides a new security paradigm that complements inadequate protection with resilience mechanisms. A Cyber-Resilient Mechanism (CRM) adapts to the known or zero-day threats and uncertainties in real-time and strategically responds to them to maintain the critical functions of the cyber systems in the event of successful attacks. Feedback architectures play a pivotal role in enabling the online sensing, reasoning, and actuation process of the CRM. Reinforcement Learning (RL) is an important gathering of algorithms that epitomize the feedback architectures for cyber resilience. It allows the CRM to provide dynamic and sequential responses to attacks with limited or without prior knowledge of the environment and the attacker. In this work, we review the literature on RL for cyber resilience and discuss the cyber-resilient defenses against three major types of vulnerabilities, i.e., posture-related, information-related, and human-related vulnerabilities. Here we introduce moving target defense, defensive cyber deception, and assistive human security technologies as three application domains of CRMs to elaborate on their designs. The RL algorithms also have vulnerabilities themselves. We explain the major vulnerabilities of RL and present develop several attack models where the attacker target the information exchanged between the environment and the agent: the rewards, the state observations, and the action commands. We show that the attacker can trick the RL agent into learning a nefarious policy with minimum attacking effort. The paper introduces several defense methods to secure the RL-enabled systems from these attacks. However, there is still a lack of works that focuses on the defensive mechanisms for RL-enabled systems. Last but not least, we discuss the future challenges of RL for cyber security and resilience and emerging applications of RL-based CRMs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

PETSc/TAO Users Manual (Rev. 3.19)

This manual describes the use of the Portable, Extensible Toolkit for Scientific Computation (PETSc) and the Toolkit for Advanced Optimization (TAO) for the numerical solution of partial differential equations and related problems on high-performance computers. PETSc/TAO is a suite of data structures and routines that provide the building blocks for the implementation of large-scale application codes on parallel (and serial) computers. PETSc uses the MPI standard for all distributed memory communication. PETSc/TAO includes a large suite of parallel linear solvers, nonlinear solvers, time integrators, and opti mization that may be used in application codes written in Fortran, C, C++, and Python (via petsc4py; see Getting Started). PETSc provides many of the mechanisms needed within parallel application codes, such as parallel matrix and vector assembly routines. The library is organized hierarchically, enabling users to employ the level of abstraction that is most appropriate for a particular problem. By using techniques of object-oriented programming, PETSc provides enormous flexibility for users. PETSc is a sophisticated set of software tools; as such, for some users it initially has a much steeper learning curve than packages such as MATLAB or a simple subroutine library. In particular, for individuals without some computer science background, experience programming in C, C++, python, or Fortran and experience using a debugger such as gdb or lldb, it may require a significant amount of time to take full advantage of the features that enable efficient software use. However, the power of the PETSc design and the algorithms it incorporates may make the efficient implementation of many application codes simpler than “rolling them” yourself. For many tasks a package such as MATLAB is often the best tool; PETSc is not intended for the classes of problems for which effective MATLAB code can be written. There are several packages, built on PETSc, that may satisfy your needs without requiring directly using PETSc. We recommend reviewing these packages functionality before starting to code directly with PETSc. PETSc can be used to provide a “MPI parallel linear solver” in an otherwise sequential, or OpenMP parallel code. This approach cannot provide extremely large improvements in the application time by utilizing large numbers of MPI processes but can still improve the performance. Certainly all parts of a previously sequential code need not be parallelized but the matrix generation portion must be parallelized to expect true scalability to large numbers of MPI processes. See PCMPI for details on how to utilize the PETSc MPI linear solver server. Since PETSc is under continued development, small changes in usage and calling sequences of routines will occur. PETSc has been supported for twenty-five years; see mailing list information on our website for information on contacting support.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Findings on Subtask 3.1 - Bakken Rich Gas Enhanced Oil Recovery Project

Total in-place oil for the Bakken petroleum system (BPS) (which includes the Bakken and Three Forks Formations) has been estimated to be 600 billion barrels (bbl). However, BPS wells have decline rates as high as 85% over the first 3 years of their lives, and primary recovery factors typically range from 3% to 10% of original oil in place. Given the low initial recovery rates, even small incremental productivity improvements could dramatically increase technically recoverable oil in the BPS. One potential solution is enhanced oil recovery (EOR) using gas injection, such as carbon dioxide (CO2) or hydrocarbon (HC) gases. While commonly used in conventional reservoirs, CO2 EOR in unconventional tight oil reservoirs has been limited to pilot tests. EOR using rich gas (mixture of methane, ethane, and propane) has also been employed in numerous pilots in several unconventional plays and has recently been successfully applied in the Eagle Ford play. If successful, large-scale gas-based EOR in the BPS could dramatically increase oil productivity and recovery factors and extend the life of the play for decades. While CO2 may be a technically suitable working fluid for EOR in the BPS, supplies are limited and costs for using CO2 in EOR pilots are prohibitively high. Meanwhile, produced gas flaring has presented challenges for BPS operators in North Dakota. Analysis conducted by the North Dakota Pipeline Authority indicates that the current gas-gathering infrastructure in North Dakota is insufficient to accommodate all of the associated gas that is produced from the BPS. The geographically isolated location of North Dakota relative to large natural gas markets, combined with suppressed natural gas prices, has made it economically challenging for industry to invest capital in expanding gas-gathering infrastructure in the state. These circumstances led to a research program conducted by the Energy & Environmental Research Center (EERC) in partnership with Liberty Resources Management Company LLC (LR) to examine the potential to use rich gas injection for EOR and mitigate flaring. A rich gas EOR pilot test was designed and executed by LR at its Stomping Horse development area in Williams County, North Dakota. From July 2018 through May 2019, a total of 160 million standard cubic feet (MMscf) of rich produced gas was injected into the BPS using five different wells in a sequential injection strategy. LR’s Leon–Gohrick drill spacing unit (DSU) was used as the test site. Regulatory oversight was provided by the North Dakota Industrial Commission (NDIC). Technical support was provided by the EERC through a series of laboratory, modeling, and field-based activities, and additional post-pilot research activities incorporated learnings from the test, developed new laboratory data, improved fracture modeling methods, and developed machine learning and big data analytics. The results from the Stomping Horse rich gas EOR pilot activities indicate that developing an effective, economical EOR approach for the BPS will require more field tests. Another key lesson learned from the Stomping Horse tests is that detailed pre- and posttest data on reservoir conditions and fluids production are essential. Robust reservoir characterization provides information that is crucial to creating realistic geomodels and conducting valid dynamic simulations of potential EOR scenarios. A detailed understanding of the completions and production history of offset wells is also necessary for valid test result interpretations. This knowledge is essential to designing the operational parameters of injectivity tests and interpreting the results. A conformance control strategy is also essential to success. Laboratory-based examinations of rich gas interactions with reservoir fluids and rocks were conducted, with an emphasis on determining the ability to mobilize oil in the tight reservoir rocks and shales of the BPS. Injection fluid composition was shown to have a positive impact on reducing reservoir oil minimum miscibility pressure (MMP), reducing interfacial tension (IFT), and altering wettability. IFT and contact angle measurements demonstrated that wettability can be altered in the presence of rich gas, suggesting the potential to improve oil recovery. Iterative modeling of surface infrastructure and reservoir performance using data generated by the various project activities was conducted. A geologic model of the Stomping Horse area was built; history-matched oil, gas, and water production was used in simulations of various EOR scenarios. Early programmatic modeling results were used to support LR’s design and operation of the EOR pilot and to provide insight regarding optimization of future commercial-scale BPS EOR design and operations. Post-pilot modeling focused on alternative methods of understanding complex fracture networks and accelerating simulation time. These led to improved simulation run times and provide excellent history-matching results. Several of these iterative models were used as the bases for developing algorithms into machine learning and big data analytics. History matching in reservoir simulation is time-consuming and computer processing-intensive. Machine learning algorithms were created, and an automated history-matching tool was developed. A large set of synthetic reservoir simulations were created to generate well responses (oil, gas, and water production, well bottomhole pressure [BHP], and tracer or propane breakthrough) for a set of EOR operating parameters that included offset well status (open or closed), injectate (rich gas or propane), injection rate, and injection well BHP. A user interface was developed to provide real-time visualization. Machine learning-based models were developed to provide rapid forecasting of well performance given a set of user-defined EOR operating parameters. These predictive models allow the user to modify the offset well status, injection rate, and injection well BHP and rapidly forecast future production performance. The combination of real-time visualization tools with real-time forecasting tools provides a framework for real-time control—operational changes that the EOR site operator can enact (e.g., changing gas injection rates) to affect the observed performance and potentially improve the EOR outcome. There is great reason to be optimistic about the future of EOR in the Bakken. The results of the laboratory studies suggest significant potential for high rates of oil mobilization using produced field gas injection under the right conditions. The results of the lab studies, combined with rigorous statistical analysis of well production data and associated modeling efforts, confirm the notion that fluid mobility within the reservoir is controlled by fractures. As more knowledge is gained about the nature and distribution of fracture networks in the Bakken, the industry will be in a better position to predict and, ultimately, influence fluid mobility. New field tests are necessary to develop a more complete understanding of those conditions. Thoughtful and creatively engineered field tests within a well-characterized geologic setting will yield the fundamental knowledge needed to take Bakken oil production to the next level. This subtask was cofunded through the EERC–U.S. Department of Energy Joint Program on Research and Development for Fossil Energy-Related Resources Cooperative Agreement No. DE-FE0024233. Nonfederal funding was provided by the North Dakota Industrial Commission’s Oil and Gas Research Program and Computer Modelling Group.

04 OIL SHALES AND TAR SANDS↗
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↗