We consider the problem of sketching the $p$-th frequency moment of a vector, $p>2$, with multiplicative error at most $1\pm ε$ and \emph{with high confidence} $1-δ$. Despite the long sequence of work on this problem, tight bounds on this quantity are only known for constant $δ$. While one can obtain an upper bound with error probability $δ$ by repeating a sketching algorithm with constant error probability $O(\log(1/δ))$ times in parallel, and taking the median of the outputs, we show this is a suboptimal algorithm! Namely, we show optimal upper and lower bounds of $Θ(n^{1-2/p} \log(1/δ) + n^{1-2/p} \log^{2/p} (1/δ) \log n)$ on the sketching dimension, for any constant approximation. Our result should be contrasted with results for estimating frequency moments for $1 \leq p \leq 2$, for which we show the optimal algorithm for general $δ$ is obtained by repeating the optimal algorithm for constant error probability $O(\log(1/δ))$ times and taking the median output. We also obtain a matching lower bound for this problem, up to constant factors.

Effective mechanisms for detecting and thwarting distributed denial-of-service (DDoS) attacks are becoming increasingly important to the success of today's Internet as a viable commercial and business tool. In this paper, we propose novel data-streaming algorithms for the robust, real-time detection of DDoS activity in large ISP networks. The key element of our solution is a new, hash-based synopsis data structure for network-data streams that allows us to efficiently track, in guaranteed small space and time, destination IP addresses in the underlying network that are "large" with respect to the number of distinct source IP addresses that have established potentially-malicious (e.g., "half-open") connections to them. Our work is the first to address the problem of efficiently tracking the top distinct-source frequencies over a general stream of updates (insertions and deletions) to the set of underlying network flows, thus enabling us to effectively distinguish between DDoS activity and flash crowds. Preliminary experimental results verify the effectiveness of our approach.

A k-set structure over data streams is a bounded-space data structure that supports stream insertion and deletion operations and returns the set of (item, frequency) pairs in the stream, provided, the number of distinct items in the stream does not exceed k; and returns nil otherwise. This is a fundamental problem with applications in data streaming [14], data reconciliation in distributed systems [12] and mobile computing [16], etc. In this paper, we present a deterministic algorithm for the k-set problem that matches the space lower bound to within a logarithmic factor.

There is growing interest in algorithms for processing and querying continuous data streams (i.e., data that is seen only once in a fixed order) with limited memory resources. Providing (perhaps approximate) answers to queries over such streams is a crucial requirement for many application environments; examples include large IP network installations where performance data from different parts of the network needs to be continuously collected and analyzed.

No abstract available.

There is growing interest in algorithms for processing and querying continuous data streams (i.e., data that is seen only once in a fixed order) with limited memory resources. In its most general form, a data stream is actually an update stream, i.e., comprising data-item deletions as well as insertions. Such massive update streams arise naturally in several application domains (e.g., monitoring of large IP network installations, or processing of retail-chain transactions).Estimating the cardinality of set expressions defined over several (perhaps, distributed) update streams is perhaps one of the most fundamental query classes of interest; as an example, such a query may ask "what is the number of distinct IP source addresses seen in passing packets from both router R1 and R2 but not router R3?". Earlier work has only addressed very restricted forms of this problem, focusing solely on the special case of insert-only streams and specific operators (e.g., union). In this paper, we propose the first space-efficient algorithmic solution for estimating the cardinality of full-fledged set expressions over general update streams. Our estimation algorithms are probabilistic in nature and rely on a novel, hash-based synopsis data structure, termed "2-level hash sketch". We demonstrate how our 2-level hash sketch synopses can be used to provide low-error, high-confidence estimates for the cardinality of set expressions (including operators such as set union, intersection, and difference) over continuous update streams, using only small space and small processing time per update. Furthermore, our estimators never require rescanning or resampling of past stream items, regardless of the number of deletions in the stream. We also present lower bounds for the problem, demonstrating that the space usage of our estimation algorithms is within small factors of the optimal. Preliminary experimental results verify the effectiveness of our approach.

In this work, we study the complexity of the problem of approximate query optimization. We show that, for any δ > 0, the problem of finding a join order sequence whose cost is within a factor 2Θ(log1-δ(K)) of K, where K is the cost of the optimal join order sequence is NP-Hard. The complexity gap remains if the number of edges in the query graph is constrained to be a given function e(n) of the number of vertices n of the query graph, where n(n - 1)/2 - Θ(nτ) ≥ e(n) ≥ n + Θ(nτ) and τ is any constant between 0 and 1. These results show that, unless P=NP, the query optimization problem cannot be approximately solved by an algorithm that runs in polynomial time and has a competitive ratio that is within some polylogarithmic factor of the optimal cost.

This paper introduces bifocal sampling, a new technique for estimating the size of an equi-join of two relations. Bifocal sampling classifies tuples in each relation into two groups, sparse and dense, based on the number of tuples with the same join value. Distinct estimation procedures are employed that focus on various combinations for joining tuples (e.g., for estimating the number of joining tuples that are dense in both relations). This combination of estimation procedures overcomes some well-known problems in previous schemes, enabling good estimates with no a priori knowledge about the data distribution. The estimate obtained by the bifocal sampling algorithm is proven to lie with high probability within a small constant factor of the actual join size, regardless of the skew, as long as the join size is Ω(n lg n), for relations consisting of n tuples. The algorithm requires a sample of size at most O(√n lg n). By contrast, previous algorithms using a sample of similar size may require the join size to be Ω(n√n) to guarantee an accurate estimate. Experimental results support the theoretical claims and show that bifocal sampling is practical and effective.

The problem of mapping the parallel bottom up execution of Datalog programs to an interconnected network of processors is studied. The parallelization is achieved by using hash functions that partition the set of instantiations for the rules. We first examine this problem in an environment where the number of processors and the interconnection topology is known, and communication between program segments residing at non-adjacent processors is not permitted. An algorithm is presented that decides whether a given Datalog program can be mapped onto such an architecture. We then relax the constraint on the architecture by allowing program segments residing at non-adjacent processors to communicate, A theory of approximate mappings is developed, and an algorithm to obtain the closest approximate mapping of a given Datalog program onto a given architecture is presented.>

The greedy paradigm of algorithm design is a well known tool used for efficiently solving many classical computational problems within the framework of procedural languages. However, it is very difficult to express these algorithms within the declarative framework of logic-based languages. In this paper, we extend the framework of Datalog-like languages to provide simple and declarative formulations of such problems, with computational complexities comparable to those of procedural formulations. This is achieved through the use of constructs, such as least and choice, that have semantics reducible to that of negative programs under stable model semantics. Therefore, we show that the formulation of greedy algorithms using these constructs lead to a syntactic class of programs, called stage-stratified programs, that are easily recognized at compile time. The fixpoint-based implementation of these recursive programs is very efficient and, combined with suitable storage structures, yields asymptotic complexities comparable to those obtained using procedural languages.

The decreasing cost of computing makes it economically viable to reduce the response time of decision support queries by using parallel execution to exploit inexpen-sive resources. This goal poses the following query op-timization problem: Mzntmzze response ttme subject to constraints on throughput, which we motivate as the dual of the traditional DBMS problem, We address this novel problem in the context of Select-Project-Join queries by extending the execution space, cost model and search al-gorithm that are widely used in commercial DBItlSs. We incorporate the sources and deterrents of parallelism in the traditional execution space. We show that a cost model can predict response time while accounting for the new aspects due to parallelism, We observe that the response time optimization metric violates a fundamen-tal assumption in the dynamic programming algorithm that is the linchpin in the optimizers of most commer-cial DBMSS. We extend dynamic programming and show how optimization metrics which correctly predict response time may be designed. 1

A novel experimental procedure, based on a standard statistical estimation procedure, is presented to estimate the performance of transitive closure algorithms. This experimental procedure has been exemplified in three contexts: (1) comparison of a suite of algorithms: (2) analysis of one particular algorithm; and (3) analysis of the transitive closure problem itself. It is shown that the number of duplicate edges generated (by most algorithms) can be more than ten times the size of the transitive closure, even for small graphs. The majority of these duplicates are due to the existence of strongly connected components in the graph. This experimental approach can be generalized to estimate various performance metrics for a large class of database queries. It is both simple and general and provides the necessary ingredients for a guess-and-verify paradigm of testing hypotheses.>

A novel approach is proposed for ezpressing and computing efficiently a large class of problems, including finding the shortest path in a graph, that were previously considered impervious to an efficient treatment in the declarative framework of logic-based languages. Our approach is based on the use of rain and max predicates having a first-order semantics defined using rules with negation in their bodies. We show that when cer- tain monotonictry conditions hold then (1) there ezists a totM well-founded model for these programs contain- ing negation, () this model can be computed efciently using a procedure called greedy flxpoint, and (3) the original program can be rewritten into a more efficient one by pushing rain and max predicates into recursion.

This paper presents several complementary methods for the parallel, bottom-up evaluation of Datalog queries. We introduce the notion of a discriminating predicate, based on hash functions, that partitions the computation between the processors in order to achieve parallelism. A parallelization scheme with the property of non-redundant computation (no duplication of computation by processors) is then studied in detail. The mapping of Datalog programs onto a network of processors, such that the results is a non-redundant computation, is also studied. The methods reported in this paper clearly demonstrate the trade-offs between redundancy and interprocessor-communication for this class of problems.