More Like this

1. Statically bounded-memory delayed sampling for probabilistic streams

   https://doi.org/10.1145/3485492  

   Atkinson, Eric; Baudart, Guillaume; Mandel, Louis; Yuan, Charles; Carbin, Michael (October 2021, Proceedings of the ACM on Programming Languages)

   Probabilistic programming languages aid developers performing Bayesian inference. These languages provide programming constructs and tools for probabilistic modeling and automated inference. Prior work introduced a probabilistic programming language, ProbZelus, to extend probabilistic programming functionality to unbounded streams of data. This work demonstrated that the delayed sampling inference algorithm could be extended to work in a streaming context. ProbZelus showed that while delayed sampling could be effectively deployed on some programs, depending on the probabilistic model under consideration, delayed sampling is not guaranteed to use a bounded amount of memory over the course of the execution of the program. In this paper, we the present conditions on a probabilistic program’s execution under which delayed sampling will execute in bounded memory. The two conditions are dataflow properties of the core operations of delayed sampling: the m -consumed property and the unseparated paths property . A program executes in bounded memory under delayed sampling if, and only if, it satisfies the m -consumed and unseparated paths properties. We propose a static analysis that abstracts over these properties to soundly ensure that any program that passes the analysis satisfies these properties, and thus executes in bounded memory under delayed sampling. 

   more » « less
2. Dynamic Quality Metric Oriented Error Bounded Lossy Compression for Scientific Datasets

   https://doi.org/10.1109/SC41404.2022.00067  

   Liu, Jinyang; Di, Sheng; Zhao, Kai; Liang, Xin; Chen, Zizhong; Cappello, Franck (November 2022, SC22: International Conference for High Performance Computing, Networking, Storage and Analysis)

   With ever-increasing execution scale of the high performance computing (HPC) applications, vast amount of data are being produced by scientific research every day. Error-bounded lossy compression has been considered a very promising solution to address the big-data issue for scientific applications, because it can significantly reduce the data volume with low time cost meanwhile allowing users to control the compression errors with a specified error bound. The existing error-bounded lossy compressors, however, are all developed based on inflexible designs or compression pipelines, which cannot adapt to diverse compression quality requirements/metrics favored by different application users. In this paper, we propose a novel dynamic quality metric oriented error-bounded lossy compression framework, namely QoZ. The detailed contribution is three fold. (1) We design a novel highly-parameterized multi-level interpolation-based data predictor, which can significantly improve the overall compression quality with the same compressed size. (2) We design the error bounded lossy compression framework QoZ based on the adaptive predictor, which can auto-tune the critical parameters and optimize the compression result according to user-specified quality metrics during online compression. (3) We evaluate QoZ carefully by comparing its compression quality with multiple state-of-the-arts on various real-world scientific application datasets. Experiments show that, compared with the second best lossy compressor, QoZ can achieve up to 70% compression ratio improvement under the same error bound, up to 150% compression ratio improvement under the same PSNR, or up to 270% compression ratio improvement under the same SSIM. 

   more » « less
3. Facial Input Decompositions for Robust Peak Estimation under Polyhedral Uncertainty

   https://doi.org/10.1016/j.ifacol.2022.09.323  

   Miller, Jared; Sznaier, Mario (January 2022, IFAC-PapersOnLine)

   This work bounds extreme values of state functions for a class of input-affine continuous-time systems that are affected by polyhedral-bounded uncertainty. Instances of these systems may arise in data-driven peak estimation, in which the state function must be bounded for all systems that are consistent with a set of state-derivative data records corrupted under L-infinity bounded noise. Existing occupation measure-based methods form a convergent sequence of outer approximations to the true peak value, given an initial set, by solving a hierarchy of semidefinite programs in increasing size. These techniques scale combinatorially in the number of state variables and uncertain parameters. We present tractable algorithms for peak estimation that scale linearly in the number of faces of the uncertainty-bounding polytope rather than combinatorially in the number of uncertain parameters by leveraging convex duality and a theorem of alternatives (facial decomposition). The sequence of decomposed semidefinite programs will converge to the true peak value under mild assumptions (convergence and smoothness of dynamics). 

   more » « less
4. Constructions of bounded solutions of div u = f in critical spaces

   DeVore, R; Cohen, A; Tadmor, E (December 2024, Springer)

   DeVore, R; Kunoth, A (Ed.)

   We construct uniformly bounded solutions of the equation div u = f for arbitrary data f in the critical spaces Ld(Ω), where Ω is a domain of Rd. This question was addressed by Bourgain & Brezis, [BB2003], who proved that although the problem has a uniformly bounded solution, it is critical in the sense that there exists no linear solution operator for general Ld-data. We first discuss the validity of this existence result under weaker conditions than f ∈ Ld(Ω), and then focus our work on constructive processes for such uniformly bounded solutions. In the d = 2 case, we present a direct one-step explicit construction, which generalizes for d > 2 to a (d − 1)-step construction based on induction. An explicit construction is proposed for compactly supported data in L2,∞(Ω) in the d = 2 case. We also present constructive approaches based on optimization of a certain loss functional adapted to the problem. This approach provides a two-step construction in the d = 2 case. This optimization is used as the building block of a hierarchical multistep process introduced in [Tad2014] that converges to a solution in more general situations. 

   more » « less
5. Parallel Nearest Neighbors in Low Dimensions with Batch Updates

   Blelloch, Guy E.; Dobson, Magdalen (January 2022, 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX))

   We present a set of parallel algorithms for computing exact k-nearest neighbors in low dimensions. Many k-nearest neighbor algorithms use either a kd-tree or the Morton ordering of the point set; our algorithms combine these approaches using a data structure we call the zd-tree. We show that this combination is both theoretically efficient under common assumptions, and fast in practice. For point sets of size n with bounded expansion constant and bounded ratio, the zd-tree can be built in O(n) work with O(n^ε) span for constant ε < 1, and searching for the k-nearest neighbors of a point takes expected O(k log k) time. We benchmark our k-nearest neighbor algorithms against existing parallel k-nearest neighbor algorithms, showing that our implementations are generally faster than the state of the art as well as achieving 75x speedup on 144 hyperthreads. Furthermore, the zd-tree supports parallel batch-dynamic insertions and deletions; to our knowledge, it is the first k-nearest neighbor data structure to support such updates. On point sets with bounded expansion constant and bounded ratio, a batch-dynamic update of size k requires O(k log n/k) work with O(k^ε + polylog(n)) span. 

   more » « less