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

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Assadi, Sepehr Behnezhad, Soheil Khanna, Sanjeev Li, Huan Rutgers State Univ New Brunswick NJ 08903 USA Northeastern Univ Boston MA USA Univ Penn Philadelphia PA USA

ISBN: (纸本)9781450399135

We present a new approach for finding matchings in dense graphs by building on Szemeredi's celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs: (i) A deterministic single-pass streaming algorithm that finds a (1 - o(1))-approximate matching in o(n2) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm. (ii) A randomized fully dynamic algorithm that with high probability maintains a (1 - o(1))-approximate matching in o(n) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the first o(n) update-time dynamic algorithm with approximation guarantee arbitrarily close to one. Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log* n)T(1) factor. Nevertheless, in each case, they show that the "right" answer to the problem is not what is dictated by the previous bounds. Finally, in the streaming model, we also present a randomized (1o(1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemeredi (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.

关键词： Maximum Matching streaming algorithms Dynamic algorithms Regularity Lemma

来源：评论

学校读者我要写书评

暂无评论

A Quantum Advantage for a Natural streaming Problem 62

A Quantum Advantage for a Natural Streaming Problem

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Kallaugher, John Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

ISBN: (纸本)9781665420556

Data streaming, in which a large dataset is received as a "stream" of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA '06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best-studied problems in classical graph streaming-the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting;our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.

关键词： streaming algorithms graph algorithms quantum computation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Catching the head, tail, and everything in between: a streaming algorithm for the degree distribution 15

Catching the head, tail, and everything in between: a stream...

引用

IEEE International Conference on Data Mining (ICDM)

作者： Simpson, Olivia Seshadhri, C. McGregor, Andrew Univ Calif San Diego San Diego CA 92103 USA Univ Calif Santa Cruz Santa Cruz CA 95064 USA Univ Massachusetts Amherst MA 01003 USA

ISBN: (纸本)9781467395038

The degree distribution is one of the most fundamental graph properties of interest for real-world graphs. It has been widely observed in numerous domains that graphs typically have a tailed or scale-free degree distribution. While the average degree is usually quite small, the variance is quite high and there are vertices with degrees at all scales. We focus on the problem of approximating the degree distribution of a large streaming graph, with small storage. We design an algorithm headtail, whose main novelty is a new estimator of infrequent degrees using truncated geometric random variables. We give a mathematical analysis of headtail and show that it has excellent behavior in practice. We can process streams will millions of edges with storage less than 1% and get extremely accurate approximations for all scales in the degree distribution. We also introduce a new notion of Relative Hausdorff distance between tailed histograms. Existing notions of distances between distributions are not suitable, since they ignore infrequent degrees in the tail. The Relative Hausdorff distance measures deviations at all scales, and is a more suitable distance for comparing degree distributions. By tracking this new measure, we are able to give strong empirical evidence of the convergence of headtail.

关键词： Degree distribution Graph sampling Small-space algorithms streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

A Multi-pass streaming Algorithm for Regularized Submodular Maximization 15th

A Multi-pass Streaming Algorithm for Regularized Submodular ...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Gong, Qinqin Gao, Suixiang Wang, Fengmin Yang, Ruiqi Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China Beijing Jinghang Res Inst Comp & Commun Beijing 100074 Peoples R China

ISBN: (纸本)9783030926816;9783030926809

In this paper, we consider a problem of maximizing regularized submodular functions with a k-cardinality constraint under streaming fashion. In the model, the utility function f(.) = g(.)-l(.) is expressed as the difference between a non-negative monotone non-decreasing submodular function g and a non-negative modular function l. In addition, the elements are revealed in a streaming setting, that is to say, an element is visited in one time slot. The problem asks to find a subset of size at most k such that the regularized utility value is maximized. Most of the existing algorithms for the submodular maximization heavily rely on the non-negativity assumption of the utility function, which may not be applicable for our regularized scenario. Indeed, determining if the maximum is positive or not is NP-hard, which implies that no multiplicative factor approximation is existed for this problem. To circumvent this challenge, several works paid attention to more meaningful guarantees by introducing a slightly weaker notion of approximation, and any developed algorithm is aim to construct a solution S satisfying f(S) >= rho . g(OPT) - l(OPT) for some rho > 0. In this work, assume there is a weak.-approximation for the k-cardinality constrained regularized submodular maximization, we develop Distorted-Threshold-streaming, a multi-pass bicriteria algorithm for the streaming regularized submodular maximization with the k-cardinality constraint (SRSMCC), which produces a (rho/lambda, 1/lambda)-bicriteria approximation bymaking over O(log(lambda/rho)/epsilon) passes, consuming O(k) memory and using O(log(lambda/rho)/epsilon) queries per element, where lambda = 2-(2 rho+2)/(3+root 5-4 rho)/(3+root 5-4 rho)/(2 rho+2)-1 and any accuracy parameter epsilon > 0.

关键词： Submodular maximization Stream model streaming algorithms Threshold-based Multi-pass

来源：评论

学校读者我要写书评

暂无评论

A Memory-Efficient Sketch Method for Estimating High Similarities in streaming Sets 19

A Memory-Efficient Sketch Method for Estimating High Similar...

引用

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

作者： Wang, Pinghui Qi, Yiyan Zhang, Yuanming Zhai, Qiaozhu Wang, Chenxu Lui, John C. S. Guan, Xiaohong Xi An Jiao Tong Univ NSKEYLAB Xian Shaanxi Peoples R China Xi An Jiao Tong Univ Shenzhen Res Inst Shenzhen Peoples R China Chinese Univ Hong Kong Hong Kong Peoples R China Tsinghua Univ Dept Automat Beijing Peoples R China Tsinghua Univ NLIST Lab Beijing Peoples R China

ISBN: (纸本)9781450362016

Estimating set similarity and detecting highly similar sets are fundamental problems in areas such as databases, machine learning, and information retrieval. MinHash is a well-known technique for approximating Jaccard similarity of sets and has been successfully used for many applications such as similarity search and large scale learning. Its two compressed versions, b-bit MinHash and Odd Sketch, can significantly reduce the memory usage of the original MinHash method, especially for estimating high similarities (i.e., similarities around 1). Although MinHash can be applied to static sets as well as streaming sets, of which elements are given in a streaming fashion and cardinality is unknown or even infinite, unfortunately, b-bit MinHash and Odd Sketch fail to deal with streaming data. To solve this problem, we design a memory efficient sketch method, MaxLogHash, to accurately estimate Jaccard similarities in streaming sets. Compared to MinHash, our method uses smaller sized registers (each register consists of less than 7 bits) to build a compact sketch for each set. We also provide a simple yet accurate estimator for inferring Jaccard similarity from MaxLogHash sketches. In addition, we derive formulas for bounding the estimation error and determine the smallest necessary memory usage (i.e., the number of registers used for a MaxLogHash sketch) for the desired accuracy. We conduct experiments on a variety of datasets, and experimental results show that our method MaxLogHash is about 5 times more memory efficient than MinHash with the same accuracy and computational cost for estimating high similarities.

关键词： streaming algorithms Sketch Jaccard coefficient similarity

来源：评论

学校读者我要写书评

暂无评论

Discovery of Cloud Incidents through streaming Consolidation of Events across Timeline and Topology Hierarchy

Discovery of Cloud Incidents through Streaming Consolidation...

引用

IEEE/IFIP Network Operations and Management Symposium (NOMS)

作者： Harutyunyan, Ashot Poghosyan, Arnak Bunarjyan, Tigran Grigoryan, Naira Grigoryan, Artur Tadevosyan, Vahan Baloian, Nelson Yerevan State Univ Yerevan Armenia NAS RA Inst Informat & Automat Problems Yerevan Armenia NAS RA Inst Math Yerevan Armenia Tech Univ Munich Munich Germany VMware Yerevan Armenia Univ Chile Dept Comp Sci Santiago Chile

ISBN: (纸本)9798350327939;9798350327946

With the growing complexity and dynamism of cloud environments, users of operations management solutions are facing a critical headache of "event storms". Understanding and prioritizing reactions to such high volumes of noisy recommendation content for various tasks is beyond the capacities of human operators. This significantly degrades the resolution metrics of performance issues and optimization of infrastructures and applications. We have devised a novel streaming clustering algorithm for processing alerts and discovering Alert Episodes with their evolution tracked in time and space. It is based on the principles of the classical density-based clustering DBSCAN. We learn Unknown Problems applying this algorithm to low-level events within the VMware Aria Operations manager. Those episodes might typically be out of alert definitions coverage and explain new types of emerging incidents. Our solutions with different hyperparameters are prototyped and integrated into the production. We share experimental insights from an internal environment with interesting alert episodes learned and unknown problems of alarms/symptoms discovered with a self-explainable story on where the source of the performance issue stays and how it evolved into a larger problem situation affecting several objects and hierarchy layers. The constructs we introduce help reduce user efforts in making sense of events' waves and perform troubleshooting with relevance. Our solution can be refactored into an independent event management service for cloud operations.

关键词： AI Ops event management intelligent troubleshooting cloud incident streaming algorithms density-based clustering root cause analysis

来源：评论

学校读者我要写书评

暂无评论

A New Information Complexity Measure for Multi-pass streaming with Applications 2024

A New Information Complexity Measure for Multi-pass Streamin...

引用

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

作者： Braverman, Mark Garg, Sumegha Li, Qian Wang, Shuo Woodruff, David P. Zhang, Jiapeng Princeton Univ Princeton NJ 08544 USA Rutgers State Univ Piscataway NJ USA Shenzhen Res Inst Big Data Shenzhen lnternat Ctr Ind & Appl Math Shenzhen Peoples R China Shanghai Jiao Tong Univ Shanghai Peoples R China Carnegie Mellon Univ Pittsburgh PA USA Univ Southern Calif Los Angeles CA USA

ISBN: (纸本)9798400703836

We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams: (1) In the coin problem, one sees a stream of = i.i.d. uniformly random bits and one would like to compute the majority with constant advantage. We show that any constant-pass algorithm must use Omega(log n) bits of memory, significantly extending an earlier Omega(log n) bit lower bound for single-pass algorithms of Braverman-Garg-Woodruff (FOCS, 2020). This also gives the first Omega(log n) bit lower bound for the problem of approximating a counter up to a constant factor in worst-case turnstile streams for more than one pass. (2) In the needle problem, one either sees a stream of = i.i.d. uniform samples from a domain [C], or there is a randomly chosen "needle" alpha is an element of[l] for which each item independently is chosen to equal alpha with probability p, and is otherwise uniformly random in [C]. The problem of distinguishing these two cases is central to understanding the space complexity of the frequency moment estimation problem in random order streams. We show tight multi-pass space bounds for this problem for every p < 1/root n log(3) n, resolving an open question of Lovett and Zhang (FOCS, 2023);even for 1-pass our bounds are new. To show optimality, we improve both lower and upper bounds from existing results. Our information complexity framework significantly extends the toolkit for proving multi-pass streaming lower bounds, and we give a wide number of additional streaming applications of our lower bound techniques, including multi-pass lower bounds for l(p)-norm estimation, l(p)-point query and heavy hitters, and compressed sensing problems.

关键词： Information Complexity streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Cloud Computing’s Effect on Video Games streaming 2

Cloud Computing’s Effect on Video Games Streaming

引用

2nd International Conference on Automation, Computing and Renewable Systems, ICACRS 2023

作者： Komathi, A. Lenin, J. Asha, S. Suresh, A. Suguna, M. Srinivasan, C. Department of Computer Science Nadar Saraswathi College of Arts and Science College Tamilnadu Theni India Department of ComputerScience and Engineering Alliance College of Engineering and Design Alliance University Karnataka Bengaluru India Department of Information Technology S.A. Engineering College Tamil Nadu Chennai India Department of Computer Science and Engineering Siddharth Institute of Engineering & Technology Andhra Pradesh Puttur India Tamil Nadu Salem India Department of Computer Science and Engineering Saveetha School of Engineering Saveetha Institute of Medical and Technical Sciences Saveetha University Tamil Nadu Chennai India

ISBN: (纸本)9798350340235

The disruptive power of cloud computing is altering the gaming industry. Real-time gaming is now feasible because to advancements in streaming algorithms, further blurring the lines between the digital and physical worlds. Understanding the potential of Cloud computing to change the gaming industry is the emphasis which investigates the complicated relationship between numerous technologies. By using cutting-edge streaming protocols and techniques like Adaptive Bitrate streaming (ABS), buffering, caching, and compression, users may have uninterrupted, high-quality gaming experiences. The study's findings herald a new era of interactive entertainment and shed light on the transformative possibilities of these technologies. Asynchronous Bit-Rate (ABR) encoding, buffering, caching algorithms, video compression standards, and streaming protocols are just few of the numerous digital components that work together to provide uninterrupted data transmission. The rapid progress of ABR algorithms has made it possible to dynamically alter video quality to maximize the user experience across a broad variety of network scenarios. Buffering and caching algorithms play crucial roles by proactively managing data flow and storage to avoid disruptions in the streaming experience. © 2023 IEEE.

关键词： Autism buffering algorithms caching methods Cloud Computing Impact Interactive Entertainment Standards for video compression streaming algorithms streaming protocols Video Games

来源：评论

学校读者我要写书评

暂无评论

Near Optimal Frequent Directions for Sketching Dense and Sparse Matrices

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2019年第1期20卷 2018-2040页

作者： Huang, Zengfeng Fudan Univ Sch Data Sci Shanghai Peoples R China

Given a large matrix A is an element of R-n x d, we consider the problem of computing a sketch matrix B is an element of R-l x d which is significantly smaller than but still well approximates A. We consider the problems in the streaming model, where the algorithm can only make one pass over the input with limited working space, and we are interested in minimizing the covariance error parallel to A(T) A - B-T B parallel to(2). The popular Frequent Directions algorithm of Liberty (2013) and its variants achieve optimal space-error tradeoffs. However, whether the running time can be improved remains an unanswered question. In this paper, we almost settle the question by proving that the time complexity of this problem is equivalent to that of matrix multiplication up to lower order terms. Specifically, we provide new space-optimal algorithms with faster running times and also show that the running times of our algorithms can be improved if and only if the state-of-the-art running time of matrix multiplication can be improved significantly.

关键词： Matrix Sketching Frequent Directions streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：