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

作者： 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

来源：评论

学校读者我要写书评

暂无评论

A Framework for Adversarially Robust streaming algorithms

引用

JOURNAL OF THE ACM 2022年第2期69卷 1-33页

作者： Ben-Eliezer, Omri Jayaram, Rajesh Woodruff, David P. Yogev, Eylon MIT 77 Massachusetts Ave Cambridge MA 02139 USA Google Res New York NY USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Bar Ilan Univ Ramat Gan Israel Tel Aviv Univ Tel Aviv Israel Harvard Univ Cambridge MA 02138 USA

We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms;on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertiononly model, including distinct elements and more generally F-p-estimation, F-p-heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1 + epsilon)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(log n.1/epsilon) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a non-robust streaming algorithm into a robust one in various scenarios.

关键词： streaming algorithms adversarial model distinct elements robust streaming adaptive inputs

来源：评论

学校读者我要写书评

暂无评论

Quantum Online streaming algorithms with Logarithmic Memory

引用

INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS 2021年第2期60卷 608-616页

作者： Khadiev, Kamil Khadieva, Aliya Smart Quantum Technol Ltd Kazan Russia Kazan Fed Univ Kazan Russia Univ Latvia Fac Comp Riga Latvia

We consider quantum and classical (deterministic or randomize) streaming online algorithms with respect to competitive ratio. We show that there is a problem that can be solved by a quantum online streaming algorithm better than by classical ones in the case of logarithmic memory. The problem is an online version of the Disjointness problem (Checking weather two sets are disjoint or not).

关键词： Quantum computation Online algorithms Logarithmic space streaming algorithms Online minimization problems OBDD Computational complexity

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Bin Packing and Vector Scheduling 1

引用

17th International Workshop on Approximation and Online algorithms (WAOA)

作者： Cormode, Graham Vesely, Pavel Univ Warwick Dept Comp Sci Coventry W Midlands England

ISBN: (数字)9783030394790

ISBN: (纸本)9783030394790;9783030394783

Problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling, are fundamental tasks in combinatorial optimization. These are well understood in the traditional online and offline cases, but have been less well-studied when the volume of the input is truly massive, and cannot even be read into memory. This is captured by the streaming model of computation, where the aim is to approximate the cost of the solution in one pass over the data, using small space. As a result, streaming algorithms produce concise input summaries that approximately preserve the optimum value. We design the first efficient streaming algorithms for these fundamental problems in combinatorial optimization. For BIN PACKING, we provide a streaming asymptotic 1 + epsilon-approximation with (O) over tilde (1/epsilon) memory, where (O) over tilde hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming d + epsilon-approximation for VECTOR BIN PACKING in d dimensions, running in space (O) over tilde (d/epsilon). For the related VECTOR SCHEDULING problem, we show how to construct an input summary in space (O) over tilde (d(2). m/epsilon(2)) that preserves the optimum value up to a factor of 2 - 1/m + epsilon, where m is the number of identical machines.

关键词： streaming algorithms Bin Packing Scheduling

来源：评论

学校读者我要写书评

暂无评论

Exploration with Limited Memory: streaming algorithms for Coin Tossing, Noisy Comparisons, and Multi-armed Bandits 2020

Exploration with Limited Memory: Streaming Algorithms for Co...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Assadi, Sepehr Wang, Chen Rutgers Univ New Brunswick Piscataway NJ 08854 USA

ISBN: (纸本)9781450369794

Consider the following abstract coin tossing problem: Given a set of n coins with unknown biases, find the most biased coin using a minimal number of coin tosses. This is a common abstraction of various exploration problems in theoretical computer science and machine learning and has been studied extensively over the years. In particular, algorithms with optimal sample complexity (number of coin tosses) have been known for this problem for quite some time. Motivated by applications to processing massive datasets, we study the space complexity of solving this problem with optimal number of coin tosses in the streaming model. In this model, the coins are arriving one by one and the algorithm is only allowed to store a limited number of coins at any point - any coin not present in the memory is lost and can no longer be tossed or compared to arriving coins. Prior algorithms for the coin tossing problem with optimal sample complexity are based on iterative elimination of coins which inherently require storing all the coins, leading to memory-inefficient streaming algorithms. We remedy this state-of-affairs by presenting a series of improved streaming algorithms for this problem: we start with a simple algorithm which require storing only O(log n) coins and then iteratively refine it further and further, leading to algorithms with O(log log (n)) memory, O(log*(n)) memory, and finally a one that only stores a single extra coin in memory - the same exact space needed to just store the best coin throughout the stream. Furthermore, we extend our algorithms to the problem of finding the k most biased coins as well as other exploration problems such as finding top-k elements using noisy comparisons or finding an e-best arm in stochastic multi-armed bandits, and obtain efficient streaming algorithms for these problems.

关键词： streaming algorithms Pure Exploration Memory-efficient algorithms Noisy Comparison Multi-Armed Bandits

来源：评论

学校读者我要写书评

暂无评论

A Framework for Adversarially Robust streaming algorithms 20

A Framework for Adversarially Robust Streaming Algorithms

引用

39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Ben-Eliezer, Omri Jayaram, Rajesh Woodruff, David P. Yogev, Eylon Tel Aviv Univ Tel Aviv Israel Carnegie Mellon Univ Pittsburgh PA 15213 USA Boston Univ Boston MA 02215 USA

ISBN: (纸本)9781450371087

We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms;on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertion-only model, including distinct elements and more generally Fp-estimation, Fp-heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1 + e)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(logn, 1/e) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a nonrobust streaming algorithm into a robust one in various scenarios.

关键词： Adversarial robustness streaming algorithms Frequency moments Distinct elements Heavy hitters Databases

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Almost Optimal streaming algorithms for Coverage Problems 17

Almost Optimal Streaming Algorithms for Coverage Problems

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：