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

29th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Bateni, MohammadHossein Esfandiari, Hossein Mirrokni, Vahab Google Res New York NY 10011 USA Univ Maryland College Pk MD 20742 USA

ISBN: (纸本)9781450345934

Maximum coverage and minimum set cover problems-here collectively called coverage problems-have been studied extensively in streaming models. However, previous research not only achieves suboptimal approximation factors and space complexities but also study a restricted set-arrival model which makes an explicit or implicit assumption on oracle access to the sets, ignoring the complexity of reading and storing the whole set at once. In this paper, we address the above shortcomings and present algorithms with improved approximation factor and improved space complexity, and prove that our results are almost tight. Moreover, unlike most of the previous work, our results hold in a more general edge-arrival model. More specifically, consider an instance with n sets, together covering m elements. Information arrives in the form of "edges" from sets to elements (denoting membership) in arbitrary order. (1) We present (almost) optimal approximation algorithms for maximum coverage and minimum set cover problems in the streaming model with an (almost) optimal space complexity of (O) over tilde (n);i.e., the space is independent of the size of the sets or the size of the ground set of elements. These results not only improve the best known algorithms for the set-arrival model, but also are the first such algorithms for the more powerful edge-arrival model. (2) In order to achieve the above results, we introduce a new general sketching technique for coverage functions: One can apply this sketching scheme to convert an alpha-approximation algorithm for a coverage problem to a (1-epsilon) alpha-approximation algorithm for the same problem in streaming model. (3) We show the significance of our sketching technique by ruling out the possibility of solving coverage problems via accessing (as a black box) a (1 +/-epsilon)-approximate oracle (e.g., a sketch function) that estimates the coverage function on any subfamily of the sets. Finally, we show that our streaming algorithms achiev

关键词： set cover distributed algorithm coverage maximization submodular maximization streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved streaming algorithms for Maximum Directed Cut via Smoothed Snapshots 64

Improved Streaming Algorithms for Maximum Directed Cut via S...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Saxena, Raghuvansh R. Singer, Noah G. Sudan, Madhu Velusamy, Santhoshini Tata Inst Fundamental Res Mumbai Maharashtra India Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA USA Harvard Univ Sch Engn & Appl Sci Cambridge MA USA Toyota Technol Inst Chicago Chicago IL USA

ISBN: (纸本)9798350318944

We give an (O) over tilde(root n)-space single-pass 0.483-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on n vertices. This improves over an O(log n)-space 4/9 < 0.45 approximation algorithm due to Chou, Golovnev, and Velusamy (FOCS 2020), which was known to be optimal for o(root n)-space algorithms. Max-DICUT is a special case of a constraint satisfaction problem (CSP). In this broader context, we give the first CSP for which algorithms with <($)over tilde>(root n) space can provably outperform o(root n)-space algorithms. The key technical contribution of our work is development of the notions of a first-order snapshot of a (directed) graph and of estimates of such snapshots. These snapshots can be used to simulate certain (non-streaming) Max- DICUT algorithms, including the "oblivious" algorithms introduced by Feige and Jozeph (Algorithmica, 2015), who showed that one such algorithm achieves a 0.483-approximation. Previous work of the authors (SODA 2023) studied the restricted case of bounded-degree graphs, and observed that in this setting, it is straightforward to estimate the snapshot with l(1) errors and this suffices to simulate oblivious algorithms. But for unbounded-degree graphs, even defining an achievable and sufficient notion of estimation is subtle. We describe a new notion of snapshot estimation and prove its sufficiency using careful smoothing techniques, and then develop an algorithm which sketches such an estimate via a delicate process of intertwined vertex- and edge-subsampling. Prior to our work, the only streaming algorithms for any CSP on general instances were based on generalizations of the O(log n)-space algorithm for Max-DICUT, and can roughly be characterized as based on "zeroth" order snapshots. Our work thus opens the possibility of a new class of algorithms for approximating CSPs by demonstrating that more sophisticated snapshots can outperform cruder ones in the case of

关键词： constraint satisfaction problem approximation algorithms sublinear algorithms streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Augmented Index and Quantum streaming algorithms for DYCK(2) 32

Augmented Index and Quantum Streaming Algorithms for DYCK(2)

引用

32nd Computational Complexity Conference (CCC)

作者： Nayak, Ashwin Touchette, Dave Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada Univ Waterloo Inst Quantum Comp Waterloo ON Canada Perimeter Inst Theoret Phys Waterloo ON Canada

ISBN: (纸本)9783959770408

We show how two recently developed quantum information theoretic tools can be applied to obtain lower bounds on quantum information complexity. We also develop new tools with potential for broader applicability, and use them to establish a lower bound on the quantum information complexity for the Augmented Index function on an easy distribution. This approach allows us to handle superpositions rather than distributions over inputs, the main technical challenge faced previously. By providing a quantum generalization of the argument of Jain and Nayak [IEEE TIT'14], we leverage this to obtain a lower bound on the space complexity of multi-pass, unidirectional quantum streaming algorithms for the DYCK(2) language.

关键词： streaming algorithms Space complexity Quantum communication complexity Quantum information cost DYcK(2) Augmented Index

来源：评论

学校读者我要写书评

暂无评论

Turnstile streaming algorithms Might as Well Be Linear Sketches 14

Turnstile Streaming Algorithms Might as Well Be Linear Sketc...

引用

46th Annual ACM Symposium on Theory of Computing (STOC)

作者： Li, Yi Nguyen, Huy L. Woodruff, David P. Max Planck Inst Informat Saarbrucken Germany Princeton Univ Princeton NJ 08544 USA IBM Res Almaden San Jose CA USA

ISBN: (纸本)9781450327107

In the turnstile model of data streams, an underlying vector x E {m, m +1,..., m 1, m} is presented as a long sequence of positive and negative integer updates to its coordinates. A randomized algorithm seeks to approximate a function f (x) with constant probability while only making a single pass over this sequence of updates and using a small amount of space. All known algorithms in this model are linear sketches: they sample a matrix A from a distribution on integer matrices in the preprocessing phase, and maintain the linear sketch A " x while processing the stream. At the end of the stream, they output an arbitrary function of A " x. One cannot help but ask: are linear sketches universal? In this work we answer this question by showing that any 1 pass constant probability streaming algorithm for approximating an arbitrary function f of x in the turnstile model can also be implemented by sampling a matrix A from the uniform distribution on 0 (n log m) integer matrices, with entries of magnitude poly (n), and maintaining the linear sketch Ax. Furthermore, the logarithm of the number of possible states of Ax, as x ranges over {m 1,, m}n, plus the amount of randomness needed to store A, is at most a logarithmic factor larger than the space required of the space-optimal algorithm. Our result shows that to prove space lower bounds for 1-pass streaming algorithms, it suffices to prove lower bounds in the simultaneous model of communication complexity, rather than the stronger 1-way model. Moreover, the fact that we can assume we have a linear sketch with polynomially-bounded entries further simplifies existing lower bounds, e.g., for frequency moments we present a simpler proof of the Q(711-2/k) bit complexity lower bound without using communication complexity.

关键词： streaming algorithms linear sketches lower bounds communication complexity

来源：评论

学校读者我要写书评

暂无评论

Experimental Analysis of streaming algorithms for Graph Partitioning 19

Experimental Analysis of Streaming Algorithms for Graph Part...

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Pacaci, Anil Ozsu, M. Tamer Univ Waterloo Waterloo ON Canada

ISBN: (纸本)9781450356435

We report a systematic performance study of streaming graph partitioning algorithms. Graph partitioning plays a crucial role in overall system performance as it has a significant impact on both load balancing and inter-machine communication. The streaming model for graph partitioning has recently gained attention due to its ability to scale to very large graphs with limited resources. The main objective of this study is to understand how the choice of graph partitioning algorithm affects system performance, resource usage and scalability. We focus on both offline graph analytics and online graph query workloads. The study considers both edge-cut and vertex-cut approaches. Our results show that the no partitioning algorithms performs best in all cases, and the choice of graph partitioning algorithm depends on: (i) type and degree distribution of the graph, (ii) characteristics of the workloads, and (iii) specific application requirements.

关键词： Graph Partitioning streaming algorithms Graph Processing

来源：评论

学校读者我要写书评

暂无评论

Real-Time Data streaming algorithms and Processing Technologies: A Survey

Real-Time Data Streaming Algorithms and Processing Technolog...

引用

International Conference on Computational Intelligence and Knowledge Economy (ICCIKE)

作者： Navaz, Alramzana Nujum Harous, Saad Serhani, Mohamed Adel Taleb, Ikbal UAE Univ Coll Informat Technol Al Ain U Arab Emirates Concordia Univ CIISE Montreal PQ Canada

ISBN: (纸本)9781728137780

With the ever-increasing generation of data, there exists a plethora of real-time streaming algorithms proposed in the literature. Enterprises are moving from massive data to quick data;therefore, they will need to use and maybe extend the latest innovative technologies for real-time stream processing. To serve this purpose the paper surveys and classifies the existing streaming data algorithms and techniques. It presents a categorization of existing recent data streaming algorithms that solve the well-known concept drift research problem. In addition, it lists the various datasets used for the purpose of validation. Finally, it highlights the remaining open research inquiries in this field.

关键词： Data streaming Concept Drift Real-Time Data streaming algorithms Stream Processing Technologies

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Estimating the Matching Size in Planar Graphs and Beyond

引用

ACM TRANSACTIONS ON algorithms 2018年第4期14卷 48-48页

作者： Esfandiari, Hossein Hajiaghayi, Mohammadtaghi Liaghat, Vahid Monemizadeh, Morteza Onak, Krzysztof Harvard Univ Sch Engn & Appl Sci Comp Sci Cambridge MA 02138 USA Univ Maryland Dept Comp Sci College Pk MD 20742 USA Stanford Univ Inst Computat & Math Engn Stanford CA 94305 USA Amazon 2100 Univ Ave East Palo Alto CA 94303 USA IBM TJ Watson Res Ctr POB 218 Yorktown Hts NY 10598 USA Harvard Univ Dept Comp Sci 33 Oxford St Cambridge MA 02138 USA Facebook Inc 1 Hacker Way Menlo Pk CA 94025 USA Charles Univ Prague Fac Math & Phys Comp Sci Inst Malostranske Nam 25 CR-18000 Prague 1 Czech Republic

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. When the input graph is planar, we present a simple and elegant streaming algorithm that, with high probability, estimates the size of a maximum matching within a constant factor using (O) over tilde (n(2/3)) space, where n is the number of vertices. The approach generalizes to the family of graphs that have bounded arboricity, which include graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model) in o(n) space. We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We further reduce the required memory size to (O) over tilde(root n) for three restricted settings: (i) when the input graph is a forest;(ii) when we have 2-passes and the input graph has bounded arboricity;and (iii) when the edges arrive in random order and the input graph has bounded arboricity. Finally, we design a reduction from the Boolean Hidden Matching Problem to show that there is no randomized streaming algorithm that estimates the size of the maximum matching to within a factor better than 3/2 and uses only o(n(1/2)) bits of space. Using the same reduction, we show that there is no deterministic algorithm that computes this kind of estimate in o(n) bits of space. The lower bounds hold even for graphs that are collections of paths of constant length.

关键词： streaming algorithms maximal matching planar graphs bounded arboricity estimating matching size

来源：评论

学校读者我要写书评

暂无评论

Scalable Data Analysis on the Fly Using streaming algorithms

Scalable Data Analysis on the Fly Using Streaming Algorithms

引用

作者： Barnas, Daniel Conrad San Diego State University

学位级别：M.S., Master of Science/Master of Surgery

streaming algorithms are a special class of algorithms that compute functions of an input stream using memory that is much smaller than the size of the input. Given an input stream consisting of a sequence of m elements {a1, a2, . . . , am} drawn from a universe of n elements, streaming algorithms attempt to compute functions summarizing the stream (such as quantiles, number of distinct elements, frequent elements, etc.) using sublinear space in terms of m and n. For example, the input could be a stream of network requests from IP addresses and one may wish to identify frequent addresses, without storing the entire stream, to identify spam or network attacks. In addition to low memory usage, many data stream algorithms are able to update the answers quickly as new data arrives. In other words, they are able to maintain statistics for a data stream on the fly as new data is processed, without needing to reprocess the whole stream or store it in memory. There is plenty of literature available about the theory behind many of these algorithms. However, experimental studies of these algorithms are somewhat limited. The purpose of this thesis is to experiment with these algorithms on real-world data streams and data sets. In particular, we will focus on the Misra-Gries algorithm for finding heavy-hitters, as well as a couple of algorithms that estimate the number of distinct elements in a stream. Our goal is threefold: • By applying such space-efficient algorithms to real-world data sets, we hope to be able to glean new features of the data that would otherwise be inaccessible using traditional algorithms due to the size of the streams involved. • We would also like to evaluate the effectiveness of these algorithms, such as memory footprint, update time, and estimation accuracy, on real-world data compared to brute-force approaches. • Moreover, we propose and develop a useful data visualization tool based on the output of the Misra-Gries algorithm as well as implement a P

关键词： Data analysis streaming algorithms Network attacks Distinct elements Frequent elements

来源：评论

学校读者我要写书评

暂无评论

New streaming algorithms for Parameterized Maximal Matching & Beyond 15

New Streaming Algorithms for Parameterized Maximal Matching ...

引用

Proceedings of the 27th ACM symposium on Parallelism in algorithms and Architectures

作者： Rajesh Chitnis Graham Cormode Hossein Esfandiari MohammadTaghi Hajiaghayi Morteza Monemizadeh Weizmann Institute of Science Rehovot Israel University of Warwick Coventry England UK University of Maryland College Park USA Charles University Prague Czech Rep

ISBN: (纸本)9781450335881

Very recently at SODA'15 [2], we studied maximal matching via the framework of parameterized streaming, where we sought solutions under the promise that no maximal matching exceeds k in size. In this paper, we revisit this problem and provide a much simpler algorithm for this problem. We are also able to apply the same technique to the Point Line Cover problem [3].

关键词： maximal matching dynamic streams point line cover streaming algorithms promise

来源：评论

学校读者我要写书评

暂无评论

Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance 13

Space efficient streaming algorithms for the distance to mon...

引用

Symposium on Discrete algorithms

作者： Michael Saks C. Seshadhrit Dept. of Mathematics Rutgers University Sandia National Labs

ISBN: (纸本)9781627484855

Approximating the length of the longest increasing sequence (LIS) of an array is a well-studied problem. We study this problem in the data stream model, where the algorithm is allowed to make a single left-to-right pass through the array and the key resource to be minimized is the amount of additional memory used. We present an algorithm which, for any δ > 0, given streaming access to an array of length n provides a (1 + δ)-multiplicative approximation to the distance to monotonicity (n minus the length of the LIS), and uses only O((log~2 n)/δ) space. The previous best known approximation using polylogarithmic space was a multiplicative 2-factor. The improved approximation factor reflects a qualitative difference between our algorithm and previous algorithms: previous polylogarithmic space algorithms could not reliably detect increasing subsequences of length as large as n/2, while ours can detect increasing subsequences of length βn for any β > 0. More precisely, our algorithm can be used to estimate the length of the LIS to within an additive δn for any δ > 0 while previous algorithms could only achieve additive error n(1/2 - o(1)). Our algorithm is very simple, being just 3 lines of pseudocode, and has a small update time. It is essentially a polylogarithmic space approximate implementation of a classic dynamic program that computes the LIS. We also show how our technique can be applied to other problems solvable by dynamic programs. For example, we give a streaming algorithm for approximating LCS(x, y), the length of the longest common subsequence between strings χ and y, each of length n. Our algorithm works in the asymmetric setting (inspired by [AKO10]), in which we have random access to y and streaming access to x, and runs in small space provided that no single symbol appears very often in y. More precisely, it gives an additive-δn approximation to LCS(x,y) (and hence also to E(x,y) = n - LCS(x,y), the edit distance between χ and y when insertions and delet

关键词： streaming algorithms monotonicity asymmetric edit distance monotonicity Information Sciences algorithms streaming SPACE Space DISTANCE arrays refresh time expanded pseudo code yttrium approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：