Benwei Wu

Benwei Wu

Auto-generated profile, based on publicly available information

Benwei Wu

University of Science and Technology of China, Hefei, China

Research Focus & Metrics

Academic Career Length

6Years (2021-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 December 2022 in Information Processing & Management
Verified
Journal Article
Closed access
BWBenwei Wu
Benwei Wu
KHKai Han
Kai Han
EZEnpei Zhang
Enpei Zhang

18 February 2021 in Proceedings of the ACM on Measurement and Analysis of Computing Systems
Verified
Journal Article
Open access
KHKai Han
Kai Han
SCShuang Cui
Shuang Cui
TZTianshuai Zhu
Tianshuai Zhu
EZEnpei Zhang
Enpei Zhang
BWBenwei Wu
Benwei Wu
HHe Huang
He Huang
Data summarization, i.e., selecting representative subsets of manageable size out of massive data, is often modeled as a submodular optimization problem. Although there exist extensive algorithms for submodular optimization, many of them incur large computational overheads and hence are not suitable for mining big data. In this work, we consider the fundamental problem of (non-monotone) submodular function maximization with a knapsack constraint, and propose simple yet effective and efficient algorithms for it. Specifically, we propose a deterministic algorithm with approximation ratio 6 and a randomized algorithm with approximation ratio 4, and show that both of them can be accelerated to achieve nearly linear running time at the cost of weakening the approximation ratio by an additive factor of ε. We then consider a more restrictive setting without full access to the whole dataset, and propose streaming algorithms with approximation ratios of 8+ε and 6+ε that make one pass and two passes over the data stream, respectively. As a by-product, we also propose a two-pass streaming algorithm with an approximation ratio of 2+ε when the considered submodular function is monotone. To the best of our knowledge, our algorithms achieve the best performance bounds compared to the state-of-the-art approximation algorithms with efficient implementation for the same problem. Finally, we evaluate our algorithms in two concrete submodular data summarization applications for revenue maximization in social networks and image summarization, and the empirical results show that our algorithms outperform the existing ones in terms of both effectiveness and efficiency.

7 June 2021 in ACM SIGMETRICS Performance Evaluation Review
Verified
Journal Article
Open access
KHKai Han
Kai Han
SCShuang Cui
Shuang Cui
TZTianshuai Zhu
Tianshuai Zhu
EZEnpei Zhang
Enpei Zhang
BWBenwei Wu
Benwei Wu
HHe Huang
He Huang
Data summarization, a fundamental methodology aimed at selecting a representative subset of data elements from a large pool of ground data, has found numerous applications in big data processing, such as social network analysis [5, 7], crowdsourcing [6], clustering [4], network design [13], and document/corpus summarization [14]. Moreover, it is well acknowledged that the "representativeness" of a dataset in data summarization applications can often be modeled by submodularity - a mathematical concept abstracting the "diminishing returns" property in the real world. Therefore, a lot of studies have cast data summarization as a submodular function maximization problem (e.g., [2]).

8 August 2022
Verified
Conference Paper
Closed access
BWBenwei Wu
Benwei Wu
KHKai Han
Kai Han
As an effective tool to extract representative summary from big data, data summarization is often cast into a submodular maximization problem. Although submodular maximization problem has a long research history, and many related algorithms have been born, these algorithms often have high computational complexity and are difficult to apply to the field of big data. Therefore, in recent years, research on low-time complexity algorithms has attracted extensive attention. In this paper, we mainly focus on the non-monotone submodular maximization problem under the setting of a knapsack and a partition matroid constraints. To solve it, we design a practical, effective and efficient algorithm called FASKP, that can achieve an approximation ratio of near 7.2 + ϵ using near linear runing time. As far as we know, the FASKP algorithm achieves the best approximate guarantee compared to existing algorithms with low-time complexity. Furthermore, we demonstrate how to apply FASKP in three real data summarization applications: image summarization (10K images), movie recommendation (11K movies), and revenue maximization on social networks (Youtube). Experimental results in real scenarios show that, compared with existing algorithms, the FASKP algorithm can consistently obtain the highest utility, which validates its superiority.