检索结果-内蒙古大学图书馆

The Frequent Items Problem in Online streaming Under Various Performance Measures

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2015年第4期26卷 413-439页

作者： Boyar, Joan Larsen, Kim S. Maiti, Abyayananda Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense M Denmark

This is a contribution to the ongoing study of properties of perform nose measures for online algorithms. It has long been known that competitive analysis suffers from drawbacks in certain situations, and many alternative measures have been proposed. More systematic comparative studies of performance measures have been initiated recently, and we continue this work, considering competitive analysis, relative interval analysis, and relative worst order analysis on the frequent items problem, a fundamental online streaming problem.

关键词： Online algorithms streaming algorithms performance measures

来源：评论

学校读者我要写书评

暂无评论

Mergeable summaries 12

Mergeable summaries

引用

31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '12

作者： Agarwal, Pankaj K. Cormode, Graham Huang, Zengfeng Phillips, Jeff Wei, Zhewei Yi, Ke Duke University Durham NC United States AT and T Labs.-Research United States HKUST Hong Kong Hong Kong University of Utah Salt Lake City UT United States

ISBN: (纸本)9781450312486

We study the mergeability of data summaries. Informally speaking, mergeability requires that, given two summaries on two data sets, there is a way to merge the two summaries into a single summary on the union of the two data sets, while preserving the error and size guarantees. This property means that the summaries can be merged in a way like other algebraic operators such as sum and max, which is especially useful for computing summaries on massive distributed data. Several data summaries are trivially mergeable by construction, most notably all the sketches that are linear functions of the data sets. But some other fundamental ones like those for heavy hitters and quantiles, are not (known to be) mergeable. In this paper, we demonstrate that these summaries are indeed mergeable or can be made mergeable after appropriate modifications. Specifically, we show that for Ε-approximate heavy hitters, there is a deterministic mergeable summary of size O(1/Ε) for Ε-approximate quantiles, there is a deterministic summary of size O(1/Ε log(Εn))that has a restricted form of mergeability, and a randomized one of size O(1/Ε log 3/21/Ε) with full mergeability. We also extend our results to geometric summaries such as Ε-approximations and Εkernels. We also achieve two results of independent interest: (1) we provide the best known randomized streaming bound for Ε-approximate quantiles that depends only on Ε, of size O(1/Ε log 3/21/Ε, and (2) we demonstrate that the MG and the SpaceSaving summaries for heavy hitters are isomorphic. © 2012 ACM.

关键词： streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximating Semi-matchings in streaming and in Two-Party Communication

引用

ACM TRANSACTIONS ON algorithms 2016年第3期12卷 32-32页

作者： Konrad, Christian Rosen, Adi Reykjavik Univ Sch Comp Sci Dept Comp Sci Menntavegur 1 IS-101 Reykjavik Iceland Univ Paris 07 IRIF Case 7014 F-75205 Paris 13 France

We study the streaming complexity and communication complexity of approximating unweighted semi-matchings. A semi-matching in a bipartite graph G = (A, B, E) with n = vertical bar A vertical bar is a subset of edges S subset of E that matches all A vertices to B vertices with the goal usually being to do this as fairly as possible. While the term semi-matching was coined in 2003 by Harvey et al. [2003], the problem had already previously been studied in the scheduling literature under different names. We present a deterministic one-pass streaming algorithm that for any 0 <= epsilon <= 1 uses space (O) over tilde (n(1+epsilon)) and computes an O(n((1-epsilon)/2))-approximation to the semi-matching problem. Furthermore, with O(log n) passes it is possible to compute an O(log n)-approximation with space (O) over tilde (n). In the one-way two-party communication setting, we show that for every epsilon > 0, deterministic communication protocols for computing an O(n(1/(1+epsilon)c+ 1))-approximation require a message of size more than cn bits. We present two deterministic protocols communicating n and 2n edges that compute an O(root n) and an O(n(1/3))-approximation, respectively. Finally, we improve on the results of Harvey et al. [2003] and prove new links between semi-matchings and matchings. While it was known that an optimal semi-matching contains a maximum matching, we show that there is a hierarchical decomposition of an optimal semi-matching into maximum matchings. A similar result holds for semi-matchings that do not admit length-two degree-minimizing paths. Categories and Subject Descriptors: F.2.2. [Theory of Computation]: Analysis of algorithms and Problem Complexity-Nonnumerical algorithms and problems

关键词： algorithms Theory Semi-matchings job assignment streaming algorithms communication complexity

来源：评论

学校读者我要写书评

暂无评论

Truly Perfect Samplers for Data Streams and Sliding Windows 22

Truly Perfect Samplers for Data Streams and Sliding Windows

引用

41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Jayaram, Rajesh Woodruff, David P. Zhou, Samson Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450392600

In the G-sampling problem, the goal is to output an index i of a vector f is an element of R-n, such that for all coordinates j is an element of [n], Pr[i = j] = (1 +/- epsilon) G(f(j))/Sigma(k is an element of[n]) G(f(k)) + gamma, where : R -> R->= 0 is some non-negative function. If epsilon = 0 and gamma = 1/poly(n), the sampler is called perfect. In the data stream model, integral is defined implicitly by a sequence of updates to its coordinates, and the goal is to design such a sampler in small space. Jayaram and Woodruff (FOCS 2018) gave the first perfect L-p samplers in turnstile streams, where G(x) = vertical bar x vertical bar(p), using polylog(n) space for p is an element of (0, 2]. However, to date all known sampling algorithms are not truly perfect, since their output distribution is only point-wise gamma = 1/poly(n) close to the true distribution. This small error can be significant when samplers are run many times on successive portions of a stream, and leak potentially sensitive information about the data stream. In this work, we initiate the study of truly perfect samplers, with epsilon = gamma = 0, and comprehensively investigate their complexity in the data stream and sliding window models. We begin by showing that sublinear space truly perfect sampling is impossible in the turnstile model, by proving a lower bound of Omega (min {n, log 1/gamma}) for any G-sampler with point-wise error gamma from the true distribution. We then give a general time-efficient sublinear-space framework for developing truly perfect samplers in the insertion-only streaming and sliding window models. As specific applications, our framework addresses L-p sampling for all p > 0, e.g., (O) over tilde (n(1-1/p)) space for p >= 1, concave functions, and a large number of measure functions, including the L-1 - L-2, Fair, Huber, and Tukey estimators. The update time of our truly perfect L-p-samplers is O (1), which is an exponential improvement over the running time of previous p

关键词： streaming algorithms sampling sliding window model

来源：评论

学校读者我要写书评

暂无评论

TIGHT BOUNDS FOR SINGLE-PASS streaming COMPLEXITY OF THE SET COVER PROBLEM

引用

SIAM JOURNAL ON COMPUTING 2021年第3期50卷 STOC16-341-STOC16-376页

作者： Assadi, Sepehr Khanna, Sanjeev Li, Yang Univ Penn Dept Comp & Informat Sci Philadelphia PA 19104 USA

We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an alpha-approximate set cover (for any alpha = o(root n/ log n)) using a single-pass streaming algorithm, we show that Theta(mn/alpha) space is both sufficient and necessary (up to an O(log n) factor);here m denotes the number of sets and n denotes the size of the universe. This provides a strong negative answer to the open question posed by Har-Peled et al. [Towards tight bounds for the streaming set cover problem, in Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS '16), pp. 371-383] regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sublinear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets) and establish that an additional factor of alpha savings in the space is achievable in this case and is the best possible. In other words, we show that Theta (mn/alpha(2)) space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of alpha. Our algorithm, in fact, works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances, where the sets are presented in a random order.

关键词： streaming algorithms communication complexity set cover covering integer programs

来源：评论

学校读者我要写书评

暂无评论

Tracking the 2 norm with constant update time 22

Tracking the 2 norm with constant update time

引用

22nd International Conference on Approximation algorithms for Combinatorial Optimization Problems and 23rd International Conference on Randomization and Computation, APPROX/RANDOM 2019

作者： Chou, Chi-Ning Lei, Zhixian Nakkiran, Preetum School of Engineering and Applied Sciences Harvard University CambridgeMA United States

ISBN: (纸本)9783959771252

The 2 tracking problem is the task of obtaining a streaming algorithm that, given access to a stream of items a1, a2, a3, . . . from a universe [n], outputs at each time t an estimate to the 2 norm of the frequency vector f(t) ∈ n (where fi(t) is the number of occurrences of item i in the stream up to time t). The previous work [Braverman-Chestnut-Ivkin-Nelson-Wang-Woodruff, PODS 2017] gave a streaming algorithm with (the optimal) space using O(∊−2 log(1/δ)) words and O(∊−2 log(1/δ)) update time to obtain an ∊-accurate estimate with probability at least 1 − δ. We give the first algorithm that achieves update time of O(log 1/δ) which is independent of the accuracy parameter ∊, together with the nearly optimal space using O(∊−2 log(1/δ)) words. Our algorithm is obtained using the Count Sketch of [Charilkar-Chen-Farach-Colton, ICALP 2002]. © Chi-Ning Chou, Zhixian Lei, and Preetum Nakkiran.

关键词： CountSketch Sketching algorithms streaming algorithms Tracking

来源：评论

学校读者我要写书评

暂无评论

Computing k centers over streaming data for small k

引用

International Journal of Computational Geometry and Applications 2014年第2期24卷 107-123页

作者： Ahn, Hee-Kap Kim, Hyo-Sil Kim, Sang-Sub Son, Wanbin Department of Computer Science and Engineering POSTECH Pohang South Korea

In this paper, we consider the k-center problem for streaming points in Rd. More precisely, we consider the single-pass streaming model, where each point in the stream is allowed to be examined only once and a small a... 详细信息

In this paper, we consider the k-center problem for streaming points in R^d. More precisely, we consider the single-pass streaming model, where each point in the stream is allowed to be examined only once and a small amount of information can be stored in a device. Since the size of memory is much smaller than the size of the data in the streaming model, it is important to develop an algorithm whose space complexity does not depend on the number of input data. We present an approximation algorithm for k = 2 that guarantees a (2 + ε)-factor using O(d/ε) space and update time in arbitrary dimensions for any metric. We show that our algorithm can be extended to approximate an optimal k-center within factor (2 + ε) for k > 2. © 2014 World Scientific Publishing Company.

关键词： approximation algorithms k -center streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

GRAPHZEPPELIN: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams 22

GRAPHZEPPELIN: Storage-Friendly Sketching for Connected Comp...

引用

International Conference on Management of Data (SIGMOD)

作者： Tench, David West, Evan Zhang, Victor Bender, Michael A. Chowdhury, Abiyaz Dellas, J. Ahmed Farach-Colton, Martin Seip, Tyler Zhang, Kenny Rutgers State Univ New Brunswick NJ 08901 USA SUNY Stony Brook Stony Brook NY 11794 USA MongoDB New York NY USA

ISBN: (纸本)9781450392495

Finding the connected components of a graph is a fundamental problem with uses throughout computer science and engineering. The task of computing connected components becomes more difficult when graphs are very large, or when they are dynamic, meaning the edge set changes over time subject to a stream of edge insertions and deletions. A natural approach to computing the connected components on a large, dynamic graph stream is to buy enough RAM to store the entire graph. However, the requirement that the graph fit in RAM is prohibitive for very large graphs. Thus, there is an unmet need for systems that can process dense dynamic graphs, especially when those graphs are larger than available RAM. We present a new high-performance streaming graph-processing system for computing the connected components of a graph. This system, which we call GRAPHZEPPELIN, uses new linear sketching data structures (CUBESKETCH) to solve the streaming connected components problem and as a result requires space asymptotically smaller than the space required for a lossless representation of the graph. GRAPHZEPPELIN is optimized for massive dense graphs: GRAPHZEPPELIN can process millions of edge updates (both insertions and deletions) per second, even when the underlying graph is far too large to fit in available RAM. As a result GRAPHZEPPELIN vastly increases the scale of graphs that can be processed.

关键词： Linear Sketching streaming algorithms External Memory

来源：评论

学校读者我要写书评

暂无评论

Sparsifying Count Sketch

引用

INFORMATION PROCESSING LETTERS 2024年 186卷

作者： Verma, Bhisham Dev Pratap, Rameshwar Dubey, Punit Pankaj Indian Inst Technol Mandi Mandi Himachal Prades India Indian Inst Technol Hyderabad Hyderabad Telangana India

The seminal work of Charikar et al. [1] called COUNT-SKETCH suggests a sketching algorithm for real-valued vectors that has been used in frequency estimation for data streams and pairwise inner product estimation for real-valued vectors etc. One of the major advantages of COUNT-SKETCH over other similar sketching algorithms, such as random projection, is that its running time, as well as the sparsity of sketch, depends on the sparsity of the input. Therefore, sparse datasets enjoy space-efficient (sparse sketches) and faster running time. However, on dense datasets, these advantages of COUNT-SKETCH might be negligible over other baselines. In this work, we address this challenge by suggesting a simple and effective approach that outputs (asymptotically) a sparser sketch than that obtained via COUNT-SKETCH, and as a by-product, we also achieve a faster running time. Simultaneously, the quality of our estimate is closely approximate to that of COUNT-SKETCH. For frequency estimation and pairwise inner product estimation problems, our proposal SPARSE-COUNT-SKETCH provides unbiased estimates. These estimations, however, have slightly higher variances than their respective estimates obtained via COUNT-SKETCH. To address this issue, we present improved estimators for these problems based on maximum likelihood estimation (MLE) that offer smaller variances even w.r.t. COUNT-SKETCH. We suggest a rigorous theoretical analysis of our proposal for frequency estimation for data streams and pairwise inner product estimation for real-valued vectors.

关键词： Frequency estimation Count-sketch Inner product estimation streaming algorithms Sketching algorithms Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Timely Reporting of Heavy Hitters Using External Memory

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2021年第4期46卷 14-14页

作者： Singh, Shikha Pandey, Prashant Bender, Michael A. Berry, Jonathan W. Farach-Colton, Martin Johnson, Rob Kroeger, Thomas M. Phillips, Cynthia A. Williams Coll Dept Comp Sci Williamstown MA 01267 USA VMware Res 3425 Hillview Ave Palo Alto CA 94304 USA SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Sandia Natl Labs Mailstop 1327POB 5800 Albuquerque NM 87185 USA Rutgers State Univ Dept Comp Sci Piscataway NJ 08854 USA

Given an input stream S of size N, a phi-heavy hitter is an item that occurs at least phi N times in S. The problem of finding heavy-hitters is extensively studied in the database literature. We study a real-time heavy-hitters variant in which an element must be reported shortly after we see its T = phi N-th occurrence (and hence it becomes a heavy hitter). We call this the Timely Event Detection (TED) Problem. The TED problem models the needs of many real-world monitoring systems, which demand accurate (i.e., no false negatives) and timely reporting of all events from large, high-speed streams with a low reporting threshold (high sensitivity). Like the classic heavy-hitters problem, solving the TED problem without false-positives requires large space (Omega(N) words). Thus in-RAM heavy-hitters algorithms typically sacrifice accuracy (i.e., allow false positives), sensitivity, or timeliness (i.e., use multiple passes). We show how to adapt heavy-hitters algorithms to external memory to solve the TED problem on large high-speed streams while guaranteeing accuracy, sensitivity, and timeliness. Our data structures are limited only by I/O-bandwidth (not latency) and support a tunable tradeoff between reporting delay and I/O overhead. With a small bounded reporting delay, our algorithms incur only a logarithmic I/O overhead. We implement and validate our data structures empirically using the Firehose streaming benchmark. Multi-threaded versions of our structures can scale to process 11M observations per second before becoming CPU bound. In comparison, a naive adaptation of the standard heavy-hitters algorithm to external memory would be limited by the storage device's random I/O throughput, i.e., approximate to 100K observations per second.

关键词： Dictionary data structure streaming algorithms external-memory algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：