In this paper, we present an advanced analysis of near optimal algorithms that use limited space to solve the frequency estimation, heavy hitters, frequent items, and top-k approximation in the bounded deletion model. We define the family of SpaceSaving± algorithms and explain why the original SpaceSaving± algorithm only works when insertions and deletions are not interleaved. Next, we propose the new Double SpaceSaving±, Unbiased Double SpaceSaving±, and Integrated SpaceSaving± algorithms and prove their correctness. The three proposed algorithms represent different trade-offs, in which Double SpaceSaving± can be extended to provide unbiased estimations while Integrated SpaceSaving± uses less space. Since data streams are often skewed, we present an improved analysis of these algorithms and show that errors do not depend on the hot items. We also demonstrate how to achieve relative error guarantees under mild assumptions. Moreover, we establish that the important mergeability property is satisfied by all three algorithms, which is essential for running the algorithms in distributed settings.

This errata article points out an implicit assumption in the work of four of us published in VLDB 2022. The SpaceSaving± algorithm in bounded deletion data stream presented in the paper implicitly assumed deletions happen after all insertions. When insertions and deletions are interleaved, that algorithm may severely underestimate item's frequency. We first illustrate this phenomenon by an example and then present a modified algorithm with minor changes to allow interleaving between insertions and deletions. We also include a pointer to a full analysis of the new algorithms.

We study how to detect clusters in a graph defined by a stream of edges, without storing the entire graph. We extend the approach to dynamic graphs defined by the most recent edges of the stream and to several streams. The content correlation of two streams ρ(t) is the Jaccard similarity of their clusters in the windows before time t. We propose a simple and efficient method to approximate this correlation online and show that for dynamic random graphs which follow a power law degree distribution, we can guarantee a good approximation. As an application, we follow Twitter streams and compute their content correlations online. We then propose a search by correlation where answers to sets of keywords are entirely based on the small correlations of the streams. Answers are ordered by the correlations, and explanations can be traced with the stored clusters.

In the context of formal language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al., a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs of the language from those that are eps-far from it, while using the smallest possible memory (rather than limiting its number of input queries). Our main result is a streaming eps-property tester for visibly pushdown languages (V_{PL}) with memory space poly(log n /epsilon). Our construction is done in three steps. First, we simulate a visibly pushdown automaton in one pass using a stack of small height but whose items can be of linear size. In a second step, those items are replaced by small sketches. Those sketches rely on a notion of suffix-sampling we introduce. This sampling is the key idea for taking benefit of both streaming algorithms and property testers in the third step. Indeed, the last step relies on a (non-streaming) property tester for weighted regular languages based on a previous tester by Alon et al. This tester can directly be used for streaming testing special cases of instances of V_{PL} that are already hard for both streaming algorithms and property testers. We then use it to decide the correctness of completed items, given their sketches, before removing them from the stack.

We study analytical queries for two models of Social Networks. Firstly, a datawarehouse which can be analyzed along some OLAP schema and possible dimensions, secondly a model of streaming data which need to be transformed before they are analyzed. In the first case, the linear influence model is generalized for each possible dimensions and provides densities of influence types. In the second case, we need to approximate the analytical queries by sampling the data along some specific distributions. For a model of analytical queries on graphs and their approximations, we give examples of approximable and non approximable queries. We introduce a measure to quantify the information provided by various analyses using both the Entropy of the answer to the query and of the influence types. We illustrate the approach on Facebook and Twitter data.

We consider a cloud as a cluster of processors holding each a large XML tree. We present a statistical representation which can be built online on each processor and allows to approximate boolean, unary and Aggregation queries. The main result of the paper shows how these statistics can be efficiently Reduced to a master node of the cloud. We obtain an approximation of the global tree structure built from the elementary trees on each processor. In this StatsReduce model, processors only exchange statistical data with their neighbours. This technique leads to the approximation of Analytics queries on the global tree structure with a quantified confidence.

We study streaming data for a data warehouse, which combines different sources. We consider the relative answers to OLAP queries on a schema, as distributions with the L1 distance and approximate the answers without storing the entire data warehouse. We first study how to sample each source and combine the samples to approximate any OLAP query. We then consider a streaming context, where a data warehouse is built by streams of different sources. We first show a lower bound on the size of the memory necessary to approximate queries and then consider a statistical hypothesis where some attributes determine fixed distributions of the measure. We use the sampling methods to learn the statistical model and approximate OLAP queries. In this case, we approximate OLAP queries with a finite memory. We apply the method to a dataset which simulates the data of sensors, which provide weather parameters over time and locations from different sources.

Inspired by property testing, for every $\varepsilon>0$ we relax the classical satisfiability $U\models F$ between a finite structure U of a class $\mathbf{K}$ and a formula F, to a notion of $\varepsilon$-satisfiability $U\models_{\varepsilon}F$, and relax the classical equivalence $F_1\equiv F_2$ between two formulas $F_1$ and $F_2$ to $\varepsilon$-equivalence $F_1\equiv_{\varepsilon}F_2$. We consider strings and trees with the norm of the edit distance with moves, and show that, unlike their exact counterparts, these approximate notions can be efficiently decided. We use a statistical embedding of words (resp., trees) into $\ell_1$, which generalizes the original Parikh mapping, obtained by sampling $O(f(\varepsilon))$ finite samples of the words (resp., trees). We give a tester for equality and membership in any regular language, in time independent of the size of the structure. Using our geometrical embedding, we can also test the equivalence between two regular properties over words, defined by regular expressions or monadic second-order formulas. Our equivalence tester has polynomial time complexity in the size of the automaton (or regular expression), for any fixed $\varepsilon$, whereas the exact version of the equivalence problem is PSPACE-complete. We also prove versions of some of these results for trees, but with worse time complexity. Last, we extend the geometric embedding, and hence the testing algorithms, to infinite regular languages and to context-free languages. For context-free languages, the equivalence tester has an exponential time complexity for any fixed $\varepsilon$, whereas the exact version is not even decidable.

We associate a statistical vector to a trace and a geometrical embedding to a Markov decision process, based on a distance on words, and study basic membership and equivalence problems. The membership problem for a trace w and a Markov decision process S decides if there exists a strategy on S which generates with high probability traces close to w. We prove that membership of a trace is testable and equivalence of MDPs is polynomial time approximable. For probabilistic automata, membership is not testable, and approximate equivalence is undecidable. We give a class of properties, based on results concerning the structure of the tail sigma-field of a finite Markov chain, which characterizes equivalent Markov decision processes in this context.

We present a SAX implementation of the statistical embedding associated with XML data, introduced in [1], [2], which allows to efficiently decide eps-validity to any DTD or Schema, for the Edit Distance with Moves. It associates a generalized k-gram to unranked labelled trees (with k = 1/epsiv) from which any regular property can be approximately decided. We show how to exactly compute the k-gram with a SAX implementation using a memory of size d, the depth of the tree, and an approximate k-gram with queues of size M = 2kand a global memory of size 2kin the worst-case. Experiments on large XML files from the XML benchmark project confirm the error analysis for various values of M.

The goal of model checking is to verify the correctness of a given program, on all its inputs. The main obstacle, in many cases, is the intractably large size of the program's transition system. Property testing is a randomized method to verify whether some fixed property holds on individual inputs, by looking at a small random part of that input. We join the strengths of both approaches by introducing a new notion of probabilistic abstraction, and by extending the framework of model checking to include the use of these abstractions. Our abstractions map transition systems associated with large graphs to small transition systems associated with small random subgraphs. This reduces the original transition system to a family of small, even constant-size, transition systems. We prove that with high probability, “sufficiently” incorrect programs will be rejected (ε-robustness). We also prove that under a certain condition (exactness), correct programs will never be rejected (soundness). Our work applies to programs for graph properties such as bipartiteness, k -colorability, or any ∃∀ first order graph properties. Our main contribution is to show how to apply the ideas of property testing to syntactic programs for such properties. We give a concrete example of an abstraction for a program for bipartiteness. Finally, we show that the relaxation of the test alone does not yield transition systems small enough to use the standard model checking method. More specifically, we prove, using methods from communication complexity, that the OBDD size remains exponential for approximate bipartiteness.

Inspired by property testing, we relax the classical satisfiability UvDashF between a finite structure U of a class K and a formula F, to a notion of epsiv-satisfiability UvDashepsivF, and the classical equivalence F1equivF2between two formulas F1and F2, to epsiv-equivalence F1equivepsivF2for epsiv>0. We consider the class of strings and trees with the edit distance with moves, and show that these approximate notions can be efficiently decided. We use a statistical embedding of words (resp. trees) into lscr1, which generalizes the original Parikh mapping, obtained by sampling O(f(epsiv)) finite samples of the words (resp. trees). We give a tester for equality and membership in any regular language, in time independent of the size of the structure. Using our geometrical embedding, we can also test the equivalence between two regular properties on words, defined by monadic second order formulas. Our equivalence tester has polynomial time complexity in the size of the automaton (or regular expression), for a fixed epsiv, whereas the exact version of the equivalence problem is PSPACE-complete. Last, we extend the geometric embedding, and hence the tester algorithms, to infinite regular languages and to context-free languages. For context-free languages, the equivalence tester has an exponential time complexity, whereas the exact version is undecidable

The goal of model checking is to verify the correctness of a given program, on all its inputs. The main obstacle, in many cases, is the intractably large size of the program's transition system. Property testing is a randomized method to verify whether some fixed property holds on individual inputs, by looking at a small random part of that input. We join the strengths of both approaches by introducing a new notion of probabilistic abstraction, and by extending the framework of model checking to include the use of these abstractions. Our abstractions map transition systems associated with large graphs to small transition systems associated with small random subgraphs. This reduces the original transition system to a family of small, even constant-size, transition systems. We prove that with high probability, "sufficiently" incorrect programs will be rejected (E-robustness). We also prove that under a certain condition (exactness), correct programs will never be rejected (soundness). Our work applies to programs for graph properties such as bipartiteness, k-colorability, or any /spl exist//spl forall/ first order graph properties. Our main contribution is to show how to apply the ideas of property testing to syntactic programs for such properties. We give a concrete example of an abstraction for a program for bipartiteness. Finally, we show that the relaxation of the test alone does not yield transition systems small enough to use the standard model checking method. More specifically, we prove, using methods from communication complexity, that the OBDD size remains exponential for approximate bipartiteness.

A compression algorithm takes a finite structure of a class K as input and produces a finite structure of a different class K' as output. Given a property P on the class K defined in a logic /spl Lscr/, we study the definability of property P on the class K'. We consider two compression schemas on unary ordered structures (words), compression by runlength encoding and the classical Lempel-Ziv. First-order properties of strings are first-order on runlength compressed strings, but this fails for images, i.e. 2-dimensional strings. We present simple first-order properties of strings which are not first-order definable on strings compressed with the Lempel-Ziv compression schema. We show that all properties of strings that are first-order definable on strings are definable on Lempel-Ziv compressed strings in FO(TC), the extension of first-order logic with the transitive closure operator. We define a subclass /spl Fscr/ of the first-order properties of strings such that if L is defined by a property in /spl Fscr/, it is also first-order definable on the Lempel-Ziv compressed strings. Monadic second-order properties of strings are dyadic second order definable on Lempel-Ziv compressed strings.

We study the efficient approximation of queries in linear constraint databases using sampling techniques. We define the notion of an almost uniform generator for a generalized relation and extend the classical generator of Dyer, Frieze and Kannan for convex sets to the union and the projection of relations. For the intersection and the difference, we give sufficient conditions for the existence of such generators. We show how such generators give relative estimations of the volume and approximations of generalized relations as the composition of convex hulls obtained from the samples.

We introduce classes of narrow graphs (including grid strips of fixed width), for which the graph reliability problem admits a polynomial time algorithm. Using this algorithm, we show that graph reliability is computable in polynomial time for the average complexity with respect to a Gaussian distribution. The latter is defined as follows: the vertices are numbered by integers {1,2, ...n}, and the probability that an edge between i and j is present is e −|i−j| 2 .

In the paper we consider the complexity of constructing optimal policies (strategies) for some type of partially observed Markov decision processes. This particular case of the classical problem deals with finite stationary processes, and can be represented as constructing optimal strategies to reach target vertices from a starting vertex in a graph with colored vertices and probabilistic deviations from an edge chosen to follow. The colors of the visited vertices is the only information available to a strategy. The complexity of Markov decision in the case of perfect information (bijective coloring of vertices) is known and briefly surveyed at the beginning of the paper. For the unobservable case (all the colors are equal) we give an improvement of the result of Papadimitriou and Tsitsiklis, namely we show that the problem of constructing even a very weak approximation to an optimal strategy is NP-hard. Our main results concern the case of a fixed bound on the multiplicity of coloring, that is a case of partially observed processes where some upper bound on the unobservability is supposed. We show that the problem of finding an optimal strategy is still NP-hard, but polytime approximations are possible. Some relations of our results to the Max-Word Problem are also indicated.

We consider an unreliabable database as a random variable defined from a relational database with various probabilistic models.For a given query Q, we define its reliability on a database D15, pQ (lIll), as the probability that the answer to Q on an unreliable random instance coincides with the answer to Q on DB.We investigate the computational complexity of computing PQ (.DB), when Q is defined in various logic-based languages.We show that pQ (DB) is computable in polynomial time when Q is defined in first-order logic and that PQ (Ill?) is P#p computable when Q is defined in Datalog.We then discuss possible ways of estimating the reliability y for natural distributions.

A notion of robustness for planning problems is introduced in a model with uncertainty, based on a global probabilistic model. The authors define the notion of a robust strategy within this model, which allows comparison of different strategies. They then study how an outside observer would know in advance the level of robustness of a system. The analysis is based on the complexity class IP, the class of problems that can be efficiently verified by a random interactive proof system. The approach was applied to a mobile robot trying to execute a plan in a geometrical environment following a strategy that uses various sensors to cope with the uncertainty. Various examples of robust and nonrobust strategies are given.>

We study inductive and second-order definability on finite structures with successor and relate these notions to complexity theory. We introduce the dimension d of an inductive definition, directly related to the Time complexity, representing the number of variables necessary to carry an induction. We will prove the following: