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

34th IEEE International Conference on Tools with Artificial Intelligence (ICTAI)

作者： Xie, Yuyang Feng, Xu Zhang, Xizhi Qiu, Jiezhong Yu, Wenjian Tsinghua Univ BNRist Dept Comp Sci & Tech Beijing Peoples R China

ISBN: (纸本)9798350397444

The element-wise functions of a matrix are widely used in machine learning. For the applications with large matrices, efficiently computing the matrix-vector multiplication of matrix element-wise function without explicitly constructed matrix is very desired. In this work, we aim to develop an efficient low-rank approximation of the element-wise function of matrix with the time/memory cost linear to the matrix dimension. We first propose a sparse-sign streaming randomized SVD (ssrSVD) algorithm based on a streaming singular value decomposition (SVD) algorithm and the sparse-sign random projection for the approximation of element-wise function of general asymmetric matrix. For symmetric positive semi-definite (SPSD) matrix, for which the existing Nystrom [1] and FastSPSD [2] method do not perform well if the matrix's singular value decays slowly, we propose a theoretically proved shift skill to improve the approximation accuracy. Combining with the ssrSVD, we obtain the sparse-sign streaming SPSD matrix approximation with shift (S3SPSD) algorithm. Experiments are carried out to evaluate the proposed algorithms' performance in approximating element-wise functions of matrix. With the color transfer task based on the Sinkhorn algorithm, the ssrSVD algorithm largely reduces the approximation error (up to 10(5)x) compared with the state-of-the-art baselines, and results in high-quality color transfer result. For the kernel matrix approximation, the proposed S3SPSD algorithm also consistently outperforms the state-of-the-art baselines. Experimental results finally validate the linear time complexity of the proposed algorithms.

关键词： element-wise function of matrix randomized matrix approximation sparse-sign random projection streaming algorithm shift skill

来源：评论

学校读者我要写书评

暂无评论

streaming INFLUENCE MAXIMIZATION IN SOCIAL NETWORKS BASED ON MULTI-ACTION CREDIT DISTRIBUTION

STREAMING INFLUENCE MAXIMIZATION IN SOCIAL NETWORKS BASED ON...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Yu, Qilian Li, Hang Liao, Yun Cui, Shuguang Univ Calif Davis Dept ECE Davis CA 95616 USA Univ Calif San Diego Dept ECE San Diego CA 92093 USA

ISBN: (纸本)9781538646588

In a social network, influence maximization is the problem of identifying a set of users that own the maximum influence ability across the network. In this paper, a novel credit distribution (CD) based model, termed as the multi-action CD (mCD) model, is introduced to quantify the influence ability of each user. Compared to existing models, the new model can work with practical datasets where one type of action is recorded for multiple times. Based on this model, influence maximization is formulated as a submodular maximization problem under a knapsack constraint, which is NP-hard. An efficient streaming algorithm is developed to achieve (1/3 - epsilon) approximation of the optimality. Experiments conducted on real Twitter dataset demonstrate that the mCD model enjoys high accuracy compared to the conventional CD model in estimating the total number of people who get influenced in a social network. Furthermore, compared to the greedy algorithm, the proposed single-pass streaming algorithm achieves similar performance in terms of influence maximization, while running several orders of magnitude faster.

关键词： Social Networks Influence Maximization Credit Distribution Submodularity streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Maximization of k-Submodular Function Under a Matroid Constraint

引用

Tsinghua Science and Technology 2024年第6期29卷 1633-1641页

作者： Yuezhu Liu Yunjing Sun Min Li School of Mathematics and Statistics Shandong Normal UniversityJinan 250014China

In this paper,we design a deterministic 1/3-approximation algorithm for the problem of maximizing non-monotone k-submodular function under a matroid *** order to reduce the complexity of this algorithm,we also present a randomized 1/3-approximation algorithm with the probability of 1−ε,whereεis the probability of algorithm ***,we design a streaming algorithm for both monotone and non-monotone objective k-submodular functions.

关键词： k-submodular matroid constraint deterministic algorithm randomized algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint

引用

Tsinghua Science and Technology 2024年第1期29卷 46-55页

作者： Zhenning Zhang Kaiqiao Meng Donglei Du Yang Zhou Beijing Institute for Scientific and Engineering Computing Beijing University of TechnologyBeijing 100124China Faculty of Management University of New BrunswickFredericton E3B 5A3Canada School of Mathematics and Statistics Shandong Normal UniversityJinan 250014China

We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness *** sum function is non-submodular in *** an offline model,we introduce two approximation algorithms:A greedy algorithm and a threshold greedy *** a streaming model,we propose a one-pass streaming *** also analyze the approximation ratios of these algorithms,which all depend on the total curvature of the supermodular *** total curvature is computable in polynomial time and widely utilized in the literature.

关键词： submodular function supermodular function fairness constraint greedy algorithm threshold greedy algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Analysis of data streams: Computational and algorithmic challenges

引用

TECHNOMETRICS 2007年第3期49卷 346-356页

作者： Gilbert, A. C. Strauss, M. J. Univ Michigan Dept Math Ann Arbor MI 48109 USA

Over the past 15 years, our ability to collect massive data sets has increased dramatically. Concomitantly, our need to process, compress, store, analyze, and summarize these data sets has grown as well. Scientific, engineering, medical, and industrial applications require that we carry out these tasks efficiently and reasonably accurately. Data streams are one type of modern massive data sets, characterized by their size and by their distributed and dynamic properties. We give an expository discussion of data stream models and the algorithmic challenges that these models pose for computational statistical analysis, then present an overview of three streaming algorithms and a discussion of the computational challenges with each.

关键词： approximation approximation algorithm streaming algorithm sublinear algorithm

来源：评论

学校读者我要写书评

暂无评论

Space limited linear-time graph algorithms on big data

引用

THEORETICAL COMPUTER SCIENCE 2024年 993卷

作者： Chen, Jianer Chu, Zirui Guo, Ying Yang, Wei Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA Guangzhou Univ Sch Comp Sci Guangzhou 510006 Peoples R China

We study algorithms for graph problems in which the graphs are of extremely large size N so that super -linear time w ( N ) or linear space Theta( N ) would become impractical. We use a parameter k to characterize the computational power of a normal computer that can provide additional time and space bounded by polynomials of k in dealing with the large graphs. In particular, we are interested in strict linear -time algorithms using space O ( k O (1) ). In our case studies, as examples, we present (1) a randomized greedy algorithm of time O ( N ) and space O ( k 2 ) for a parameterized version of the M AXIMAL M ATCHING problem;and (2) randomized kernelization algorithms of time O ( N ) and space O ( k O (1) ) for a number of well-known NP -hard problems. Our kernelization algorithms have their kernel sizes match the best kernel sizes by known polynomialtime kernelization algorithms with no space constraints for the problems. We also study the relationship between our proposed model and the streaming model. This study motivates a new streaming kernelization algorithm for the famous V ERTEX C OVER problem that has an optimal update time complexity while matches the best known space complexity of streaming algorithms for the problem.

关键词： Big data Maximal matching Edge dominating set Vertex cover Kernelization algorithm streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast Budgeted Influence Maximization Over Multi-Action Event Logs

引用

IEEE ACCESS 2018年 6卷 14367-14378页

作者： Yu, Qilian Li, Hang Liao, Yun Cui, Shuguang Univ Calif Davis Dept Elect & Comp Engn Davis CA 95616 USA Univ Calif San Diego Dept Elect & Comp Engn San Diego CA 92093 USA

In a social network, influence maximization is the problem of identifying a set of users that own the maximum influence ability across the network. In this paper, a novel credit distribution (CD)-based model, termed as the multiaction CD (mCD) model, is introduced to quantify the influence ability of each user, which works with practical datasets where one type of action could be recorded for multiple times. Based on this model, influence maximization is formulated as a submodular maximization problem under a general knapsack constraint, which is NP hard. An effficient streaming algorithm with one-round scan over the user set is developed to find a suboptimal solution. Specifically, we first solve a special case of knapsack constraints, i.e., a cardinality constraint, and show that the developed streaming algorithm can achieve ((1/2) - epsilon) approximation of the optimality. Furthermore, for the general knapsack case, we show that the modified streaming algorithm can achieve ((1/3) - epsilon) approximation of the optimality. Finally, experiments are conducted over real Twitter dataset and demonstrate that the mCD model enjoys high accuracy compared to the conventional CD model in estimating the total number of people who get influenced in a social network. Moreover, through the comparison to the conventional CD, non-CD models, and the mCD model with the greedy algorithm on the performance of the influence maximization problem, we show the effectiveness and efficiency of the proposed mCD model with the streaming algorithm.

关键词： Online social networks influence maximization credit distribution streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

A revised cache allocation algorithm for VoD multicast service

引用

MULTIMEDIA TOOLS AND APPLICATIONS 2015年第16期74卷 6557-6572页

作者： Lee, Hyun Jong Lee, Wonhyuk Kim, Seunghae Noh, Minki Kim, Jeom Goo Kim, Hyuncheol Kakao Cooperat Seoul South Korea Korea Inst Sci Technol Informat Daejon South Korea Namseoul Univ Dept Comp Sci Cheonan South Korea

The Internet is replacing the traditional telephone network as the ubiquitous network infrastructure. Internet customers are increasing at an exponential rate and will continue to increase in the near future. Among the various Internet services, IPTV VoD (Video on Demand) service is expected to be one of the most popular services. In general, for deploying streamed video service, it is likely to use proxy by locating it nearby end-users. The use of proxy in on-demand media streaming service can help reduce the server streaming load and reduce the startup delay of media playback due to swift retrieval of beginning portion of media. We had proposed a cache allocation scheme for server-proxy media streaming environment by utilizing the advantage of threshold-based multicast mechanism. However it suffer from a little radical change of threshold value. In this paper, enhanced multicast-based server-proxy on-demand media streaming algorithm to IPTV VoD services is presented from the storage, caching size and bandwidth requirement viewpoints.

关键词： streaming algorithm IPTV VoD

来源：评论

学校读者我要写书评

暂无评论

Estimating life-time distribution by observing population continuously

引用

PERFORMANCE EVALUATION 2014年第0期79卷 182-197页

作者： Feng, Hanhua Dube, Parijat Zhang, Li Infinio Syst Inc Cambridge MA 02142 USA IBM TJ Watson Res Ctr Yorktown Hts NY USA

Often in a real world system with a fairly large population, members are not individually traceable for various reasons. As a result, the relationship between a member's behavior and the system's behavior is quite hard to understand. In this paper, we focus on a fundamental problem in such a system: the relationship between its population size and the life-time distribution for its members. We answer two questions: (A) If the life-time distribution is known and the times when members join are observable, how do we best estimate the population size? (B) If the population size can be observed accurately, how do we estimate the unknown life-time distribution for members? In the paper we focus on (B), using the results of (A) as a basis. We model the system as a G/GI/infinity queue with incomplete information, where jobs, once entering the queue, are no longer tracked. With this model, the population size is the number of jobs in the queue and the life times of members are the service times of the jobs. The problem (A) is to estimate the number of jobs in the queue, with known arrival times and a known service-time distribution. We show that, in terms of mean square error, the best deterministic estimator for the (stochastic) number of jobs in the system can be constructed using the survival function of the service-time distribution. The problem (B) is to estimate the unknown service-time distribution in a G/GI/infinity queue where the number of jobs are observable. We demonstrate that the service-time distribution can be inferred indirectly from continuous observations of the number of jobs in the queue, and then propose a few easy-to-implement algorithms. Using only a limited amount of memory, these on-line, streaming algorithms continuously refine their results which, over time, converge to the true service-time distribution. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Lifetime distribution Non-parametric estimation G/GI/infinity streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Non-submodular maximization on massive data streams

引用

JOURNAL OF GLOBAL OPTIMIZATION 2020年第4期76卷 729-743页

作者： Wang, Yijing Xu, Dachuan Wang, Yishui Zhang, Dongmei Beijing Univ Technol Coll Appl Sci Beijing 100124 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China

The problem of maximizing a normalized monotone non-submodular set function subject to a cardinality constraint arises in the context of extracting information from massive streaming data. In this paper, we present four streaming algorithms for this problem by utilizing the concept of diminishing-return ratio. We analyze these algorithms to obtain the corresponding approximation ratios, which generalize the previous results for the submodular case. The numerical experiments show that our algorithms have better solution quality and competitive running time when compared to an existing algorithm.

关键词： streaming algorithm Non-submodular maximization Cardinality constraint Set function

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：