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

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

来源：评论

学校读者我要写书评

暂无评论

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)

来源：评论

学校读者我要写书评

暂无评论

Theory meets Practice at the Median: A Worst Case Comparison of Relative Error Quantile algorithms 21

Theory meets Practice at the Median: A Worst Case Comparison...

引用

27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Cormode, Graham Mishra, Abhinav Ross, Joseph Vesely, Pavel Univ Warwick Coventry W Midlands England Splunk San Francisco CA USA Charles Univ Prague Prague Czech Republic

ISBN: (纸本)9781450383325

Estimating the distribution and quantiles of data is a foundational task in data mining and data science. We study algorithms which provide accurate results for extreme quantile queries using a small amount of space, thus helping to understand the tails of the input distribution. Namely, we focus on two recent state-of-the-art solutions: t-digest and ReqSketch. While t-digest is a popular compact summary which works well in a variety of settings, ReqSketch comes with formal accuracy guarantees at the cost of its size growing as new observations are inserted. In this work, we provide insight into which conditions make one preferable to the other. Namely, we show how to construct inputs for t-digest that induce an almost arbitrarily large error and demonstrate that it fails to provide accurate results even on i.i.d. samples from a highly non-uniform distribution. We propose practical improvements to ReqSketch, making it faster than t-digest, while its error stays bounded on any instance. Still, our results confirm that t-digest remains more accurate on the "non-adversarial" data encountered in practice.

关键词： quantiles streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Adversarially Robust Submodular Maximization under Knapsack Constraints 19

Adversarially Robust Submodular Maximization under Knapsack ...

引用

25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)

作者： Avdiukhin, Dmitrii Mitrovic, Slobodan Yaroslavtsev, Grigory Zhou, Samson Indiana Univ Bloomington IN 47405 USA MIT Cambridge MA 02139 USA Alan Turing Inst London England

ISBN: (纸本)9781450362016

We propose the first adversarially robust algorithm for monotone submodular maximization under single and multiple knapsack constraints with scalable implementations in distributed and streaming settings. For a single knapsack constraint, our algorithm outputs a robust summary of almost optimal (up to polylogarithmic factors) size, from which a constant-factor approximation to the optimal solution can be constructed. For multiple knapsack constraints, our approximation is within a constant-factor of the best known non-robust solution. We evaluate the performance of our algorithms by comparison to natural robustifications of existing non-robust algorithms under two objectives: 1) dominating set for large social network graphs from Facebook and Twitter collected by the Stanford Network Analysis Project (SNAP), 2) movie recommendations on a dataset from MovieLens. Experimental results show that our algorithms give the best objective for a majority of the inputs and show strong performance even compared to offline algorithms that are given the set of removals in advance.

关键词： submodular maximization streaming algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Sampling from Dense Streams without Penalty: Improved Bounds for Frequency Moments and Heavy Hitters

引用

20th International Conference on Computing and Combinatorics (COCOON)

作者： Braverman, Vladimir Vorsanger, Gregory Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA

ISBN: (纸本)9783319087832;9783319087825

We investigate the ability to sample relatively small amounts of data from a stream and approximately calculate statistics on the original stream. Mc-Gregor et al. [29] provide worst case theoretical bounds that show space costs for sampling that are inversely correlated with the sampling rate. Indeed, while the lower bound of McGregor et al. cannot be improved in the general case, we show it is possible to improve the space bound for stream D of domain n, when the average positive frequency mu = F-1/F-0 is sufficiently large. We consider the following range of parameters: mu >= log (n) and sample rate p >= C-k mu(-1) log (n), where C-k is a constant. On these streams we improve the bound from (O) over tilde (1/pn(1-2/k)) to (O) over tilde (1/pn(1-2/k)) 0) thus giving polynomial improvement in space for sufficiently large /1 and p(-1).

关键词： streaming algorithms Sampling Frequency Moments Heavy Hitters

来源：评论

学校读者我要写书评

暂无评论

Memory Bounds for the Experts Problem 2022

Memory Bounds for the Experts Problem

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Srinivas, Vaidehi Woodruff, David P. Xu, Ziyu Zhou, Samson Northwestern Univ Evanston IL 60208 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450392648

Online learning with expert advice is a fundamental problem of sequential prediction. In this problem, the algorithm has access to a set of n "experts" who make predictions on each day. The goal on each day is to process these predictions, and make a prediction with the minimum cost. After making a prediction, the algorithm sees the actual outcome on that day, updates its state, and then moves on to the next day. An algorithm is judged by how well it does compared to the best expert in the set. The classical algorithm for this problem is the multiplicative weights algorithm, which has been well-studied in many fields since as early as the 1950s. Variations of this algorithm have been applied to and optimized for a broad range of problems, including boosting an ensemble of weak-learners in machine learning, and approximately solving linear and semi-definite programs. However, every application, to our knowledge, relies on storing weights for every expert, and uses Omega(n) memory. There is little work on understanding the memory required to solve the online learning with expert advice problem (or to run standard sequential prediction algorithms, such as multiplicative weights) in natural streaming models, which is especially important when the number of experts and number of days are both large. We initiate the study of the learning with expert advice problem in the streaming setting, and show lower and upper bounds. Our lower bound for i.i.d., random order, and adversarial order streams uses a reduction to a custom-built problem with a novel masking technique, to show a smooth trade-off for regret versus memory. Our upper bounds show new ways to run standard sequential prediction algorithms in rounds on small "pools" of experts, thus reducing the necessary memory. For random-order streams, we show that our upper bound is tight up to low order terms. We hope that these results and techniques will have broad applications in online learning, and can inspire algorithms

关键词： online learning with experts streaming algorithms sequential prediction algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Rotation Kernel Density Estimation over Data Streams 21

Fast Rotation Kernel Density Estimation over Data Streams

引用

27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Lei, Runze Wang, Pinghui Li, Rundong Jia, Peng Zhao, Junzhou Guan, Xiaohong Deng, Chao Xi An Jiao Tong Univ MOE KLINNS Lab Xian Shaanxi Peoples R China Xi An Jiao Tong Univ Shenzhen Res Inst Xian Shaanxi Peoples R China Tsinghua Univ Dept Automat Beijing Peoples R China Tsinghua Univ NLIST Lab Beijing Peoples R China China Mobile Res Inst Beijing Peoples R China

ISBN: (纸本)9781450383325

Kernel density estimation method is a powerful tool and is widely used in many important real-world applications such as anomaly detection and statistical learning. Unfortunately, current kernel methods suffer from high computational or space costs when dealing with large-scale, high-dimensional datasets, especially when the datasets of interest are given in a stream fashion. Although there are sketch methods designed for kernel density estimation over data streams, they still suffer from high computational costs. To address this problem, in this paper, we propose a novel Rotation Kernel. The Rotation Kernel is based on a Rotation Hash method and is much faster to compute. To achieve memory-efficient kernel density estimation over data streams, we design a method, RKD-Sketch, which compresses high dimensional data streams into a small array of integer counters. We conduct extensive experiments on both synthetic and real-world datasets, and experimental results demonstrate that our RKD-Sketch saves up to 216 times computational resources and up to 104 times space resources than state-of-the-arts. Furthermore, we apply our Rotation Kernel in active learning. Results show that our method achieves up to 256 times speedup and saves up to 13 times space to achieve the same accuracy as the baseline methods.

关键词： Kernel density estimation streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Think Before You Discard: Accurate Triangle Counting in Graph Streams with Deletions

Think Before You Discard: Accurate Triangle Counting in Grap...

引用

European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD)

作者： Shin, Kijung Kim, Jisu Hooi, Bryan Faloutsos, Christos Carnegie Mellon Univ Sch Comp Sci Pittsburgh PA 15213 USA

ISBN: (纸本)9783030109288;9783030109271

Given a stream of edge additions and deletions, how can we estimate the count of triangles in it? If we can store only a subset of the edges, how can we obtain unbiased estimates with small variances? Counting triangles (i.e., cliques of size three) in a graph is a classical problem with applications in a wide range of research areas, including social network analysis, data mining, and databases. Recently, streaming algorithms for triangle counting have been extensively studied since they can naturally be used for large dynamic graphs. However, existing algorithms cannot handle edge deletions or suffer from low accuracy. Can we handle edge deletions while achieving high accuracy? We propose THINKD, which accurately estimates the counts of global triangles (i.e., all triangles) and local triangles associated with each node in a fully dynamic graph stream with edge additions and deletions. Compared to its best competitors, THINKD is (a) Accurate: up to 4.3x more accurate within the same memory budget, (b) Fast: up to 2.2x faster for the same accuracy requirements, and (c) Theoretically sound: always maintaining unbiased estimates with small variances.

关键词： Triangle counting Local triangles streaming algorithms Fully dynamic graph streams Edge deletions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：