Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint

Kai Han; Shuang Cui; Tianshuai Zhu; Enpei Zhang; Benwei Wu; Zhizhuo Yin; Tong Xu; Shaojie Tang; He Huang

doi:10.1145/3410220.3453922

Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint

Kai Han
, Shuang Cui
, Tianshuai Zhu
, Enpei Zhang
, Benwei Wu
, Zhizhuo Yin
, Tong Xu
, Shaojie Tang
, He Huang

Management Science and Systems

University at Buffalo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

12 Scopus citations

Abstract

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]).

Original language	English
Title of host publication	SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems
Publisher	Association for Computing Machinery, Inc
Pages	65-66
Number of pages	2
ISBN (Electronic)	9781450380720
DOIs	https://doi.org/10.1145/3410220.3453922
State	Published - May 31 2021
Event	2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2021 - Virtual. Online, China Duration: Jun 14 2021 → Jun 18 2021

Publication series

Name	SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

Conference

Conference	2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2021
Country/Territory	China
City	Virtual. Online
Period	06/14/21 → 06/18/21

Keywords

data summarization
machine learning
submodular function maximization

Access to Document

10.1145/3410220.3453922

Cite this

Han, K., Cui, S., Zhu, T., Zhang, E., Wu, B., Yin, Z., Xu, T., Tang, S., & Huang, H. (2021). Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint. In SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems (pp. 65-66). (SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems). Association for Computing Machinery, Inc. https://doi.org/10.1145/3410220.3453922

Han, Kai ; Cui, Shuang ; Zhu, Tianshuai et al. / Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint. SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery, Inc, 2021. pp. 65-66 (SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems).

@inproceedings{06fa0ce99af447bab25091ef07c34a4d,

title = "Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint",

abstract = "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]).",

keywords = "data summarization, machine learning, submodular function maximization",

author = "Kai Han and Shuang Cui and Tianshuai Zhu and Enpei Zhang and Benwei Wu and Zhizhuo Yin and Tong Xu and Shaojie Tang and He Huang",

note = "Publisher Copyright: {\textcopyright} 2021 Owner/Author.; 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2021 ; Conference date: 14-06-2021 Through 18-06-2021",

year = "2021",

month = may,

day = "31",

doi = "10.1145/3410220.3453922",

language = "English",

series = "SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems",

publisher = "Association for Computing Machinery, Inc",

pages = "65--66",

booktitle = "SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems",

}

Han, K, Cui, S, Zhu, T, Zhang, E, Wu, B, Yin, Z, Xu, T, Tang, S & Huang, H 2021, Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint. in SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery, Inc, pp. 65-66, 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2021, Virtual. Online, China, 06/14/21. https://doi.org/10.1145/3410220.3453922

Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint. / Han, Kai; Cui, Shuang; Zhu, Tianshuai et al.
SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery, Inc, 2021. p. 65-66 (SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint

AU - Han, Kai

AU - Cui, Shuang

AU - Zhu, Tianshuai

AU - Zhang, Enpei

AU - Wu, Benwei

AU - Yin, Zhizhuo

AU - Xu, Tong

AU - Tang, Shaojie

AU - Huang, He

PY - 2021/5/31

Y1 - 2021/5/31

N2 - 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]).

AB - 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]).

KW - data summarization

KW - machine learning

KW - submodular function maximization

UR - https://www.scopus.com/pages/publications/85108566082

U2 - 10.1145/3410220.3453922

DO - 10.1145/3410220.3453922

M3 - Conference contribution

T3 - SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

SP - 65

EP - 66

BT - SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

PB - Association for Computing Machinery, Inc

T2 - 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2021

Y2 - 14 June 2021 through 18 June 2021

ER -

Han K, Cui S, Zhu T, Zhang E, Wu B, Yin Z et al. Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint. In SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery, Inc. 2021. p. 65-66. (SIGMETRICS 2021 - Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems). doi: 10.1145/3410220.3453922

Approximation Algorithms for Submodular Data Summarization with a Knapsack Constraint

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this