Streaming Algorithms for News and Scientific Literature Recommendation: Monotone Submodular Maximization With a d-Knapsack Constraint

doi:10.1109/ACCESS.2018.2871668

	Streaming Algorithms for News and Scientific Literature Recommendation: Monotone Submodular Maximization With a d-Knapsack Constraint
	Yu, Qilian 1; Xu, Li 2; Cui, Shuguang 1
	2018
发表期刊	IEEE ACCESS
ISSN	2169-3536
卷号	6 页码:53736-53747
摘要	Submodular optimization plays a significant role in combinatorial problems, since it captures the structure of the edge cuts in graphs, the coverage of sets, and so on. Many data mining and machine learning problems can be cast as submodular maximization problems with applications in recommendation systems and data diversification. In this paper, we focus on the problem of maximizing a monotone submodular function subject to a d-knapsack constraint, for which we propose a streaming algorithm that achieves a ((1/1 + 2d) - epsilon)-approximation of the optimal value, while it only needs one single pass through the data set without storing all the data in the memory. In our experiments, we extensively evaluate the effectiveness of our proposed algorithm via two applications: news recommendation and scientific literature recommendation. It is observed that the proposed streaming algorithm achieves both execution speedup and memory saving by several orders of magnitude, compared with existing approaches.
关键词	Submodular optimization streaming algorithm news recommendation scientific literature recommendation
DOI	10.1109/ACCESS.2018.2871668
收录类别	SCI
语种	英语
资助项目	DoD[HDTRA1-13-1-0029] ; NSFC[61328102] ; NSFC[61629101] ; NSFC[91746301] ; NSF[DMS-1622433] ; NSF[AST-1547436] ; NSF[ECCS-1508051/1659025] ; NSF[CNS-1343155]
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000447994500001
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计	被引频次：11[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/4864
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Cui, Shuguang
作者单位	1.Univ Calif Davis, Dept Elect & Comp Engn, Davis, CA 95616 USA 2.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Yu, Qilian,Xu, Li,Cui, Shuguang. Streaming Algorithms for News and Scientific Literature Recommendation: Monotone Submodular Maximization With a d-Knapsack Constraint[J]. IEEE ACCESS,2018,6:53736-53747.
APA	Yu, Qilian,Xu, Li,&Cui, Shuguang.(2018).Streaming Algorithms for News and Scientific Literature Recommendation: Monotone Submodular Maximization With a d-Knapsack Constraint.IEEE ACCESS,6,53736-53747.
MLA	Yu, Qilian,et al."Streaming Algorithms for News and Scientific Literature Recommendation: Monotone Submodular Maximization With a d-Knapsack Constraint".IEEE ACCESS 6(2018):53736-53747.