1015745
Measuring independence of datasets
Approximating pairwise, or k-wise, independence with sublinear memory is of considerable importance in the data stream model. In the streaming model the joint distribution is given by a stream of k-tuples, with the goal of testing correlations among the components measured over the entire stream. Indyk and McGregor (SODA 08) recently gave exciting new results for measuring pairwise independence in this model.
 Statistical distance is one of the most fundamental metrics for measuring the similarity of two distributions, and it has been a metric of choice in many papers that discuss distribution closeness. For pairwise independence, the Indyk and McGregor methods provide log{n}-approximation under statistical distance between the joint and product distributions in the streaming model. Indyk and McGregor leave, as their main open question, the problem of improving their log n-approximation for the statistical distance metric.
 In this paper we solve the main open problem posed by Indyk and McGregor for the statistical distance for pairwise independence and extend this result to any constant k. In particular, we present an algorithm that computes an (ε, δ)-approximation of the statistical distance between the joint and product distributions defined by a stream of k-tuples. Our algorithm requires O((1/ε log(nm/δ))(30+k)k) memory and a single pass over the data stream.
8408623
Selectivity Estimation Without the Attribute Value Independence Assumption
The result size of a query that involves multiple attributes from the same relation depends on these attributes’joinr data distribution, i.e., the frequencies of all combinations of attribute values. To simplify the estimation of that size, most commercial systems make the artribute value independenceassumption and maintain statistics (typically histograms) on individual attributes only. In reality, this assumption is almost always wrong and the resulting estimations tend to be highly inaccurate. In this paper, we propose two main alternatives to effectively approximate (multi-dimensional) joint data distributions. (a) Using a multi-dimensional histogram, (b) Using the Singular Value Decomposition (SVD) technique from linear algebra. An extensive set of experiments demonstrates the advantages and disadvantages of the two approaches and the benefits of both compared to the independence assumption.
17356153
CORDS: automatic discovery of correlations and soft functional dependencies
The rich dependency structure found in the columns of real-world relational databases can be exploited to great advantage, but can also cause query optimizers---which usually assume that columns are statistically independent---to underestimate the selectivities of conjunctive predicates by orders of magnitude. We introduce CORDS, an efficient and scalable tool for automatic discovery of correlations and soft functional dependencies between columns. CORDS searches for column pairs that might have interesting and useful dependency relations by systematically enumerating candidate pairs and simultaneously pruning unpromising candidates using a flexible set of heuristics. A robust chi-squared analysis is applied to a sample of column values in order to identify correlations, and the number of distinct values in the sampled columns is analyzed to detect soft functional dependencies. CORDS can be used as a data mining tool, producing dependency graphs that are of intrinsic interest. We focus primarily on the use of CORDS in query optimization. Specifically, CORDS recommends groups of columns on which to maintain certain simple joint statistics. These "column-group" statistics are then used by the optimizer to avoid naive selectivity estimates based on inappropriate independence assumptions. This approach, because of its simplicity and judicious use of sampling, is relatively easy to implement in existing commercial systems, has very low overhead, and scales well to the large numbers of columns and large table sizes found in real-world databases. Experiments with a prototype implementation show that the use of CORDS in query optimization can speed up query execution times by an order of magnitude. CORDS can be used in tandem with query feedback systems such as the LEO learning optimizer, leveraging the infrastructure of such systems to correct bad selectivity estimates and ameliorating the poor performance of feedback systems during slow learning phases.
14696271
Declaring independence via the sketching of sketches
We consider the problem of identifying correlations in data streams. Surprisingly, our work seems to be the first to consider this natural problem. In the centralized model, we consider a stream of pairs (i,j) ∈ [n]2 whose frequencies define a joint distribution (X,Y). In the distributed model, each coordinate of the pair may appear separately in the stream. We present a range of algorithms for approximating to what extent X and Y are independent, i.e., how close the joint distribution is to the product of the marginals. We consider various measures of closeness including ℓ1, ℓ2, and the mutual information between X and Y. Our algorithms are based on "sketching sketches", i.e., composing small-space linear synopses of the distributions. Perhaps ironically, the biggest technical challenges that arise relate to ensuring that different components of our estimates are sufficiently independent.
5050980
Testing k-wise and almost k-wise independence
In this work, we consider the problems of testing whether adistribution over (0,1<sup>n</sup>) is <i>k</i>-wise (resp. (ε,k)-wise) independentusing samples drawn from that distribution.
 For the problem of distinguishing <i>k</i>-wise independent distributions from those that are δ-far from <i>k</i>-wise independence in statistical distance, we upper bound the number ofrequired samples by Õ(n<sup>k</sup>/δ<sup>2</sup>) and lower bound it by Ω(n<sup>k-1/2</sup>/δ) (these bounds hold for constant<i>k</i>, and essentially the same bounds hold for general <i>k</i>). Toachieve these bounds, we use Fourier analysis to relate adistribution's distance from <i>k</i>-wise independence to its biases, a measure of the parity imbalance it induces on a setof variables. The relationships we derive are tighter than previouslyknown, and may be of independent interest.
 To distinguish (ε,k)-wise independent distributions from thosethat are δ-far from (ε,k)-wise independence in statistical distance, we upper bound thenumber of required samples by O(k log n / δ<sup>2</sup>ε<sup>2</sup>) and lower bound it by Ω(√ k log n / 2<sup>k</sup>(ε+δ)√ log 1/2<sup>k</sup>(ε+δ)). Although these bounds are anexponential improvement (in terms of <i>n</i> and <i>k</i>) over thecorresponding bounds for testing <i>k</i>-wise independence, we give evidence thatthe time complexity of testing (ε,k)-wise independence isunlikely to be poly(n,1/ε,1/δ) for k=Θ(log n),since this would disprove a plausible conjecture concerning the hardness offinding hidden cliques in random graphs. Under the conjecture, ourresult implies that for, say, k = log n and ε = 1 / n<sup>0.99</sup>,there is a set of (ε,k)-wise independent distributions, and a set of distributions at distance δ=1/n<sup>0.51</sup> from (ε,k)-wiseindependence, which are indistinguishable by polynomial time algorithms.
101158
Almost k-wise independence versus k-wise independence
We say that a distribution over {0,1}n is (e,k)-wise independent if its restriction to every k coordinates results in a distribution that is e-close to the uniform distribution. A natural question regarding (e, k)-wise independent distributions is how close they are to some k-wise independent distribution. We show that there exist (e, k)-wise independent distributions whose statistical distance is at least nO(k) ċ e from any k-wise independent distribution. In addition, we show that for any (e,k)-wise independent distribution there exists some k-wise independent distribution, whose statistical distance is nO(k) ċ e.
5495804
Testing random variables for independence and identity
Given access to independent samples of a distribution A over [n] /spl times/ [m], we show how to test whether the distributions formed by projecting A to each coordinate are independent, i.e., whether A is /spl epsi/-close in the L/sub 1/ norm to the product distribution A/sub 1//spl times/A/sub 2/ for some distributions A/sub 1/ over [n] and A/sub 2/ over [m]. The sample complexity of our test is O/spl tilde/(n/sup 2/3/m/sup 1/3/poly(/spl epsi//sup -1/)), assuming without loss of generality that m/spl les/n. We also give a matching lower bound, up to poly (log n, /spl epsi//sup -1/) factors. Furthermore, given access to samples of a distribution X over [n], we show how to test if X is /spl epsi/-close in L/sub 1/ norm to an explicitly specified distribution Y. Our test uses O/spl tilde/(n/sup 1/2/poly(/spl epsi//sup -1/)) samples, which nearly matches the known tight bounds for the case when Y is uniform.
6128607
Sublinear algorithms for testing monotone and unimodal distributions
The complexity of testing properties of monotone and unimodal distributions, when given access only to samples of the distribution, is investigated. Two kinds of sublinear-time algorithms---those for testing monotonicity and those that take advantage of monotonicity---are provided. The first algorithm tests if a given distribution on [n] is monotone or far away from any monotone distribution in L1-norm; this algorithm uses O(√n) samples and is shown to be nearly optimal. The next algorithm, given a joint distribution on [n] x [n], tests if it is monotone or is far away from any monotone distribution in L1-norm; this algorithm uses O(n3/2) samples. The problems of testing if two monotone distributions are close in L1-norm and if two random variables with a monotone joint distribution are close to being independent in L1-norm are also considered. Algorithms for these problems that use only poly(log n) samples are presented. The closeness and independence testing algorithms for monotone distributions are significantly more efficient than the corresponding algorithms as well as the lower bounds for arbitrary distributions. Some of the above results are also extended to unimodal distributions.
11445619
Manipulating Statistical Diierence
We give several eecient transformations for manipulating the statistical diierence (variation distance) between a pair of probability distributions. The eeects achieved include increasing the statistical diierence, decreasing the statistical diierence, \polarizing" the statistical relationship, and \reversing" the statistical relationship. We also show that a boolean formula whose atoms are statements about statistical diierence can be transformed into a single statement about statistical diierence. All of these transformations can be performed in polynomial time, in the sense that, given circuits which sample from the input distributions, it only takes polynomial time to compute circuits which sample from the output distributions. By our prior work (see FOCS 97), such transformations for manipulating statistical diierence are closely connected to results about SZK, the class of languages possessing statistical zero-knowledge proofs. In particular, some of the transformations given in this paper are equivalent to the closure of SZK under complement and under certain types of Turing reductions. This connection is also discussed brieey in this paper.
2520143
Testing monotone high-dimensional distributions
A <i>monotone distribution</i> <i>P</i> over a (partially) ordered domain has <i>P</i>(<i>y</i>) ≥ <i>P</i>(<i>x</i>) if <i>y</i> ≥ <i>x</i> in the order. We study several natural problems of testing properties of monotone distributions over the <i>n</i>-dimensional Boolean cube, given access to random draws from the distribution being tested. We give a poly(<i>n</i>)-time algorithm for testing whether a monotone distribution is equivalent to or ε-far (in the <i>L</i><inf>1</inf> norm) from the uniform distribution. A key ingredient of the algorithm is a generalization of a known isoperimetric inequality for the Boolean cube. We also introduce a method for proving lower bounds on testing monotone distributions over the <i>n</i>-dimensional Boolean cube, based on a new decomposition technique for monotone distributions. We use this method to show that our uniformity testing algorithm is optimal up to polylog(<i>n</i>) factors, and also to give exponential lower bounds on the complexity of several other problems (testing whether a monotone distribution is identical to or ε-far from a fixed known monotone product distribution and approximating the entropy of an unknown monotone distribution).
6434930
AMS Without 4-Wise Independence on Product Domains
In their seminal work, Alon, Matias, and Szegedy introduced several sketching techniques, including showing that $4$-wise independence is sufficient to obtain good approximations of the second frequency moment. In this work, we show that their sketching technique can be extended to product domains $[n]^k$ by using the product of $4$-wise independent functions on $[n]$. 
 
Our work extends that of Indyk and McGregor, who showed the result for $k = 2$. Their primary motivation was the problem of identifying correlations in data streams. In their model, a stream of pairs $(i,j) \in [n]^2$ arrive, giving a joint distribution $(X,Y)$, and they find approximation algorithms for how close the joint distribution is to the product of the marginal distributions under various metrics, which naturally corresponds to how close $X$ and $Y$ are to being independent. By using our technique, we obtain a new result for the problem of approximating the $\ell_2$ distance between the joint distribution and the product of the marginal distributions for $k$-ary vectors, instead of just pairs, in a single pass. Our analysis gives a randomized algorithm that is a $(1\pm \epsilon)$ approximation (with probability $1-\delta$) that requires space logarithmic in $n$ and $m$ and proportional to $3^k$.
11803579
Testing that distributions are close
Given two distributions over an n element set, we wish to check whether these distributions are statistically close by only sampling. We give a sublinear algorithm which uses O(n/sup 2/3//spl epsiv//sup -4/ log n) independent samples from each distribution, runs in time linear in the sample size, makes no assumptions about the structure of the distributions, and distinguishes the cases when the distance between the distributions is small (less than max(/spl epsiv//sup 2//32/sup 3//spl radic/n,/spl epsiv//4/spl radic/n=)) or large (more than /spl epsiv/) in L/sub 1/-distance. We also give an /spl Omega/(n/sup 2/3//spl epsiv//sup -2/3/) lower bound. Our algorithm has applications to the problem of checking whether a given Markov process is rapidly mixing. We develop sublinear algorithms for this problem as well.
43033444
The Space Complexity of Approximating the Frequency Moments
The frequency moments of a sequence containingmielements of typei, 1?i?n, are the numbersFk=?ni=1mki. We consider the space complexity of randomized algorithms that approximate the numbersFk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF0,F1, andF2can be approximated in logarithmic space, whereas the approximation ofFkfork?6 requiresn?(1)space. Applications to data bases are mentioned as well.
4790064
Simpler algorithm for estimating frequency moments of data streams
The problem of estimating the <i>k</i><sup><i>th</i></sup> frequency moment <i>F</i><inf><i>k</i></inf> over a data stream by looking at the items exactly once as they arrive was posed in [1, 2]. A succession of algorithms have been proposed for this problem [1, 2, 6, 8, 7]. Recently, Indyk and Woodruff [11] have presented the first algorithm for estimating <i>F</i><inf><i>k</i></inf>, for <i>k</i> > 2, using space <i>Õ</i>(<i>n</i><sup>1-2/<i>k</i></sup>), matching the space lower bound (up to poly-logarithmic factors) for this problem [1, 2, 3, 4, 13] (<i>n</i> is the number of distinct items occurring in the stream.) In this paper, we present a simpler 1-pass algorithm for estimating <i>F</i><inf><i>k</i>.</inf>
15022910
Finding frequent items in data streams
The frequent items problem is to process a stream of items and find all items occurring more than a given fraction of the time. It is one of the most heavily studied problems in data stream mining, dating back to the 1980s. Many applications rely directly or indirectly on finding the frequent items, and implementations are in use in large scale industrial systems. However, there has not been much comparison of the different methods under uniform experimental conditions. It is common to find papers touching on this topic in which important related work is mischaracterized, overlooked, or reinvented. 
 
In this paper, we aim to present the most important algorithms for this problem in a common framework. We have created baseline implementations of the algorithms, and used these to perform a thorough experimental study of their properties. We give empirical evidence that there is considerable variation in the performance of frequent items algorithms. The best methods can be implemented to find frequent items with high accuracy using only tens of kilobytes of memory, at rates of millions of items per second on cheap modern hardware.
999108
An improved data stream summary: the count-min sketch and its applications
We introduce a new sublinear space data structure--the count-min sketch--for summarizing data streams. Our sketch allows fundamental queries in data stream summarization such as point, range, and inner product queries to be approximately answered very quickly; in addition, it can be applied to solve several important problems in data streams such as finding quantiles, frequent items, etc. The time and space bounds we show for using the CM sketch to solve these problems significantly improve those previously known--typically from 1/e2 to 1/e in factor.
2801140
What's new: finding significant differences in network data streams
Monitoring and analyzing network traffic usage patterns is vital for managing IP Networks. An important problem is to provide network managers with information about changes in traffic, informing them about "what's new". Specifically, we focus on the challenge of finding significantly large differences in traffic: over time, between interfaces and between routers. We introduce the idea of a deltoid: an item that has a large difference, whether the difference is absolute, relative or variational. We present novel algorithms for finding the most significant deltoids in high-speed traffic data, and prove that they use small space, very small time per update, and are guaranteed to find significant deltoids with pre-specified accuracy. In experimental evaluation with real network traffic, our algorithms perform well and recover almost all deltoids. This is the first work to provide solutions capable of working over the data with one pass, at network traffic speeds.
1897822
An Approximate Lp Difference Algorithm for Massive Data Streams
Several recent papers have shown how to approximate the difference ∑ _i|a_i-b_i| or ∑ |a_i-b_i|^2 between two functions, when the function values a_i and b_i are given in a data stream, and their order is chosen by an adversary. These algorithms use little space (much less than would be needed to store the entire stream) and little time to process each item in the stream. They approximate with small relative error. Using different techniques, we show how to approximate the L^p-difference ∑ _i|a_i-b_i|^p for any rational-valued p∈(0,2], with comparable efficiency and error. We also show how to approximate ∑ _i|a_i-b_i|^p for larger values of p but with a worse error guarantee. Our results fill in gaps left by recent work, by providing an algorithm that is precisely tunable for the application at hand. These results can be used to assess the difference between two chronologically or physically separated massive data sets, making one quick pass over each data set, without buffering the data or requiring the data source to pause. For example, one can use our techniques to judge whether the traffic on two remote network routers are similar without requiring either router to transmit a copy of its traffic. A web search engine could use such algorithms to construct a library of small ''sketches,'' one for each distinct page on the web; one can approximate the extent to which new web pages duplicate old ones by comparing the sketches of the web pages. Such techniques will become increasingly important as the enormous scale, distributional nature, and one-pass processing requirements of data sets become more commonplace.
8645568
On Estimating Frequency Moments of Data Streams
Space-economical estimation of the pth frequency moments, defined as , for p> 0, are of interest in estimating all-pairs distances in a large data matrix [14], machine learning, and in data stream computation. Random sketches formed by the inner product of the frequency vector f 1 , ..., f n with a suitably chosen random vector were pioneered by Alon, Matias and Szegedy [1], and have since played a central role in estimating F p and for data stream computations in general. The concept of p-stable sketches formed by the inner product of the frequency vector with a random vector whose components are drawn from a p-stable distribution, was proposed by Indyk for estimating F p , for 0 < p< 2, and has been further studied in Li [13]. 
 
In this paper, we consider the problem of estimating F p , for 0 p , for 0 sketch [7] and the structure [5]. Our algorithms require space $\tilde{O}(\frac{1}{\epsilon^{2+p}})$ to estimate F p to within 1 ±i¾?factors and requires expected time $O(\log F_1 \log \frac{1}{\delta})$ to process each update. Thus, our technique trades an $O(\frac{1}{\epsilon^p})$ factor in space for much more efficient processing of stream updates. We also present a stand-alone iterative estimator for F 1 .
3923409
Stable distributions, pseudorandom generators, embeddings, and data stream computation
In this article, we show several results obtained by combining the use of <i>stable distributions</i> with <i>pseudorandom generators for bounded space</i>. In particular:---We show that, for any <i>p</i> ∈ (0, 2], one can maintain (using only <i>O</i>(log <i>n</i>/ε<sup>2</sup>) words of storage) a <i>sketch</i> <i>C(q)</i> of a point <i>q</i> ∈ <i>l</i><sup><i>n</i></sup><sub><i>p</i></sub> under dynamic updates of its coordinates. The sketch has the property that, given <i>C(q)</i> and <i>C(s)</i>, one can estimate ‖<i>q</i> − <i>s</i>‖<sub><i>p</i></sub> up to a factor of (1 + ε) with large probability. This solves the main open problem of Feigenbaum et al. [1999].---We show that the aforementioned sketching approach directly translates into an approximate algorithm that, for a fixed linear mapping <i>A</i>, and given <i>x</i> ∈ ℜ<sup><i>n</i></sup> and <i>y</i> ∈ ℜ<sup><i>m</i></sup>, estimates ‖<i>Ax</i> − <i>y</i>‖<sub><i>p</i></sub> in <i>O</i>(<i>n</i> + <i>m</i>) time, for any <i>p</i> ∈ (0, 2]. This generalizes an earlier algorithm of Wasserman and Blum [1997] which worked for the case <i>p</i> = 2.---We obtain another sketch function <i>C</i>′ which probabilistically embeds <i>l</i><sup><i>n</i></sup><sub>1</sub> into a <i>normed space</i> <i>l</i><sup><i>m</i></sup><sub>1</sub>. The embedding guarantees that, if we set <i>m</i> = log(1/Δ)<sup><i>O</i>(1/ε)</sup>, then for any pair of points <i>q</i>, <i>s</i> ∈ <i>l</i><sup><i>n</i></sup><sub>1</sub>, the distance between <i>q</i> and <i>s</i> does not <i>increase</i> by more than (1 + ε) with constant probability, and it does not <i>decrease</i> by more than (1 − ε) with probability 1 − Δ. This is the only known dimensionality reduction theorem for the <i>l</i><sub>1</sub> norm. In fact, stronger theorems of this type (i.e., that guarantee very low probability of expansion as well as of contraction) cannot exist [Brinkman and Charikar 2003].---We give an explicit embedding of <i>l</i><sup><i>n</i></sup><sub>2</sub> into <i>l</i><sup><i>n</i><sup><i>O</i>(log <i>n</i>)</sup></sup><sub>1</sub> with distortion (1 + 1/<i>n</i><sup>Θ(1)</sup>).
7911758
Optimal approximations of the frequency moments of data streams
We give a 1-pass <i>Õ</i>(<i>m</i><sup>1-2⁄<i>k</i></sup>)-space algorithm for computing the <i>k</i>-th frequency moment of a data stream for any real <i>k</i> > 2. Together with the lower bounds of [1, 2, 4], this resolves the main problem left open by Alon et al in 1996 [1]. Our algorithm also works for streams with deletions and thus gives an <i>Õ</i>(<i>m</i> <sup>1-2⁄p</sup>) space algorithm for the <i>L</i><i><inf>p</inf></i> difference problem for any p > 2. This essentially matches the known Ω(<i>m</i><sup>1-2⁄<i>p</i>-<i>o</i>(1)</sup>) lower bound of [12, 2]. Finally the update time of our algorithms is <i>Õ</i>(1).
3043343
Estimators and tail bounds for dimension reduction in lα (0 < α ≤ 2) using stable random projections
The method of <i>stable random projections</i> is popular in data stream computations, data mining, information retrieval, and machine learning, for efficiently computing the <i>l</i>α (0 < α ≤ 2) distances using a small (memory) space, in one pass of the data.
 We propose algorithms based on (1) the <i>geometric mean</i> estimator, for all 0 <α ≤ 2, and (2) the <i>harmonic mean</i> estimator, only for small α (e.g., α < 0.344). Compared with the previous classical work [27], our main contributions include:
 • <b>The general sample complexity bound for α ≠ 1,2.</b>
 For α = 1, [27] provided a nice argument based on the inverse of Cauchy density about the median, leading to a sample complexity bound, although they did not provide the constants and their proof restricted ε to be "small enough."
 For general α ≠ 1, 2, however, the task becomes much more difficult. [27] provided the "conceptual promise" that the sample complexity bound similar to that for α = 1 should exist for general α, if a "non-uniform algorithm based on <i>t</i>-quantile" could be implemented. Such a conceptual algorithm was only for supporting the arguments in [27], not a real implementation. We consider this is one of the main problems left open in [27]. In this study, we propose a practical algorithm based on the <i>geometric mean</i> estimator and derive the sample complexity bound for all 0 < α ≤ 2.
 • <b>The practical and optimal algorithm for α = 0+</b>
 The <i>l</i><sub>0</sub> norm is an important case. <i>Stable random projections</i> can provide an approximation to the <i>l</i><sub>0</sub> norm using α → 0+. We provide an algorithm based on the <i>harmonic mean</i> estimator, which is simple and statistically optimal. Its tail bounds are sharper than the bounds derived based on the <i>geometric mean.</i> We also discover a (possibly surprising) fact: in <i>boolean</i> data, <i>stable random projections</i> using α = 0+ with the <i>harmonic mean</i> estimator will be about <i>twice</i> as accurate as <i>(l</i><sub>2</sub><i>) normal random projections.</i> Because high-dimensional boolean data are common, we expect this fact will be practically quite useful.
 • <b>The precise theoretical analysis and practical implications</b> We provide the precise constants in the tail bounds for both the <i>geometric mean</i> and <i>harmonic mean</i> estimators. We also provide the variances (either exact or asymptotic) for the proposed estimators. These results can assist practitioners to choose sample sizes accurately.
2840261
Effective Computations on Sliding Windows
In the streaming model, elements arrive sequentially and can be observed only once. Maintaining statistics and aggregates is an important and nontrivial task in this model. These tasks become even more challenging in the sliding windows model, where statistics must be maintained only over the most recent $n$ elements. In their pioneering paper, Datar et al. [SIAM J. Comput., 31 (2002), pp. 1794-1813] presented the exponential histogram, an effective method for estimating statistics on sliding windows. In this paper we present a novel smooth histogram method that is more general and achieves stronger bounds than the exponential histogram. In particular, the smooth histogram method improves the approximation error rate obtained via exponential histograms. Furthermore, the smooth histogram method not only captures and improves multiple previous results on sliding windows but also extends the class of functions that can be approximated on sliding windows. In particular, we provide the first approximation algorithms for the following functions: $L_p$ norms, frequency moments, the length of the increasing subsequence, and the geometric mean.
122554061
Smooth Histograms for Sliding Windows
In the streaming model elements arrive sequentially and can be observed only once. Maintaining statistics and aggregates is an important and non-trivial task in the model. This becomes even more challenging in the sliding windows model, where statistics must be maintained only over the most recent n elements. In their pioneering paper, Datar, Gionis, Indyk and Motwani [15] presented exponential histograms, an effective method for estimating statistics on sliding windows. In this paper we present a new smooth histograms method that improves the approximation error rate obtained via exponential histograms. Furthermore, our smooth histograms method not only captures and improves multiple previous results on sliding windows bur also extends the class functions that can be approximated on sliding windows. In particular, we provide the first approximation algorithms for the following functions: Lp norms for p notin [1,2], frequency moments, length of increasing subsequence and geometric mean.
40797538
Optimal sampling from sliding windows
A sliding windows model is an important case of the streaming model, where only the most ''recent'' elements remain active and the rest are discarded. The sliding windows model is important for many applications (see, e.g., Babcock, Babu, Datar, Motwani and Widom (PODS 02); and Datar, Gionis, Indyk and Motwani (SODA 02)). There are two equally important types of the sliding windows model - windows with fixed size (e.g., where items arrive one at a time, and only the most recent n items remain active for some fixed parameter n), and timestamp-based windows (e.g., where many items can arrive in ''bursts'' at a single step and where only items from the last t steps remain active, again for some fixed parameter t). Random sampling is a fundamental tool for data streams, as numerous algorithms operate on the sampled data instead of on the entire stream. Effective sampling from sliding windows is a nontrivial problem, as elements eventually expire. In fact, the deletions are implicit; i.e., it is not possible to identify deleted elements without storing the entire window. The implicit nature of deletions on sliding windows does not allow the existing methods (even those that support explicit deletions, e.g., Cormode, Muthukrishnan and Rozenbaum (VLDB 05); Frahling, Indyk and Sohler (SOCG 05)) to be directly ''translated'' to the sliding windows model. One trivial approach to overcoming the problem of implicit deletions is that of over-sampling. When k samples are required, the over-sampling method maintains k^'>k samples in the hope that at least k samples are not expired. The obvious disadvantages of this method are twofold:(a)It introduces additional costs and thus decreases the performance; and (b)The memory bounds are not deterministic, which is atypical for streaming algorithms (where even small probability events may eventually happen for a stream that is long enough). Babcock, Datar and Motwani (SODA 02), were the first to stress the importance of improvements to over-sampling. They formally introduced the problem of sampling from sliding windows and improved the over-sampling method for sampling with replacement. Their elegant solutions for sampling with replacement are optimal in expectation, and thus resolve disadvantage (a) mentioned above. Unfortunately, the randomized bounds do not resolve disadvantage (b) above. Interestingly, all algorithms that employ the ideas of Babcock, Datar and Motwani have the same central problem of having to deal with a randomized complexity bound (see, e.g., Datar and Muthukrishnan (ESA 02); Chakrabarti, Cormode and McGregor (SODA 07)). Further, the proposed solutions of Babcock, Datar and Motwani for sampling without replacement are based on the over-sampling method and thus do not solve problem (a). Therefore, the question of whether we can solve sampling on sliding windows optimally (i.e., resolve both disadvantages) is implicit in the paper of Babcock, Datar and Motwani and has remained open for all variants of the problem. In this paper we answer these questions affirmatively and provide optimal sampling schemas for all variants of the problem, i.e., sampling with or without replacement from fixed or timestamp-based windows. Specifically, for fixed-size windows, we provide optimal solutions that require O(k) memory; for timestamp-based windows, we show algorithms that require O(klogn) space,^1 which is optimal since it matches the lower bound by Gemulla and Lehner (SIGMOD 08). In contrast to the work of Babcock, Datar and Motwani, our solutions have deterministic bounds.
1015745
Measuring independence of datasets
Approximating pairwise, or k-wise, independence with sublinear memory is of considerable importance in the data stream model. In the streaming model the joint distribution is given by a stream of k-tuples, with the goal of testing correlations among the components measured over the entire stream. Indyk and McGregor (SODA 08) recently gave exciting new results for measuring pairwise independence in this model.
 Statistical distance is one of the most fundamental metrics for measuring the similarity of two distributions, and it has been a metric of choice in many papers that discuss distribution closeness. For pairwise independence, the Indyk and McGregor methods provide log{n}-approximation under statistical distance between the joint and product distributions in the streaming model. Indyk and McGregor leave, as their main open question, the problem of improving their log n-approximation for the statistical distance metric.
 In this paper we solve the main open problem posed by Indyk and McGregor for the statistical distance for pairwise independence and extend this result to any constant k. In particular, we present an algorithm that computes an (ε, δ)-approximation of the statistical distance between the joint and product distributions defined by a stream of k-tuples. Our algorithm requires O((1/ε log(nm/δ))(30+k)k) memory and a single pass over the data stream.