Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “distributed algorithms”

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 685 records · Page 38

SU-E-T-626: Accuracy of Dose Calculation Algorithms in MultiPlan Treatment Planning System in Presence of Heterogeneities

Purpose: Advanced stereotactic radiotherapy (SRT) treatments require accurate dose calculation for treatment planning especially for treatment sites involving heterogeneous patient anatomy. The purpose of this study was to evaluate the accuracy of dose calculation algorithms, Raytracing and Monte Carlo (MC), implemented in the MultiPlan treatment planning system (TPS) in presence of heterogeneities. Methods: First, the LINAC of a CyberKnife radiotherapy facility was modeled with the PENELOPE MC code. A protocol for the measurement of dose distributions with EBT3 films was established and validated thanks to comparison between experimental dose distributions and calculated dose distributions obtained with MultiPlan Raytracing and MC algorithms as well as with the PENELOPE MC model for treatments planned with the homogenous Easycube phantom. Finally, bones and lungs inserts were used to set up a heterogeneous Easycube phantom. Treatment plans with the 10, 7.5 or the 5 mm field sizes were generated in Multiplan TPS with different tumor localizations (in the lung and at the lung/bone/soft tissue interface). Experimental dose distributions were compared to the PENELOPE MC and Multiplan calculations using the gamma index method. Results: Regarding the experiment in the homogenous phantom, 100% of the points passed for the 3%/3mm tolerance criteria. These criteria include the global error of the method (CT-scan resolution, EBT3 dosimetry, LINAC positionning …), and were used afterwards to estimate the accuracy of the MultiPlan algorithms in heterogeneous media. Comparison of the dose distributions obtained in the heterogeneous phantom is in progress. Conclusion: This work has led to the development of numerical and experimental dosimetric tools for small beam dosimetry. Raytracing and MC algorithms implemented in MultiPlan TPS were evaluated in heterogeneous media.

60 APPLIED LIFE SCIENCES↗

Improving unfolding and systematic uncertainty estimation using generative diffusion networks (Final Technical Report)

This final technical report summarizes the key accomplishments on the unfolding using diffusion model project, a DOE award received by PI Pierre-Hugues Beauchemin at Tufts University. This project main goal was to investigate the potential of diffusion models for unfolding experimental High Energy Physics data from detector effects while controlling systematics uncertainties. The project accomplished its goals by completing the following objectives: 1) Performing an object-by-object, event-by-event unfolding of various kinematic distributions reconstructed from detector data in HEP in a way that keeps correlations between unfolded observables while demonstrating competitive performance compared to standard algorithms used in the field; 2) Address the generalization problem by developing an unfolding algorithm capable to correctly infer the underlying distributions of observables and processes never seen before, while controlling the dominant theoretical uncertainties affecting the process, therefore increasing the effectiveness, the precision, and the applicability of the developed algorithm; 3) Understand the theoretical foundations between the developed algorithm so to extend it to applications beyond experimental HEP, for broader benefits to the society. This report provides an overview of the accomplishments related to each of these key objectives.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Scalable Optimization Methods for Distribution Networks With High PV Integration

Here this paper proposes a suite of algorithms to determine the active- and reactive-power setpoints for photovoltaic (PV) inverters in distribution networks. The objective is to optimize the operation of the distribution feeder according to a variety of performance objectives and ensure voltage regulation. In general, these algorithms take a form of the widely studied ac optimal power flow (OPF) problem. For the envisioned application domain, nonlinear power-flow constraints render pertinent OPF problems nonconvex and computationally intensive for large systems. To address these concerns, we formulate a quadratic constrained quadratic program (QCQP) by leveraging a linear approximation of the algebraic power-flow equations. Furthermore, simplification from QCQP to a linearly constrained quadratic program is provided under certain conditions. The merits of the proposed approach are demonstrated with simulation results that utilize realistic PV-generation and load-profile data for illustrative distribution-system test feeders.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Influence of local capillary trapping on containment system effectiveness

Immobilization of CO 2 injected into deep subsurface storage reservoirs is a critical component of risk assessment for geologic CO 2 storage (GCS). Local capillary trapping (LCT) is a recently established mode of immobilization that arises when CO 2 migrates due to buoyancy through heterogeneous storage reservoirs. This project sought to assess the amount and extent of LCT expected in storage formations under a range of injection conditions, and to confirm the persistence of LCT if the seal overlying the reservoir were to lose its integrity. Numerical simulation using commercial reservoir simulation software was conducted to assess the influence of injection. Laboratory experiments, modeling and numerical simulation were conducted to assess the effect of compromised seal integrity. Bench-scale (0.6 m by 0.6 m by 0.03 m) experiments with surrogate fluids provided the first empirical confirmation of the key concepts underlying LCT: accumulation of buoyant nonwetting phase at above residual saturations beneath capillary barriers in a variety of structures, which remains immobile under normal capillary pressure gradients. Immobilization of above-residual saturations is a critical distinction between LCT and the more familiar “residual saturation trapping.” To estimate the possible extent of LCT in a storage reservoir an algorithm was developed to identify all potential local traps, given the spatial distribution of capillary entry pressure in the reservoir. The algorithm assumes that the driving force for CO 2 migration can be represented as a single value of “critical capillary entry pressure” P c,entry crit , such that cells with capillary entry pressure greater/less than P c,entry crit act as barriers/potential traps during CO 2 migration. At intermediate values of P c,entry crit , the barrier regions become more laterally extensive in the reservoir, approaching a percolation threshold while non-barrier regions remain numerous. The maximum possible extent of LCT thus occurs at P c,entry crit near this threshold. Testing predictions of this simple algorithm against full-physics simulations of buoyancy-driven CO 2 migration support the concept of critical capillary entry pressure. However, further research is needed to determine whether a single value of critical capillary entry pressure always applies and how that value can be determined a priori. Simulations of injection into high-resolution (cells 0.3 m on a side) 2D and 3D heterogeneous domains show two characteristic behaviors. At small gravity numbers (vertical flow velocity much less than horizontal flow velocity) the CO 2 fills local traps as well as regions that would act as local barriers if CO 2 were moving only due to buoyancy. When injection ceases, the CO 2 migrates vertically to establish large saturations within local traps and residual saturation elsewhere. At large gravity numbers, the CO 2 invades a smaller portion of the perforated interval. Within this smaller swept zone the local barriers are not invaded, but local traps are filled to large saturation during injection and remain during post-injection gravity-driven migration. The small gravity number behavior is expected in the region within 100 m of a vertical injection well at anticipated rates of injection for commercial GCS. Simulations of leakage scenarios (through-going region of large permeability imposed in overlying seal) indicate that LCT persists (i.e. CO 2 remains held in a large fraction of the local iv traps) and the persistence is independent of injection rate during storage. Simulations of leakage for the limiting case of CO 2 migrating vertically from an areally extensive emplacement in the lower portion of a reservoir showed similar strong persistence of LCT. This research has two broad implications for GCS. The first is that LCT can retain a significant fraction of the CO 2 stored in a reservoir – above and beyond the residual saturation -- if the overlying seal were to fail. Thus frameworks for risk assessment should be extended to account for LCT. The second implication is that compared to pressure driven flow in reservoirs, CO 2 migration and trapping behave in a qualitatively different manner in heterogeneous reservoirs when buoyancy is the dominant driving force for flow. Thus simulations of GCS that neglect capillary heterogeneity will fail to capture important features of the CO 2 plume. While commercial reservoir simulation software can account for fine scale capillary heterogeneity, it has not been designed to work efficiently with such domains, and no simulators can handle fine-scale resolution throughout the reservoir. A possible way to upscale the migration and trapping is to apply an “effective residual saturation” to coarse-scale grids. While the extent of overall immobilization can be correlated in this way, all coarser grids failed to capture the distance traveled by the migrating CO 2 for large gravity number. Thus it remains unclear how best to account for LCT in the routine simulation work-flow that will be needed for large-scale GCS. Alternatives meriting investigation include streamline methods, reduced-physics proxies (e.g. particle tracking), and biased invasion percolation algorithms, which are based on precisely the capillary heterogeneity essential for LCT.

58 GEOSCIENCES↗

SU-F-T-148: Are the Approximations in Analytic Semi-Empirical Dose Calculation Algorithms for Intensity Modulated Proton Therapy for Complex Heterogeneities of Head and Neck Clinically Significant?

Purpose: Evaluate the differences in dose distributions between the proton analytic semi-empirical dose calculation algorithm used in the clinic and Monte Carlo calculations for a sample of 50 head-and-neck (H&N) patients and estimate the potential clinical significance of the differences. Methods: A cohort of 50 H&N patients, treated at the University of Texas Cancer Center with Intensity Modulated Proton Therapy (IMPT), were selected for evaluation of clinical significance of approximations in computed dose distributions. H&N site was selected because of the highly inhomogeneous nature of the anatomy. The Fast Dose Calculator (FDC), a fast track-repeating accelerated Monte Carlo algorithm for proton therapy, was utilized for the calculation of dose distributions delivered during treatment plans. Because of its short processing time, FDC allows for the processing of large cohorts of patients. FDC has been validated versus GEANT4, a full Monte Carlo system and measurements in water and for inhomogeneous phantoms. A gamma-index analysis, DVHs, EUDs, and TCP and NTCPs computed using published models were utilized to evaluate the differences between the Treatment Plan System (TPS) and FDC. Results: The Monte Carlo results systematically predict lower dose delivered in the target. The observed differences can be as large as 8 Gy, and should have a clinical impact. Gamma analysis also showed significant differences between both approaches, especially for the target volumes. Conclusion: Monte Carlo calculations with fast algorithms is practical and should be considered for the clinic, at least as a treatment plan verification tool.

60 APPLIED LIFE SCIENCES↗

ON THE ESTIMATION OF RANDOM UNCERTAINTIES OF STAR FORMATION HISTORIES

The standard technique for measurement of random uncertainties of star formation histories (SFHs) is the bootstrap Monte Carlo, in which the color-magnitude diagram (CMD) is repeatedly resampled. The variation in SFHs measured from the resampled CMDs is assumed to represent the random uncertainty in the SFH measured from the original data. However, this technique systematically and significantly underestimates the uncertainties for times in which the measured star formation rate is low or zero, leading to overly (and incorrectly) high confidence in that measurement. This study proposes an alternative technique, the Markov Chain Monte Carlo (MCMC), which samples the probability distribution of the parameters used in the original solution to directly estimate confidence intervals. While the most commonly used MCMC algorithms are incapable of adequately sampling a probability distribution that can involve thousands of highly correlated dimensions, the Hybrid Monte Carlo algorithm is shown to be extremely effective and efficient for this particular task. Several implementation details, such as the handling of implicit priors created by parameterization of the SFH, are discussed in detail.

79 ASTRONOMY AND ASTROPHYSICS↗

3D microwave tomography of the breast using prior anatomical information

Purpose: The authors have developed a new 3D breast image reconstruction technique that utilizes the soft tissue spatial resolution of magnetic resonance imaging (MRI) and integrates the dielectric property differentiation from microwave imaging to produce a dual modality approach with the goal of augmenting the specificity of MR imaging, possibly without the need for nonspecific contrast agents. The integration is performed through the application of a soft prior regularization which imports segmented geometric meshes generated from MR exams and uses it to constrain the microwave tomography algorithm to recover nearly uniform property distributions within segmented regions with sharp delineation between these internal subzones. Methods: Previous investigations have demonstrated that this approach is effective in 2D simulation and phantom experiments and also in clinical exams. The current study extends the algorithm to 3D and provides a thorough analysis of the sensitivity and robustness to misalignment errors in size and location between the spatial prior information and the actual data. Results: Image results in 3D were not strongly dependent on reconstruction mesh density, and the changes of less than 30% in recovered property values arose from variations of more than 125% in target region size—an outcome which was more robust than in 2D. Similarly, changes of less than 13% occurred in the 3D image results from variations in target location of nearly 90% of the inclusion size. Permittivity and conductivity errors were about 5 times and 2 times smaller, respectively, with the 3D spatial prior algorithm in actual phantom experiments than those which occurred without priors. Conclusions: The presented study confirms that the incorporation of structural information in the form of a soft constraint can considerably improve the accuracy of the property estimates in predefined regions of interest. These findings are encouraging and establish a strong foundation for using the soft prior technique in clinical studies, where their microwave imaging system and MRI can simultaneously collect breast exam data in patients.

60 APPLIED LIFE SCIENCES↗

Bi-Level Dynamic Optimization with Feedback

This paper considers a bi-level real-time algorithmic framework for networked systems, consisting of several local controllers and a central controller. The central controller issues setpoints to the local controllers to optimize their operational objectives while satisfying system-wide constraints. In this context, the paper develops an online algorithm for tracking the optimal solution of the underlying dynamic optimization problem. The design of the algorithm is based on a projected-gradient method, suitably modified to accommodate appropriate measurements (i.e., feedback). Optimality claims are established in terms of the dynamic regret of the algorithm; the latter is a natural performance criterion in nonstationary environments associated with real-time control problems. Finally, the application of the algorithm to real-time control of power setpoints in an electrical grid is illustrated.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Development of Steady-State and Dynamic Mass and Energy Constrained Neural Networks for Distributed Chemical Systems Using Noisy Transient Data

The paper presents the development of algorithms for mass and energy constrained neural network models that can exactly conserve the overall mass and energy of distributed chemical process systems, even though the noisy transient data used for optimal model training violate the same. In contrast to approximately satisfying mass and energy balance constraints of a system by soft penalization of objective function, algorithms have been developed for solving equality-constrained nonlinear optimization problems, thus providing the guarantee of exactly satisfying the system mass and energy conservation laws. For developing dynamic mass-energy constrained network models for distributed systems, hybrid series and parallel dynamic-static neural networks have been leveraged. The developed algorithms for solving both the training and forward problems are validated using both steady-state and dynamic data in the presence of various noise characteristics. The developed data-driven algorithms are flexible to exactly satisfy mass and energy balance constraints for dynamic chemical processes if the system holdup information is available. The proposed network structures and algorithms are applied to the development of data-driven lumped and distributed models of an adiabatic superheater/reheater system, a nonisothermal continuous stirred tank reactor, as well as an electrically heated plug-flow reactor system where one form of energy gets transformed to another. It has been observed that the mass-energy constrained neural networks yield a root mean squared error of <1% with respect to the system truth for the case studies evaluated in this work.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

SU-E-T-374: Evaluation and Verification of Dose Calculation Accuracy with Different Dose Grid Sizes for Intracranial Stereotactic Radiosurgery

Purpose: In this study, we aim to evaluate the effect of dose grid size on the accuracy of calculated dose for small lesions in intracranial stereotactic radiosurgery (SRS), and to verify dose calculation accuracy with radiochromic film dosimetry. Methods: 15 intracranial lesions from previous SRS patients were retrospectively selected for this study. The planning target volume (PTV) ranged from 0.17 to 2.3 cm{sup 3}. A commercial treatment planning system was used to generate SRS plans using the volumetric modulated arc therapy (VMAT) technique using two arc fields. Two convolution-superposition-based dose calculation algorithms (Anisotropic Analytical Algorithm and Acuros XB algorithm) were used to calculate volume dose distribution with dose grid size ranging from 1 mm to 3 mm with 0.5 mm step size. First, while the plan monitor units (MU) were kept constant, PTV dose variations were analyzed. Second, with 95% of the PTV covered by the prescription dose, variations of the plan MUs as a function of dose grid size were analyzed. Radiochomic films were used to compare the delivered dose and profile with the calculated dose distribution with different dose grid sizes. Results: The dose to the PTV, in terms of the mean dose, maximum, and minimum dose, showed steady decrease with increasing dose grid size using both algorithms. With 95% of the PTV covered by the prescription dose, the total MU increased with increasing dose grid size in most of the plans. Radiochromic film measurements showed better agreement with dose distributions calculated with 1-mm dose grid size. Conclusion: Dose grid size has significant impact on calculated dose distribution in intracranial SRS treatment planning with small target volumes. Using the default dose grid size could lead to under-estimation of delivered dose. A small dose grid size should be used to ensure calculation accuracy and agreement with QA measurements.

60 APPLIED LIFE SCIENCES↗

Resilient distributed state estimation with mobile agents: overcoming Byzantine adversaries, communication losses, and intermittent measurements

Applications in environmental monitoring, surveillance and patrolling typically require a network of mobile agents to collectively gain information regarding the state of a static or dynamical process evolving over a region. However, these networks of mobile agents also introduce various challenges, including intermittent observations of the dynamical process, loss of communication links due to mobility and packet drops, and the potential for malicious or faulty behavior by some of the agents. The main contribution of this paper is the development of resilient, fully-distributed, and provably correct state estimation algorithms that simultaneously account for each of the above considerations, and in turn, offer a general framework for reasoning about state estimation problems in dynamic, failure-prone and adversarial environments. Specifically, we develop a simple switched linear observer for dealing with the issue of time-varying measurement models, and resilient filtering techniques for dealing with worst-case adversarial behavior subject to time-varying communication patterns among the agents. Here, our approach considers both communication patterns that recur in a deterministic manner, and patterns that are induced by random packet drops. For each scenario, we identify conditions on the dynamical system, the patrols, the nominal communication network topology, and the failure models that guarantee applicability of our proposed techniques. Finally, we complement our theoretical results with detailed simulations that illustrate the efficacy of our algorithms in the presence of the technical challenges described above.

42 ENGINEERING↗

Sample IEEE123 Bus system for OEDI SI

Time series load and PV data from an IEEE123 bus system. An example electrical system, named the OEDI SI feeder, is used to test the workflow in a co-simulation. The system used is the IEEE123 test system, which is a well studied test system (see link below to IEEE PES Test Feeder), but some modifications were made to it to add some solar power modules and measurements on the system. The aim of this project is to create an easy-to-use platform where various types of analytics can be performed on a wide range of electrical grid datasets. The aim is to establish an open-source library of algorithms that universities, national labs and other developers can contribute to which can be used on both open-source and proprietary grid data to improve the analysis of electrical distribution systems for the grid modeling community. OEDI Systems Integration (SI) is a grid algorithms and data analytics API created to standardize how data is sent between different modules that are run as part of a co-simulation. The readme file included in the S3 bucket provides information about the directory structure and how to use the algorithms. The sensors.json file is used to define the measurement locations.

123 bus↗

Uncertainty Quantification with MCMC method and BFBT Data

The reliability of predictions of the system codes is closely related to the validation of their physical models. For example, the accuracy of void fraction prediction in a Boiling Water Reactor (BWR) using TRACE code depends on the uncertainties of closure relations developed for the two-phase flow models. This work focus on quantifying the uncertainties of two physical models, interfacial drag model and subcooled boiling model, using Markov Chain Monte Carlo (MCMC) method and BFBT experimental benchmark data. We applied the MCMC and MLE algorithms to BFBT benchmark data and estimated the uncertainty distribution of two model parameters: subcooled boiling heat transfer coefficient and interfacial drag (bubbly/slug rod bundle) coefficient. These algorithms tend to give various estimation results. Despite the differences in these algorithms, we find that the estimation results are consistent. After obtaining the uncertainty estimates, we validated the uncertainty estimates by applying the estimated distributions of model parameters to TRACE prediction. The new predictions succeed in reducing the void fraction prediction error, but it is not possible to eliminate all prediction error. We are only adjusting two model parameters, and there exists uncertainties in all model parameters. Application of the algorithms to other physical models and experimental data will be helpful for future work. (authors)

42 ENGINEERING↗

Approximate Boltzmann distributions in quantum approximate optimization

Approaches to compute or estimate the output probability distributions from the quantum approximate optimization algorithm (QAOA) are needed to assess the likelihood it will obtain a quantum computational advantage. We analyze output from QAOA circuits solving 7200 random MaxCut instances, with $n$ = 14–23 qubits and depth parameter $p$ ≤ 12 and find that the average basis state probabilities follow approximate Boltzmann distributions: The average probabilities scale exponentially with their energy (cut value), with a peak at the optimal solution. Furthermore, we describe the rate of exponential scaling or effective temperature in terms of a series with a leading-order term $T$ ~ $C$ min /$n$ $\sqrt{p}$, with $C$ min the optimal solution energy. Using this scaling, we generate approximate output distributions with up to 38 qubits and find these give accurate accounts of important performance metrics in cases we can simulate exactly.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

SU-E-T-231: Cross-Validation of 3D Gamma Comparison Tools

Purpose: Moving the computational analysis for 3D gel dosimetry into the 3D Slicer (www.slicer.org) environment has made gel dosimetry more clinically accessible. To ensure accuracy, we cross-validate the 3D gamma comparison module in 3D Slicer with an independently developed algorithm using simulated and measured dose distributions. Methods: Two reference dose distributions were generated using the Varian Eclipse treatment planning system. The first distribution consisted of a four-field box irradiation delivered to a plastic water phantom and the second, a VMAT plan delivered to a gel dosimeter phantom. The first reference distribution was modified within Eclipse to create an evaluated dose distribution by spatially shifting one field by 3mm, increasing the monitor units of the second field, applying a dynamic wedge for the third field, and leaving the fourth field unchanged. The VMAT plan was delivered to a gel dosimeter and the evaluated dose in the gel was calculated from optical CT measurements. Results from the gamma comparison tool built into the SlicerRT toolbox were compared to results from our in-house gamma algorithm implemented in Matlab (via MatlabBridge in 3D Slicer). The effects of noise, resolution and the exchange of reference and evaluated designations on the gamma comparison were also examined. Results: Perfect agreement was found between the gamma results obtained using the SlicerRT tool and our Matlab implementation for both the four-field box and gel datasets. The behaviour of the SlicerRT comparison with respect to changes in noise, resolution and the role of the reference and evaluated dose distributions was consistent with previous findings. Conclusion: Two independently developed gamma comparison tools have been cross-validated and found to be identical. As we transition our gel dosimetry analysis from Matlab to 3D Slicer, this validation serves as an important test towards ensuring the consistency of dose comparisons using the 3D Slicer environment.

60 APPLIED LIFE SCIENCES↗

Adversarial sampling of unknown and high-dimensional conditional distributions

Many engineering problems require the prediction of realization-to-realization variability or a refined description of modeled quantities. In that case, it is necessary to sample elements from unknown high-dimensional spaces with possibly millions of degrees of freedom. While there exist methods able to sample elements from probability density functions (PDF) with known shapes, several approximations need to be made when the distribution is unknown. In this paper the sampling method, as well as the inference of the underlying distribution, are both handled with a data-driven method known as generative adversarial networks (GAN), which trains two competing neural networks to produce a network that can effectively generate samples from the training set distribution. In practice, it is often necessary to draw samples from conditional distributions. When the conditional variables are continuous, only one (if any) data point corresponding to a particular value of a conditioning variable may be available, which is not sufficient to estimate the conditional distribution. This work handles this problem using an a priori estimation of the conditional moments of a PDF. Herein, two approaches, stochastic estimation, and an external neural network are compared for computing these moments; however, any preferred method can be used. The algorithm is demonstrated in the case of the deconvolution of a filtered turbulent flow field. It is shown that all the versions of the proposed algorithm effectively sample the target conditional distribution with minimal impact on the quality of the samples compared to state-of-the-art methods. Additionally, the procedure can be used as a metric for the diversity of samples generated by a conditional GAN (cGAN) conditioned with continuous variables.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Final Report: Sampling-Based Algorithms for Estimating Structure in Big Data.

The purpose of this project was to develop sampling-based algorithms to discover hidden struc- ture in massive data sets. Inferring structure in large data sets is an increasingly common task in many critical national security applications. These data sets come from myriad sources, such as network traffic, sensor data, and data generated by large-scale simulations. They are often so large that traditional data mining techniques are time consuming or even infeasible. To address this problem, we focus on a class of algorithms that do not compute an exact answer, but instead use sampling to compute an approximate answer using fewer resources. The particular class of algorithms that we focus on are streaming algorithms , so called because they are designed to handle high-throughput streams of data. Streaming algorithms have only a small amount of working storage - much less than the size of the full data stream - so they must necessarily use sampling to approximate the correct answer. We present two results: * A streaming algorithm called HyperHeadTail , that estimates the degree distribution of a graph (i.e., the distribution of the number of connections for each node in a network). The degree distribution is a fundamental graph property, but prior work on estimating the degree distribution in a streaming setting was impractical for many real-world application. We improve upon prior work by developing an algorithm that can handle streams with repeated edges, and graph structures that evolve over time. * An algorithm for the task of maintaining a weighted subsample of items in a stream, when the items must be sampled according to their weight, and the weights are dynamically changing. To our knowledge, this is the first such algorithm designed for dynamically evolving weights. We expect it may be useful as a building block for other streaming algorithms on dynamic data sets.

97 MATHEMATICS AND COMPUTING↗