This paper considers online compression algorithms that use at most polylogarithmic space (plogon). These algorithms correspond to compressors in the datastream model. We study the performance attained by these algor...
详细信息
ISBN:
(纸本)9783540958901
This paper considers online compression algorithms that use at most polylogarithmic space (plogon). These algorithms correspond to compressors in the datastream model. We study the performance attained by these algorithms and show they are incomparable with both pushdown compressors and the Lempel-Ziv compression algorithm.
This work evaluates the OGK (On a Good Knowledge), an in-network datastream based reduction algorithm for real-time wireless sensor network (WSN) applications. OGK uses the knowledge about the stream items to choose ...
详细信息
ISBN:
(纸本)9781605582382
This work evaluates the OGK (On a Good Knowledge), an in-network datastream based reduction algorithm for real-time wireless sensor network (WSN) applications. OGK uses the knowledge about the stream items to choose the appropriate reduction solution in real-time WSN applications. OCK is integrated in forward tree routing phase to allow the stream item reduction, by routing nodes, when the stream item cannot be delivered on time. Simulation results reveal the efficiency of OGK in achieving the deadlines without loosing data representativeness in real-time applications.
Given m distributed datastreams A1, . . . ,Am, we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over A1, . . . ,Am. We identify a broad class of algorithms ...
详细信息
The notion of L-p sampling, and corresponding algorithms known as L-p samplers, has found a wide range of applications in the design of data stream algorithms and beyond. In this survey, we present some of the core al...
详细信息
The notion of L-p sampling, and corresponding algorithms known as L-p samplers, has found a wide range of applications in the design of data stream algorithms and beyond. In this survey, we present some of the core algorithms to achieve this sampling distribution based on ideas from hashing, sampling, and sketching. We give results for the special cases of insertion-only inputs, lower bounds for the sampling problems, and ways to efficiently sample multiple elements. We describe a range of applications of L-p sampling, drawing on problems across the domain of computer science, from matrix and graph computations, as well as to geometric and vector streaming problems.
stream monitoring is fundamental in many datastream applications, such as financial data trackers, security, anomaly detection, and load balancing. In that respect, quantiles are of particular interest, as they often...
详细信息
stream monitoring is fundamental in many datastream applications, such as financial data trackers, security, anomaly detection, and load balancing. In that respect, quantiles are of particular interest, as they often capture the user's utility. For example, if a video connection has high tail (e.g., 99'th percentile) latency, the perceived quality will suffer, even if the average and median latencies are *** this work, we consider the problem of approximating the per-item quantiles. Elements in our stream are (ID, value) tuples, and we wish to track the quantiles for each ID. Existing quantile sketches are designed for a plain number stream (i.e., containing just a value). While one could allocate a separate sketch instance for each ID, this may require an infeasible amount of memory. Instead, we consider tracking the quantiles for the heavy hitters (most frequent items), which are often considered particularly important, without knowing them *** first present a couple of simple and effective algorithms that serve as baselines, a sampling approach and a sketching approach. Then, we present SQUAD, an algorithm that combines sampling and sketching while improving the asymptotic space complexity. Intuitively, SQUAD uses a background sampling process to capture the behaviour of the quantiles of an item before it is allocated with a sketch, thereby allowing us to use fewer samples and sketches. The algorithms are rigorously analyzed, and we demonstrate SQUAD's superiority using extensive~simulations on real-world traces.
Given a graph G = (V, E), for a vertex set S subset of V, let N(S) denote the set of vertices in V that have a neighbor in S. Extending the concept of binding number of graphs by Woodall (1973), for a vertex set X sub...
详细信息
Given a graph G = (V, E), for a vertex set S subset of V, let N(S) denote the set of vertices in V that have a neighbor in S. Extending the concept of binding number of graphs by Woodall (1973), for a vertex set X subset of V, we define the binding number of X, denoted by bind(X), as the maximum number b such that for every S subset of X where N(S) not equal V(G) it holds that vertical bar N(S)vertical bar >= b vertical bar S vertical bar. Given this definition, we prove that if a graph V(G) contains a subset X with bind (X) = 1/k where k is an integer, then G possesses a matching of size at least vertical bar X vertical bar/(k + 1). Using this statement, we derive tight bounds for the estimators of the matching size in planar graphs. These estimators are previously used in designing sublinear space algorithms for approximating the matching size in the datastream model of computation. In particular, we show that the number of locally superior vertices is a 3 factor approximation of the matching size in planar graphs. The previous analysis by Jowhari (2023) proved a 3.5 approximation factor. As another application, we show a simple variant of an estimator by Esfandiari et al. (2015) achieves 3factor approximation of the matching size in planar graphs. Namely, let s be the number of edges with both endpoints having degree at most 2 and let h be the number of vertices with degree at least 3. We prove that when the graph is planar, the size of matching is at least (s + h)/3. This result generalizes a known fact that every planar graph on n vertices with minimum degree 3 has a matching of size at least n/3. (c) 2024 Elsevier B.V. All rights reserved.
暂无评论