Distributed Pareto optimization for subset selection

Qian，Chao1; Li，Guiying1; Feng，Chao1; Tang，Ke2

2018

1045-0823

IJCAI International Joint Conference on Artificial Intelligence

2018-July

1492-1498

Stockholm, Sweden

International Joint Conferences on Artificial Intelligence

The subset selection problem that selects a few items from a ground set arises in many applications such as maximum coverage, influence maximization, sparse regression, etc. The recently proposed POSS algorithm is a powerful approximation solver for this problem. However, POSS requires centralized access to the full ground set, and thus is impractical for large-scale real-world applications, where the ground set is too large to be stored on one single machine. In this paper, we propose a distributed version of POSS (DPOSS) with a bounded approximation guarantee. DPOSS can be easily implemented in the MapReduce framework. Our extensive experiments using Spark, on various real-world data sets with size ranging from thousands to millions, show that DPOSS can achieve competitive performance compared with the centralized POSS, and is almost always better than the state-of-the-art distributed greedy algorithm RANDGREEDI.

其他

英语

EI

[2017YFB1003102] ; [NA150123] ; Shenzhen Science and Technology Innovation Commission[ZDSYS201703031748284] ; National Natural Science Foundation of China[61672478] ; National Natural Science Foundation of China[61603367]

20184406016149

Artificial intelligence ; Multiobjective optimization ; Pareto principle ; Scheduling algorithms

Artificial Intelligence:723.4 ; Mathematics:921 ; Optimization Techniques:921.5

2-s2.0-85055699108

Scopus

1.,Anhui Province Key Lab of Big Data Analysis and Application,University of Science and Technology of China,Hefei,230027,China
2.,Shenzhen Key Lab of Computational Intelligence,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China

Qian，Chao,Li，Guiying,Feng，Chao,et al. Distributed Pareto optimization for subset selection[C]:International Joint Conferences on Artificial Intelligence,2018:1492-1498.