Search

Selecting appropriate distributed join methods for logical join operations in a query plan is crucial for the performance of data-intensive scalable computing (DISC). Different network communication patterns in the data exchange phase generate varying network communication workloads and significantly affect the distributed join performance. However, most cost-based query optimizers focus on the local computing cost and do not precisely model the network communication cost. We propose a cost model for various distributed join methods to optimize join queries in DISC platforms. Our method precisely measures the network and local computing workloads in different execution phases, using information on the size and cardinality statistics of datasets and cluster join parallelism. Our cost model reveals the importance of the relative size of the joining datasets. We implement an efficient distributed join selection strategy, known as RelJoin in SparkSQL, which is an industry-prevalent distributed data processing framework. RelJoin uses runtime adaptive statistics for accurate cost estimation and selects optimal distributed join methods for logical joins to optimize the physical query plan. The evaluation results on the TPC-DS benchmark show that RelJoin performs best in 62 of the 97 queries and can reduce the average query time by 21% compared with other strategies.

Markov chain Monte Carlo (MCMC) methods are sampling methods that have become a commonly used tool in statistics, for example to perform Monte Carlo integration. As a consequence of the increase in computational power, many variations of MCMC methods exist for generating samples from arbitrary, possibly complex, target distributions. The performance of an MCMC method is predominately governed by the choice of the so-called proposal distribution used. In this paper, we introduce a new type of proposal distribution for the use in MCMC methods that operates component-wise and with multiple trials per iteration. Specifically, the novel class of proposal distributions, called Plateau distributions, do not overlap, thus ensuring that the multiple trials are drawn from different regions of the state space. Furthermore, the Plateau proposal distributions allow for a bespoke adaptation procedure that lends itself to a Markov chain with efficient problem dependent state space exploration and improved burn-in properties. Simulation studies show that our novel MCMC algorithm outperforms competitors when sampling from distributions with a complex shape, highly correlated components or multiple modes., Comment: 24 pages, 12 figures

Conditional Generative Adversarial Networks~(CGAN) are a recent and popular method for generating samples from a probability distribution conditioned on latent information. The latent information often comes in the form of a discrete label from a small set. We propose a novel method for training CGANs which allows us to condition on a sequence of continuous latent distributions $f^{(1)}, \ldots, f^{(K)}$. This training allows CGANs to generate samples from a sequence of distributions. We apply our method to paintings from a sequence of artistic movements, where each movement is considered to be its own distribution. Exploiting the temporal aspect of the data, a vector autoregressive (VAR) model is fitted to the means of the latent distributions that we learn, and used for one-step-ahead forecasting, to predict the latent distribution of a future art movement $f^{{(K+1)}}$. Realisations from this distribution can be used by the CGAN to generate "future" paintings. In experiments, this novel methodology generates accurate predictions of the evolution of art. The training set consists of a large dataset of past paintings. While there is no agreement on exactly what current art period we find ourselves in, we test on plausible candidate sets of present art, and show that the mean distance to our predictions is small., Comment: 15 pages, 6 figures

Statistical techniques play a large role in the structural health monitoring of instrumented infrastructure, such as a railway bridge constructed with an integrated network of fibre optic sensors. One possible way to reason about the structural health of such a railway bridge, is to model the time it takes to recover to a no-load (baseline) state after a train passes over. Inherently, this recovery time is random and should be modelled statistically. This paper uses a non-parametric model, based on empirical quantile approximations, to construct a space-memory efficient baseline distribution for the streaming data from these sensors. A fast statistical test is implemented to detect deviations away from, and recovery back to, this distribution when trains pass over the bridge, yielding a recovery time. Our method assumes that there are no temporal variations in the data. A median-based detrending scheme is used to remove the temporal variations likely due to temperature changes. This allows for the continuous recording of sensor data with a space-memory constraint., Comment: 18 pages

Resampling is a standard step in particle filters and more generally sequential Monte Carlo methods. We present an algorithm, called chopthin, for resampling weighted particles. In contrast to standard resampling methods the algorithm does not produce a set of equally weighted particles; instead it merely enforces an upper bound on the ratio between the weights. Simulation studies show that the chopthin algorithm consistently outperforms standard resampling methods. The algorithms chops up particles with large weight and thins out particles with low weight, hence its name. It implicitly guarantees a lower bound on the effective sample size. The algorithm can be implemented efficiently, making it practically useful. We show that the expected computational effort is linear in the number of particles. Implementations for C++, R (on CRAN), Python and Matlab are available., Comment: 14 pages, 4 figures

A system to update estimates from a sequence of probability distributions is presented. The aim of the system is to quickly produce estimates with a user-specified bound on the Monte Carlo error. The estimates are based upon weighted samples stored in a database. The stored samples are maintained such that the accuracy of the estimates and quality of the samples is satisfactory. This maintenance involves varying the number of samples in the database and updating their weights. New samples are generated, when required, by a Markov chain Monte Carlo algorithm. The system is demonstrated using a football league model that is used to predict the end of season table. Correctness of the estimates and their accuracy is shown in a simulation using a linear Gaussian model.

We show optimality, in a well-defined sense, using cumulative sum (CUSUM) charts for detecting changes in distributions. We consider a setting with multiple changes between two known distributions. This result advocates the use of non-restarting CUSUM charts with an upper boundary. Typically, after signalling, a CUSUM chart is restarted by setting it to some value below the threshold. A non-restarting CUSUM chart is not reset after signalling; thus is able to signal continuously. Imposing an upper boundary prevents the CUSUM chart rising too high, which facilitates detection in our setting. We discuss, via simulations, how the choice of the upper boundary changes the signals made by the non-restarting CUSUM charts., Comment: 10 pages, 3 figures

Cumulative sum (CUSUM) charts are typically used to detect changes in a stream of observations e.g. shifts in the mean. Usually, after signalling, the chart is restarted by setting it to some value below the signalling threshold. We propose a non-restarting CUSUM chart which is able to detect periods during which the stream is out of control. Further, we advocate an upper boundary to prevent the CUSUM chart rising too high, which helps detecting a change back into control. We present a novel algorithm to control the false discovery rate (FDR) pointwise in time when considering CUSUM charts based on multiple streams of data. We prove that the FDR is controlled under two definitions of a false discovery simultaneously. Simulations reveal the difference in FDR control when using these two definitions and other desirable definitions of a false discovery., Comment: 10 pages, 2 figures