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

Multiple pass streaming algorithms for learning mixtures of distributions in R^d

THEORETICAL COMPUTER SCIENCE 2009年第19期410卷 1765-1780页

作者： Chang, Kevin L. Yahool Inc Yahool Labs Sunnyvale CA 94089 USA

We present a multiple pass streaming algorithm for learning the density function of a mixture of k uniform distributions over rectangles in R-d, for any d > 0. Our learning model is: samples drawn according to the mixture are placed in arbitrary order in a data stream that may only be accessed sequentially by an algorithm with a very limited random access memory space. Our algorithm makes 2l + 2 passes, for any l > 0, and requires memory at most (O) over tilde(epsilon(-2/l) k(2)d(4) + (4k)(d)), where E is the tolerable error of the algorithm. This exhibits a strong memory-pass tradeoff in terms of E: a few more passes significantly lower its memory requirements, thus trading one of the two most important resources in streaming computation for the other. Chang and Karman first considered this problem for of d = 1, 2. Our learning algorithm is especially appropriate for situations where massive data sets of samples are available, but computation with such large inputs requires very restricted models of computation. (C) 2009 Elsevier B.V. All rights reserved.

关键词： streaming algorithm Machine learning Mixture model Computational learning theory

来源：评论

学校读者我要写书评

暂无评论

Maximizing k-submodular functions under budget constraint: applications and streaming algorithms

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第1期44卷 723-751页

作者： Pham, Canh, V Vu, Quang C. Ha, Dung K. T. Nguyen, Tai T. Le, Nguyen D. Phenikaa Univ Fac Comp Sci ORlab Hanoi 12116 Vietnam Peoples Secur Acad Fac Informat Secur Hanoi 10000 Vietnam Vietnam Natl Univ Univ Engn & Technol Fac Informat Technol Hanoi 10000 Vietnam Haiphong Univ Haiphong 180000 Vietnam

Motivated by the practical applications in solving plenty of important combinatorial optimization problems, this paper investigates the Budgeted k-Submodular Maximization problem defined as follows: Given a finite set V, a budget B and a k-submodular function f : (k + 1)(V) (sic) R+, the problem asks to find a solution s = (S-1, S-2,..., S-k) is an element of (k + 1)(V), in which an element e is an element of V has a cost c(i) (e) when added into the i -th set Si, with the total cost of s that does not exceed B so that f (s) is maximized. To address this problem, we propose two single pass streaming algorithms with approximation guarantees: one for the case that an element e has only one cost value when added to all i -th sets and one for the general case with different values of c(i) (e). We further investigate the performance of our algorithms in two applications of the problem, Influence Maximization with k topics and sensor placement of k types of measures. The experiment results indicate that our algorithms can return competitive results but require fewer the number of queries and running time than the state-of-the-art methods.

关键词： k-submodular Budget constraint Approximation algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved streaming algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint

引用

algorithmICA 2021年第3期83卷 879-902页

作者： Huang, Chien-Chung Kakimura, Naonori CNRS Ecole Normale Super Paris France Keio Univ Yokohama Kanagawa Japan

In this paper, we consider the problem of maximizing amonotone submodular function subject to a knapsack constraint in a streaming setting. In such a setting, elements arrive sequentially and at any point in time, and the algorithm can store only a small fraction of the elements that have arrived so far. For the special case that all elements have unit sizes (i.e., the cardinality-constraint case), one can find a (0.5 - epsilon)-approximate solution in O( K epsilon(-1)) space, where K is the knapsack capacity (Badanidiyuru et al. KDD 2014). The approximation ratio is recently shown to be optimal (Feldman et al. STOC 2020). In thiswork, we propose a (0.4 - epsilon)-approximation algorithm for the knapsackconstrained problem, using space that is a polynomial of K and epsilon. This improves on the previous best ratio of 0.363 - epsilon with space of the same order. Our algorithm is based on a careful combination of various ideas to transform multiple-pass streaming algorithms into a single-pass one.

关键词： Submodular functions streaming algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2021年第5期38卷 2140004-2140004页

作者： Zhang, Zhenning Guo, Longkun Wang, Yishui Xu, Dachuan Zhang, Dongmei Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Qilu Univ Technol Shandong Acad Sci Sch Comp Sci & Technol Shandong Key Lab Comp Networks Jinan 250353 Shandong Peoples R China Univ Sci & Technol Beijing Sch Math & Phys Beijing 100083 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

Emerging applications such as optimal budget allocation and sensor placement impose problems of maximizing variants of submodular functions with constraints under a streaming setting. In this paper, we first devise a streaming algorithm based on Sieve-streaming for maximizing a monotone diminishing return submodular (DR-submodular) function with a cardinality constraint on the integer lattice and show it is a one-pass algorithm with approximation ratio 1/2 - epsilon. The key idea to ensure one pass for the algorithm is to combine binary search for determining the level of an element with the exponential-growth method for estimating the OPT. Inspired by Sieve-streaming++, we then improve the memory of the algorithm to O(k/epsilon) and the query complexity to O(k log(2) k/epsilon).

关键词： Diminishing return submodular submodular maximization integer lattice cardinality streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

streaming algorithms for Non-Submodular Functions Maximization with d-Knapsack Constraint on the Integer Lattice

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2023年第5期40卷 2340018-2340018页

作者： Tan, Jingjing Yang, Ruiqi Zhang, Yapu Zhu, Mingyue Weifang Univ Sch Math & Informat Sci Weifang 261061 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China

We study the problem of maximizing a monotone non-submodular function under a d knapsack constraint on the integer lattice. We propose three streaming algorithms to approach this problem. We first design a two-pass min{alpha(1 - epsilon)/2(alpha+1)d, 1 - 1/alpha(w)2(alpha) - epsilon}-approximate algorithm with total memory complexity O(log d beta(-1)/beta epsilon), and total query complexity for each element O(log || B ||(infinity) log d beta(-1)/epsilon). The algorithm relies on a binary search technique to determine the amount of the current elements to be added into the output solution. It also requires to have a good estimate of the optimal value, we use the maximum value of the unit standard vector which can be obtained by reading a round of data to construct a guess set of the optimal value. Then, we modify our algorithm to avoid a repetitive reading of data by dynamically update the maximum value of the unit vector along with the coming elements, and obtain a one-pass streaming algorithm with same approximate ratio. Moreover, we design an improved streamingKnapsack algorithm to reduce the memory complexity to O(d/epsilon(2)).

关键词： streaming algorithm non-submodular function integer lattice knapsack constraint

来源：评论

学校读者我要写书评

暂无评论

Improved streaming algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint 16th

Improved Streaming Algorithms for Maximizing Monotone Submod...

引用

16th International algorithms and Data Structures Symposium (WADS)

作者： Huang, Chien-Chung Kakimura, Naonori Ecole Normale Super CNRS Paris France Keio Univ Yokohama Kanagawa Japan

ISBN: (纸本)9783030247669;9783030247652

In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.4 - epsilon)-approximation algorithm requiring only a single pass through the data. This improves on the currently best (0.363 - epsilon)-approximation algorithm. The required memory space depends only on the size of the knapsack capacity and e.

关键词： Submodular functions streaming algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast streaming algorithms for k-Submodular Maximization under a Knapsack Constraint 9

Fast Streaming Algorithms for k-Submodular Maximization unde...

引用

9th IEEE International Conference on Data Science and Advanced Analytics (DSAA)

作者： Pham, Canh V. Ha, Dung K. T. Hoang, Huan X. Tran, Tan D. Phenikaa Univ ORLab Fac Comp Sci Hanoi Vietnam VNU Univ Engn & Technol Fac Informat Technol Hanoi Vietnam Halong Univ Fac Informat Technol Quang Ninh Vietnam Peoples Secur Acad Hanoi Vietnam

ISBN: (纸本)9781665473309

This paper proposes two fast streaming algorithms for the problem of k-submodular maximization over the ground set of n elements under the knapsack constraint which is important and popular in combinatorial optimization and machine learning. Our algorithms are the first ones that provide constantapproximation ratios within O(nk) query complexity. The first algorithm is a single-pass streaming algorithm that returns a 1/10-approximation solution, the second one is a multi-pass streaming algorithm and improves the approximation ratio to nearly 1/4. Although these ratios are simply near to the stateof-the-art algorithms yet the number of queries can diminish by a large factor. We further investigate the performance of our algorithms by directing several experiments on instances of the issue: Influence Maximization and Sensor Placement. The outcomes confirm that our algorithms not only methodology in the quality arrangement of the cutting edge techniques including streaming and non-streaming algorithms yet in addition significantly reduce the number of queries.

关键词： Approximation algorithm k-submodular maximization knapsack constraint streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Quantum Versus Classical Online streaming algorithms with Logarithmic Size of Memory

引用

LOBACHEVSKII JOURNAL OF MATHEMATICS 2023年第2期44卷 687-698页

作者： Khadiev, K. Khadieva, A. Kravchenko, D. Mannapov, I. Rivosh, A. Yamilov, R. Smart Quantum Technol Ltd Kazan 420000 Russia Kazan Fed Univ Inst Computat Math & Informat Technol Kazan 420008 Tatarstan Russia Univ Latvia Fac Comp LV-1586 Riga Latvia Univ Latvia Fac Comp Ctr Quantum Comp Sci LV-1586 Riga Latvia OOO Yandeks Tekhnol Moscow 119021 Russia

We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with a non-constant size of memory (streaming algorithms) as a model for online algorithms. We construct problems that can be solved by quantum online streaming algorithms better than by classical ones in the case of the logarithmic or sublogarithmic size of memory.

关键词： quantum computation online algorithm automaton streaming algorithm online minimization problem branching program BDD

来源：评论

学校读者我要写书评

暂无评论

Space Complexity of streaming algorithms on Universal Quantum Computers 16th

Space Complexity of Streaming Algorithms on Universal Quantu...

引用

16th International Conference on Theory and Applications of Models of Computation (TAMC)

作者： Hu, Yanglin Melnyk, Darya Wang, Yuyi Wattenhofer, Roger Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9783030592660;9783030592677

Universal quantum computers are the only general purpose quantum computers known that can be implemented as of today. These computers consist of a classical memory component which controls the quantum memory. In this paper, the space complexity of some data stream problems, such as PartialMOD and Equality, is investigated on universal quantum computers. The quantum algorithms for these problems are believed to outperform their classical counterparts. Universal quantum computers, however, need classical bits for controlling quantum gates in addition to qubits. Our analysis shows that the number of classical bits used in quantum algorithms is equal to or even larger than that of classical bits used in corresponding classical algorithms. These results suggest that there is no advantage of implementing certain data stream problems on universal quantum computers instead of classical computers when space complexity is considered.

关键词： streaming algorithm Universal quantum computer Space complexity Solovay-Kitaev algorithm

来源：评论

学校读者我要写书评

暂无评论

Multiple pass streaming algorithms for learning mixtures of distributions in R^d

Multiple pass streaming algorithms for learning mixtures of ...

引用

18th International Conference on algorithmic Learning Theory

作者： Chang, Kevin L. Yahool Inc Yahool Labs Sunnyvale CA 94089 USA

ISBN: (纸本)9783540752240

关键词： streaming algorithm Machine learning Mixture model Computational learning theory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：