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

ACM TRANSACTIONS ON algorithms 2014年第4期10卷 22-22页

作者： Breslauer, Dany Galil, Zvi Univ Haifa Caesarea Rothchild Inst Interdisciplinary Applica IL-31999 Haifa Israel Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

This article presents a real-time randomized streaming string-matching algorithm that uses O(log m) space. The algorithm only makes one-sided small probability false-positive errors, possibly reporting phantom occurre... 详细信息

关键词： algorithms Theory String matching streaming algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Semi-streaming Set Cover

引用

ACM TRANSACTIONS ON algorithms 2016年第1期13卷 6-6页

作者： Emek, Yuval Rosen, Adi Technion Israel Inst Technol Fac Ind Engn & Management IL-3200003 Haifa Israel CNRS Paris France Univ Paris Diderot IRIF Case 7014 F-75205 Paris 13 France

This article studies the set cover problem under the semi-streaming model. The underlying set system is formalized in terms of a hypergraph G = (V, E) whose edges arrive one by one, and the goal is to construct an edge cover F subset of E with the objective of minimizing the cardinality (or cost in the weighted case) of F. We further consider a parameterized relaxation of this problem, where, given some 0 <= epsilon < 1, the goal is to construct an edge (1 - epsilon)-cover, namely, a subset of edges incident to all but an epsilon-fraction of the vertices (or their benefit in the weighted case). The key limitation imposed on the algorithm is that its space is limited to (poly) logarithmically many bits per vertex. Our main result is an asymptotically tight tradeoff between epsilon and the approximation ratio: We design a semi-streaming algorithm that on input hypergraph G constructs a succinct data structure D such that for every 0 <= epsilon < 1, an edge (1 - epsilon)-cover that approximates the optimal edge (1-) cover within a factor of f (epsilon, n) can be extracted from D (efficiently and with no additional space requirements), where f (epsilon, n) = {O(1/epsilon), if epsilon > 1/root n O(root n), otherwise. In particular, for the traditional set cover problem, we obtain an O(root n)-approximation. This algorithm is proved to be best possible by establishing a family (parameterized by epsilon) of matching lower bounds.

关键词： streaming algorithms set cover lower bounds

来源：评论

学校读者我要写书评

暂无评论

Introduction to the special issue on foundations of adaptive networked societies of tiny artefacts

引用

COMPUTER SCIENCE REVIEW 2011年第1期5卷 4-6页

作者： Chatzigiannakis, Ioannis Spirakis, Paul RACTI Patras Greece

This special issue of Computer Science Review features seven papers on foundations of adaptive networked societies of tiny artefacts. The introduction describes the motivation for the special issue and briefly overvie... 详细信息

关键词： Wireless sensor networks Mobile networks Distributed computing Security Computation models Self-stabilization Game theory streaming algorithms Data aggregation Algorithm engineering Experimentation Ubiquitous applications

来源：评论

学校读者我要写书评

暂无评论

Space-Optimal Heavy Hitters with Strong Error Bounds

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2010年第4期35卷 1–28页

作者： Berinde, Radu Indyk, Piotr Cormode, Graham Strauss, Martin J. MIT Cambridge MA 02139 USA Univ Michigan Ann Arbor MI 48109 USA

The problem of finding heavy hitters and approximating the frequencies of items is at the heart of many problems in data stream analysis. It has been observed that several proposed solutions to this problem can outperform their worst-case guarantees on real data. This leads to the question of whether some stronger bounds can be guaranteed. We answer this in the positive by showing that a class of counter-based algorithms (including the popular and very space-efficient FREQUENT and SPACESAVING algorithms) provides much stronger approximation guarantees than previously known. Specifically, we show that errors in the approximation of individual elements do not depend on the frequencies of the most frequent elements, but only on the frequency of the remaining tail. This shows that counter-based methods are the most space-efficient (in fact, space-optimal) algorithms having this strong error bound. This tail guarantee allows these algorithms to solve the sparse recovery problem. Here, the goal is to recover a faithful representation of the vector of frequencies, f. We prove that using space O(k), the algorithms construct an approximation f* to the frequency vector f so that the L-1 error parallel to f - f*parallel to(1) is close to the best possible error min f' parallel to f' - f parallel to(1), where f' ranges over all vectors with at most k non-zero entries. This improves the previously best known space bound of about O(k log n) for streams without element deletions (where n is the size of the domain from which stream elements are drawn). Other consequences of the tail guarantees are results for skewed (Zipfian) data, and guarantees for accuracy of merging multiple summarized streams.

关键词： algorithms Theory Frequency estimation heavy hitters streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Relative Error streaming Quantiles

引用

JOURNAL OF THE ACM 2023年第5期70卷 30-30页

作者： Cormode, Graham Karnin, Zohar Liberty, Edo Thaler, Justin Vesely, Pavel Univ Warwick Coventry W Midlands England Amazon New York NY USA Pinecone San Mateo CA USA Georgetown Univ Washington DC 20057 USA Charles Univ Prague Prague Czech Republic

Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of n items from a data universe equipped with a total order, the task is to compute a sketch (data structure) of size polylogarithmic in n. Given the sketch and a query item y, one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal to y. Most works to date focused on additive en error approximation, culminating in the KLL sketch that achieved optimal asymptotic behavior. This article investigates multiplicative (1 +/- epsilon)-error approximations to the rank. Practical motivation for multiplicative error stems from demands to understand the tails of distributions, and hence for sketches to be more accurate near extreme values. The most space-efficient algorithms due to prior work store either O(log(epsilon(2)n)/epsilon 2) or O(log(3) (epsilon n)/epsilon) universe items. We present a randomized sketch storing O(log(1.5) (epsilon n)/epsilon) items that can (1 +/- epsilon)-approximate the rank of each universe item with high constant probability;this space bound is within an O(root log(epsilon n)) factor of optimal. Our algorithm does not require prior knowledge of the stream length and is fully mergeable, rendering it suitable for parallel and distributed computing environments.

关键词： streaming algorithms quantiles

来源：评论

学校读者我要写书评

暂无评论

Time Bounds for streaming Problems

引用

THEORY OF COMPUTING 2019年 15卷

作者： Clifford, Raphael Jalsenius, Markus Sach, Benjamin Univ Bristol Algorithm Design Bristol Avon England Telia Co AB Solna Sweden Alan Turing Inst London England

We give tight cell-probe bounds for the time to compute convolution, multiplication and Hamming distance in a stream. The cell probe model is a particularly strong computational model and subsumes, for example, the popular word RAM model. We first consider online convolution where the task is to compute the inner product between a fixed n-dimensional vector and a vector of the n most recent values from a stream. One symbol of the stream arrives at a time and then each output symbol must be computed before the next input symbol arrives. Next we show bounds for online multiplication of two n-digit numbers where one of the multiplicands is known in advance and the other arrives one digit at a time, starting from the lower-order end. When a digit arrives, the task is to compute a single new digit from the product before the next digit arrives. Finally we look at the online Hamming distance problem where the Hamming distance is computed instead of the inner product. For each of these three problems, we give a lower bound of Omega ((delta/w) log n) time on average per output symbol, where delta is the number of bits needed to represent an input symbol and w is the cell or word size. We argue that these bounds are in fact tight within the cell probe model.

关键词： lower bounds cell probe streaming algorithms online algorithms

来源：评论

学校读者我要写书评

暂无评论

A Space-Efficient streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday Paradox

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2015年第3期9卷 15-15页

作者： Jha, Madhav Seshadhri, C. Pinar, Ali Sandia Natl Labs Livermore CA 94550 USA

We design a space-efficient algorithm that approximates the transitivity (global clustering coefficient) and total triangle count with only a single pass through a graph given as a stream of edges. Our procedure is based on the classic probabilistic result, the birthday paradox. When the transitivity is constant and there are more edges than wedges (common properties for social networks), we can prove that our algorithm requires O(root n) space (n is the number of vertices) to provide accurate estimates. We run a detailed set of experiments on a variety of real graphs and demonstrate that the memory requirement of the algorithm is a tiny fraction of the graph. For example, even for a graph with 200 million edges, our algorithm stores just 40,000 edges to give accurate results. Being a single pass streaming algorithm, our procedure also maintains a real-time estimate of the transitivity/number of triangles of a graph by storing a minuscule fraction of edges.

关键词： algorithms Theory Triangle counting streaming graphs clustering coefficient transitivity birthday paradox streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

NEAR-OPTIMAL APPROXIMATE SHORTEST PATHS AND TRANSSHIPMENT IN DISTRIBUTED AND streaming MODELS

引用

SIAM JOURNAL ON COMPUTING 2021年第3期50卷 815-856页

作者： Becker, Ruben Forster, Sebastian Karrenbauer, Andreas Lenzen, Christoph Gran Sasso Sci Inst Laquila Italy Univ Salzburg Dept Comp Sci Salzburg Austria Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany

We present a method for solving the transshipment problem-also known as uncapacitated minimum cost flow-up to a multiplicative error of 1+ epsilon in undirected graphs with nonnegative edge weights using a tailored gradient descent algorithm. Using \widetilde (O) over tilde (.) to hide polylogarithmic factors in n (the number of nodes in the graph), our gradient descent algorithm takes \widetilde (O) over tilde(epsilon(-2)) iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of polylog n. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a randomized rounding scheme, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve upon prior works by obtaining the following results: (1) Broadcast CONGEST model: (1 + epsilon)-approximate SSSP using (O) over tilde((root n + D)epsilon(-3)) rounds, where D is the (hop) diameter of the network. (2) Broadcast Congested Clique model: (1 + epsilon)-approximate transshipment and SSSP using \widetilde (O) over tilde(epsilon(-2)) rounds. (3) Multipass streaming model: (1 + epsilon)-approximate transshipment and SSSP using \widetilde (O) over tilde (n) space and \widetilde (O) over tilde(epsilon(-2)) passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction;computing a spanner is sufficient with our method. The above bounds assume nonnegative edge weights that are polynomially bounded in n;for general nonnegative weights, there is an additional multiplicative overhead equal to the logarithm of the maximum ratio between nonzero weights. Our algorithms can also handle asymmetric costs for traversing edges in opposite directions. In this case, we obtain an additional multiplicative dependence of the maximum ratio between the two costs on so

关键词： shortest paths gradient descent distributed algorithms streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal streaming and Tracking Distinct Elements with High Probability

引用

ACM TRANSACTIONS ON algorithms 2020年第1期16卷 3-3页

作者： Blasiok, Jaroslaw Harvard Univ John A Paulson Sch Engn & Appl Sci 33 Oxford St Cambridge MA 02138 USA

The distinct elements problem is one of the fundamental problems in streaming algorithms-given a stream of integers in the range {1, ... , n), we wish to provide a (1 + epsilon) approximation to the number of distinct elements in the input. After a long line of research an optimal solution for this problem with constant probability of success, using O(1/epsilon(2) + lg n) bits of space, was given by Kane, Nelson, and Woodruff in 2010. The standard approach used to achieve low failure probability delta is to take the median of lg delta(-1) parallel repetitions of the original algorithm. We show that such a multiplicative space blow-up is unnecessary: We provide an optimal algorithm using O(lg delta(-1)/epsilon(2) + lg n) bits of space-matching known lower bounds for this problem. That is, the lg delta(-1) factor does not multiply the lg( )n term. This settles completely the space complexity of the distinct elements problem with respect to all standard parameters. We consider also the strong tracking (or continuous monitoring) variant of the distinct elements problem, where we want an algorithm that provides an approximation of the number of distinct elements seen so far, at all times of the stream. We show that this variant can be solved using O(lg lg n +lg delta(-1)/epsilon(2)+ lg n) bits of space, which we show to be optimal.

关键词： Distinct elements streaming algorithms continuous monitoring

来源：评论

学校读者我要写书评

暂无评论

Minwise-Independent Permutations with Insertion and Deletion of Features 16th

Minwise-Independent Permutations with Insertion and Deletion...

引用

16th International Conference on Similarity Search and Applications

作者： Pratap, Rameshwar Kulkarni, Raghav IIT Hyderabad Hyderabad Telangana India Chennai Math Inst Chennai Tamil Nadu India

ISBN: (纸本)9783031469930;9783031469947

The seminal work of Broder et al. [5] introduces the minHash algorithm that computes a low-dimensional sketch of high-dimensional binary data that closely approximates pairwise Jaccard similarity. Since its invention, minHash has been commonly used by practitioners in various big data applications. In many real-life scenarios, the data is dynamic and their feature sets evolve over time. We consider the case when features are dynamically inserted and deleted in the dataset. A naive solution to this problem is to repeatedly recompute minHash with respect to the updated dimension. However, this is an expensive task as it requires generating fresh random permutations. To the best of our knowledge, no systematic study of minHash is recorded in the context of dynamic insertion and deletion of features. In this work, we initiate this study and suggest algorithms that make the minHash sketches adaptable to the dynamic insertion and deletion of features. We show a rigorous theoretical analysis of our algorithms and complement it with supporting experiments on several real-world datasets. Empirically we observe a significant speed-up in the running time while simultaneously offering comparable performance with respect to running minHash from scratch. Our proposal is efficient, accurate, and easy to implement in practice.

关键词： Sketching algorithms Jaccard similarity estimation streaming algorithms Locality sensitive hashing (LSH)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：