For a bucket test with a single criterion for success and a fixed number of samples or testing period, requiring a p-value less than a specified value of α for the success criterion produces statistical confidence at level 1 − α. For multiple criteria, a Bonferroni correction that partitions α among the criteria produces statistical confidence, at the cost of requiring lower p-values for each criterion. The same concept can be applied to decisions about early stopping, but that can lead to strict requirements for p-values. We show how to address that challenge by requiring criteria to be successful at multiple decision points.

The k-Minimum Values (KMV) data sketch algorithm stores the k least hash keys generated by hashing the items in a dataset. We show that compression based on ordering the keys and encoding successive differences can offer O(log n) bits per key in expected storage savings, where n is the number of unique values in the data set. We also show that O(log n) expected bits saved per key is optimal for any form of compression for the k least of n random values – that the encoding method is near-optimal among all methods to encode a KMVsketch.We present a practical method to perform that compression, show that it is computationally efficient, and demonstrate that its average savings in practice is within about five percent of the theoretical minimum based on entropy. We verify that our method outperforms off-the-shelf compression methods, and we demonstrate that it is practical, using real and synthetic data.1

Data sketching has emerged as a key infrastructure for large-scale data analysis on streaming and distributed data. Merging sketches enables efficient estimation of cardinalities and frequency histograms over distributed data. However, merging sketches can require that each sketch stores hash codes for identifiers in different data sets or partitions, in order to perform effective matching. This can reveal identifiers during merging or across different data set or partition owners. This paper presents a framework to use noisy hash codes, with the noise level selected to obfuscate identifiers while allowing matching, with high probability. We give probabilistic error bounds on simultaneous obfuscation and matching, concluding that this is a viable approach.

if a data set covers a population of interest then statistics can be computed exactly. If it is a sample of the population (or distribution) of interest then statistics must be estimated. We consider conditions for those estimates to be accurate or inaccurate.

Big data is often used to generate reports consisting of computed statistics. When the statistics are displayed, they may be marked for significance based on p-values. For multiple statistics, we propose a system to mark for significance adjusted for the number of statistics, using a Bonferroni correction in general, and a slightly milder correction for independent statistics.

One way to estimate a statistic over a large data set is to draw a sample consisting of some records from the data set, and compute the statistic over the sample as an estimate of the statistic over the data set. This procedure may fail to produce an accurate estimate. Using one sample for multiple statistics reduces computation and latency, but it can increase the probability of multiple failures to produce accurate estimates, because estimates based on the same sample may not have independent failure probabilities. We show how to bound the probability of multiple failures for sequences of estimates over one or more samples.

We introduce methods to bound the mean of a discrete distribution (or finite population) based on sample data, for random variables with a known set of possible values. In particular, the methods can be applied to categorical data with known category-based values. For small sample sizes, we show how to leverage the knowledge of the set of possible values to compute bounds that are stronger than for general random variables such as standard concentration inequalities.

A data sketch algorithm scans a big data set, collecting a small amount of data - the sketch, which can be used to statistically infer properties of the big data set. Some data sketch algorithms take a fixed-size random sample of a big data set, and use that sample to infer frequencies of items that meet various criteria in the big data set. This paper shows how to statistically infer probably approximately correct (PAC) bounds for those frequencies, efficiently, and precisely enough that the frequency bounds are either sharp or off by only one, which is the best possible result without exact computation.

With mobile shopping surging in popularity, people are spending ever more money on digital purchases through their mobile devices and phones. However, few large-scale studies of mobile shopping exist. In this paper we analyze a large data set consisting of more than 776M digital purchases made on Apple mobile devices that include songs, apps, and in-app purchases. We find that 61% of all the spending is on in-app purchases and that the top 1% of users are responsible for 59% of all the spending. These big spenders are more likely to be male and older, and less likely to be from the US. We study how they adopt and abandon individual app, and find that, after an initial phase of increased daily spending, users gradually lose interest: the delay between their purchases increases and the spending decreases with a sharp drop toward the end. Finally, we model the in-app purchasing behavior in multiple steps: 1) we model the time between purchases; 2) we train a classifier to predict whether the user will make a purchase from a new app or continue purchasing from the existing app; and 3) based on the outcome of the previous step, we attempt to predict the exact app, new or existing, from which the next purchase will come. The results yield new insights into spending habits in the mobile digital marketplace.