Efficiently Approximating Query Optimizer Plan Diagrams

Given a parametrized n-dimensional SQL query template and a choice of query optimizer, a plan diagram is a color-coded pictorial enumeration of the execution plan choices of the optimizer over the query parameter space. These diagrams have proved to be a powerful metaphor for the analysis and redesign of modern optimizers, and are gaining currency in diverse industrial and academic institutions. However, their utility is adversely impacted by the impractically large computational overheads incurred when standard brute-force exhaustive approaches are used for producing fine-grained diagrams on high-dimensional query templates. In this paper, we investigate strategies for efficiently producing close approximations to complex plan diagrams. Our techniques are customized to the features available in the optimizer's API, ranging from the generic optimizers that provide only the optimal plan for a query, to those that also support costing of sub-optimal plans and enumerating rank-ordered lists of plans. The techniques collectively feature both random and grid sampling, as well as inference techniques based on nearest-neighbor classifiers, parametric query optimization and plan cost monotonicity. Extensive experimentation with a representative set of TPC-H and TPC-DS-based query templates on industrial-strength optimizers indicates that our techniques are capable of delivering 90% accurate diagrams while incurring less than 15% of the computational overheads of the exhaustive approach. In fact, for full-featured optimizers, we can guarantee zero error with less than 10% overheads. These approximation techniques have been implemented in the publicly available Picasso optimizer visualization tool.

Quantum destruction of spiral order in two-dimensional frustrated magnets

We study the fate of spin-1/2 spiral-ordered two-dimensional quantum antiferromagnets that are disordered by quantum fluctuations. A crucial role is played by the topological point defects of the spiral phase, which are known to have a Z(2) character. Previous works established that a nontrivial quantum spin-liquid phase results when the spiral is disordered without proliferating the Z(2) vortices. Here, we show that when the spiral is disordered by proliferating and condensing these vortices, valence-bond solid ordering occurs due to quantum Berry phase effects. We develop a general theory for this latter phase transition and apply it to a lattice model. This transition potentially provides a new example of a Landau-forbidden deconfined quantum critical point.

Zero momentum gluons and the total pp and pbarp cross-sections

We describe a QCD motivated model for total cross-sections which uses the eikonal representation and incorporates QCD mini-jets to drive the rise with energy of the cross-section, while the impact parameter distribution is obtained through the Fourier transform of the transverse momentum distribution of soft gluons emitted in the parton-parton interactions giving rise to mini-jets in the final state. A singular but integral expression for the running coupling constant in the infrared region is part of this model.

Scalable Context-Sensitive Points-To Analysis Using Multi-Dimensional Bloom Filters

Context-sensitive points-to analysis is critical for several program optimizations. However, as the number of contexts grows exponentially, storage requirements for the analysis increase tremendously for large programs, making the analysis non-scalable. We propose a scalable flow-insensitive context-sensitive inclusion-based points-to analysis that uses a specially designed multi-dimensional bloom filter to store the points-to information. Two key observations motivate our proposal: (i) points-to information (between pointer-object and between pointer-pointer) is sparse, and (ii) moving from an exact to an approximate representation of points-to information only leads to reduced precision without affecting correctness of the (may-points-to) analysis. By using an approximate representation a multi-dimensional bloom filter can significantly reduce the memory requirements with a probabilistic bound on loss in precision. Experimental evaluation on SPEC 2000 benchmarks and two large open source programs reveals that with an average storage requirement of 4MB, our approach achieves almost the same precision (98.6%) as the exact implementation. By increasing the average memory to 27MB, it achieves precision upto 99.7% for these benchmarks. Using Mod/Ref analysis as the client, we find that the client analysis is not affected that often even when there is some loss of precision in the points-to representation. We find that the NoModRef percentage is within 2% of the exact analysis while requiring 4MB (maximum 15MB) memory and less than 4 minutes on average for the points-to analysis. Another major advantage of our technique is that it allows to trade off precision for memory usage of the analysis.

Optimality of orthogonal sequences with multi-dimensional signaling

The sum capacity on a symbol-synchronous CDMA system having processing gain N and supporting K power constrained users is achieved by employing any set of N orthogonal sequences if a few users are allowed to signal along multiple dimensions. Analogously, the minimum received power (energy-per-chip) on the symbolsynchronous CDMA system supporting K users that demand specified data rates is attained by employing any set of N orthogonal sequences. At most (N - 1) users need to be split and if there are no oversized users, these split users need to signal only in two dimensions each. These results show that sum capacity or minimum sum power can be achieved with minimal downlink signaling.

Active Vibration Suppression of One-dimensional Nonlinear Structures Using Optimal Dynamic Inversion

A flexible robot arm can be modeled as an Euler-Bernoulli beam which are infinite degrees of freedom (DOF) system. Proper control is needed to track the desired motion of a robotic arm. The infinite number of DOF of beams are reduced to finite number for controller implementation, which brings in error (due to their distributed nature). Therefore, to represent reality better distributed parameter systems (DPS) should be controlled using the systems partial differential equation (PDE) directly. In this paper, we propose to use a recently developed optimal dynamic inversion technique to design a controller to suppress nonlinear vibration of a beam. The method used in this paper determines control forces directly from the PDE model of the system. The formulation has better practical significance, because it leads to a closed form solution of the controller (hence avoids computational issues).

Three-Dimensional Site Characterization Model Using Artificial Neural Networks

This research is designed to develop a new technique for site characterization in a three-dimensional domain. Site characterization is a fundamental task in geotechnical engineering practice, as well as a very challenging process, with the ultimate goal of estimating soil properties based on limited tests at any half-space subsurface point in a site.In this research, the sandy site at the Texas A&M University's National Geotechnical Experimentation Site is selected as an example to develop the new technique for site characterization, which is based on Artificial Neural Networks (ANN) technology. In this study, a sequential approach is used to demonstrate the applicability of ANN to site characterization. To verify its robustness, the proposed new technique is compared with other commonly used approaches for site characterization. In addition, an artificial site is created, wherein soil property values at any half-space point are assumed, and thus the predicted values can compare directly with their corresponding actual values, as a means of validation. Since the three-dimensional model has the capability of estimating the soil property at any location in a site, it could have many potential applications, especially in such case, wherein the soil properties within a zone are of interest rather than at a single point. Examples of soil properties of zonal interest include soil type classification and liquefaction potential evaluation. In this regard, the present study also addresses this type of applications based on a site located in Taiwan, which experienced liquefaction during the 1999 Chi-Chi, Taiwan, Earthquake.

Real-time Computer Simulation of Three Dimensional Elastostatics using the Finite Point Method

Real-time simulation of deformable solids is essential for some applications such as biological organ simulations for surgical simulators. In this work, deformable solids are approximated to be linear elastic, and an easy and straight forward numerical technique, the Finite Point Method (FPM), is used to model three dimensional linear elastostatics. Graphics Processing Unit (GPU) is used to accelerate computations. Results show that the Finite Point Method, together with GPU, can compute three dimensional linear elastostatic responses of solids at rates suitable for real-time graphics, for solids represented by reasonable number of points.

Dynamic Multiscaling in Two-Dimensional Fluid Turbulence

We obtain, by extensive direct numerical simulations, time-dependent and equal-time structure functions for the vorticity, in both quasi-Lagrangian and Eulerian frames, for the direct-cascade regime in two-dimensional fluid turbulence with air-drag-induced friction. We show that different ways of extracting time scales from these time-dependent structure functions lead to different dynamic-multiscaling exponents, which are related to equal-time multiscaling exponents by different classes of bridge relations; for a representative value of the friction we verify that, given our error bars, these bridge relations hold.