Projekt per år
Sammanfattning
We study the problem of extracting a small subset of representative items from a large data stream. In many data mining and machine learning applications such as social network analysis and recommender systems, this problem can be formulated as maximizing a monotone submodular function subject to a cardinality constraint k. In this work, we consider the setting where data items in the stream belong to one of several disjoint groups and investigate the optimization problem with an additional fairness constraint that limits selection to a given number of items from each group. We then propose efficient algorithms for the fairnessaware variant of the streaming submodular maximization problem. In particular, we first give a (1/2ε)approximation algorithm that requires O((1/ε) log(k/ε)) passes over the stream for any constant ε>0. Moreover, we give a singlepass streaming algorithm that has the same approximation ratio of (1/2ε) when unlimited buffer sizes and postprocessing time are permitted, and discuss how to adapt it to more practical settings where the buffer sizes are bounded. Finally, we demonstrate the efficiency and effectiveness of our proposed algorithms on two realworld applications, namely maximum coverage on large graphs and personalized recommendation.
Originalspråk  engelska 

Titel på värdpublikation  Proceedings of the Web Conference 2021 (WWW '21) 
Förlag  ACM 
Utgivningsdatum  2021 
Sidor  1340–1350 
ISBN (tryckt)  9781450383127 
ISBN (elektroniskt)  9781450383127 
DOI  
Status  Publicerad  2021 
MoEpublikationstyp  A4 Artikel i en konferenspublikation 
Evenemang  The Web Conference 2021  Ljubljana, Slovenien Varaktighet: 19 apr. 2021 → 23 apr. 2021 https://www2021.thewebconf.org/ 
Vetenskapsgrenar
 113 Data och informationsvetenskap
Projekt
 1 Aktiv

MLDB: Model Management Systems: Machine learning meets Database Systems
Gionis, A., Mahadevan, A., Maniatis, A., Merchant, A., Pai, S. G. & Mathioudakis, M.
Suomen Akatemia Projektilaskutus
01/09/2019 → 31/12/2023
Projekt: Finlands Akademi: Akademiprojektsbidrag