IEEE Access · 2018 · 16 citations · 27 references
ComputingComputer ScienceMathematicsAlgorithmsData MiningRecommender SystemsApproximation AlgorithmsCombinatorial OptimizationLinear ProgrammingLiterature MiningOptimization For Machine LearningStreaming AlgorithmsKnapsack ApproximationNews RecommendationNews Recommendation SystemsScientific Literature MiningSubmodular MaximizationSubmodular Optimization
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) - e)-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.
27
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
The PageRank Citation Ranking : Bringing Order to the Web
Lawrence M. Page, Sergey Brin, Rajeev Motwani et al. · 1999 · 12.7K citations
Cost-effective outbreak detection in networks
Jure Leskovec, Andreas Krause, Carlos Guestrin et al. · 2007 · 2.5K citations · Full text
Public Health, Environmental Sciences, Outbreak Detection +7
Random sampling with a reservoir
Jeffrey Scott Vitter · ACM Transactions on Mathematical Software · 1985 · 1.8K citations · Full text