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

39th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT)

作者： Dinur, Itai Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9783030457242;9783030457235

An adversary with S bits of memory obtains a stream of Q elements that are uniformly drawn from the set {1, 2, ... , N}, either with or without replacement. This corresponds to sampling Q elements using either a random function or a random permutation. The adversary's goal is to distinguish between these two cases. This problem was first considered by Jaeger and Tessaro (EUROCRYPT 2019), which proved that the adversary's advantage is upper bounded by root Q . S/N. Jaeger and Tessaro used this bound as a streaming switching lemma which allowed proving that known time-memory tradeoff attacks on several modes of operation (such as counter-mode) are optimal up to a factor of O(log N) if Q . S approximate to N. However, the bound's proof assumed an unproven combinatorial conjecture. Moreover, if Q . S << N there is a gap between the upper bound of root Q . S/N and the Q . S/N advantage obtained by known attacks. In this paper, we prove a tight upper bound (up to poly-logarithmic factors) of O(log Q . Q . S/N) on the adversary's advantage in the streaming distinguishing problem. The proof does not require a conjecture and is based on a hybrid argument that gives rise to a reduction from the unique-disjointness communication complexity problem to streaming.

关键词： streaming algorithm Time-memory tradeoff Communication complexity Provable security Switching lemma Mode of operation

来源：评论

学校读者我要写书评

暂无评论

Fairness in streaming Submodular Maximization Subject to a Knapsack Constraint 24

Fairness in Streaming Submodular Maximization Subject to a K...

引用

30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

作者： Cui, Shuang Han, Kai Tang, Shaojie Li, Feng Luo, Jun Univ Sci & Technol China Sch Comp Sci & Technol Hefei Anhui Peoples R China Soochow Univ Sch Comp Sci & Technol Suzhou Jiangsu Peoples R China Univ Texas Dallas Richardson TX USA Shandong Univ Sch Comp Sci & Technol Jinan Shandong Peoples R China Qilu Univ Technol Qingdao Key Lab Comp Power Network & Informat Secur Minist Educ Jinan Shandong Peoples R China Nanyang Technol Univ Singapore Singapore

ISBN: (纸本)9798400704901

Submodular optimization has been identified as a powerful tool for many data mining applications, where a representative subset of moderate size needs to be extracted from a large-scale dataset. In scenarios where data points possess sensitive attributes such as age, gender, or race, it becomes imperative to integrate fairness measures into submodular optimization to mitigate bias and discrimination. In this paper, we study the fundamental problem of fair submodular maximization subject to a knapsack constraint and propose the first streaming algorithm for it with provable performance guarantees for both monotone and non-monotone submodular functions. As a byproduct, we also propose a streaming algorithm for submodular maximization subject to a partition matroid and a knapsack constraint, significantly improving the performance bounds achieved by previous work. We conduct extensive experiments on real-world applications such as movie recommendation, image summarization, and maximum coverage in social networks. The experimental results strongly demonstrate the superiority of our proposed algorithms in terms of both fairness and utility.

关键词： data stream mining fairness submodular maximization streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating Element-Wise Functions of Matrix with Improved streaming Randomized SVD 34

Approximating Element-Wise Functions of Matrix with Improved...

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：