Agenda

Speaker: Andrea A. Pietracaprina, ​University of Padova​

Abstract
Given a dataset of points in a metric space and an integer k, a diversity maximization problem requires determining a subset of k points maximizing some diversity objective measure, e.g., the minimum or the average distance between a pair of points in the subset. Diversity maximization problems are computationally hard,hence only approximate solutions can be hoped for. Although its applications are mostly in massive data analysis, most of the past research on diversity maximization has concentrated on the standard sequential setting. Thus, there is a need for efficient algorithms in computational settings that can handle very large datasets, such as those at the base of the MapReduce and the Streaming models. In this work we provide algorithms for these models in the special case of metric spaces of bounded doubling dimension, which include the important family of Euclidean spaces of constant dimension. Our results show that despite the inherent space-constraints of the two models, for a variety of diversity objective functions, we can achieve efficient MapReduce or Streaming algorithms yielding an (alpha+epsilon)-approximation ratio, for any constant epsilon>0, where alpha the is best approximation ratio achieved by a standard polynomial-time, linear-space sequential algorithm for the same diversity criterion. As for other approaches in the literature, our algorithms revolve upon the determination of a high-quality core-set, that is, a (much) smaller subset of the input dataset which contains a good approximation to the optimal solution for the whole dataset. (Joint work with  Matteo Ceccarello, Andrea Pietracaprina, and Eli Upfal based on a paper to appear at VLDB’17.)

Bio sketch
Andrea A. Pietracaprina received the Laurea degree (summa cum laude) in Computer Science (1987) from the University of Pisa, Italy, co-winning best undergraduate thesis awards from IBM-Italia and UNITEAM. He received the M.Sc. (1991) and Ph.D. (1994), both in Computer Science, from the University of Illinois at Urbana-Champaign, IL, USA. Since 1994, he has been with the University of Padova. Since 2002 he is Full Professor at the Department of Information Engineering, where he served as vice chair from 2008 to 2013. Andrea Pietracaprina's research interests concern: models of computation, algorithms and data structures for parallel and/or hierarchical platforms, data mining and ad-hoc networks. His research results have been published in over 80 papers appeared in international journals, conference proceedings, and collections (including an encyclopedia). He has been Principal Investigator of the project MIUR-PRIN AlgoDEEP (2010-2012), and of projects funded by University of Padova, CNR, and NATO. He has been key researcher in several projects funded by MIUR, CNR, and EU. He has also been reviewer for projects funded by MIUR and EU (5th Framework Programme). Since 2010 he is member of the editorial board of the Journal of Discrete Algorithms (Elsevier). From 2004 to 2009 he was Associate Editor for IEEE TPDS. In 2008 he was Guest co-Editor of the Special Issue of Theoretical Computer Science 408(2-3). He has been Member of the Program Committee of several international conferences, including: ACM-SIAM SODA (2017) ACM SPAA (2002, 2005, 2008); ICALP (2014); IEEE-IPDPS (2008, 2010, 2012, 2016); EURO-PAR Conference (1998, 2004, 2005, 2009, 2014); ACM Computing Frontiers (2010, 2013, 2015); PKDDECML (2015). He has also been involved in the organization of a number of international conferences (ACM SPAA'96, ESA'98, ICALP'06) and schools. Since 1999 he has been Member of the Advisory Board of the EURO-PAR Conference.