2020/02/08 by Matteo Ceccarello, Ceccarello, Matteo, Andrea Pietracaprina +3
Computer Science · Decision Sciences · #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Multi-Criteria Decision Making #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2002.03175
openalex publication_date 2020/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Diversity maximization is a fundamental problem in web search and data\nmining. For a given dataset S of n elements, the problem requires to\ndetermine a subset of S containing k\≪ n "representatives" which minimize\nsome diversity function expressed in terms of pairwise distances, where\ndistance models dissimilarity. An important variant of the problem prescribes\nthat the solution satisfy an additional orthogonal requirement, which can be\nspecified as a matroid constraint (i.e., a feasible solution must be an\nindependent set of size k of a given matroid). While unconstrained diversity\nmaximization admits efficient coreset-based strategies for several diversity\nfunctions, known approaches dealing with the additional matroid constraint\napply only to one diversity function (sum of distances), and are based on an\nexpensive, inherently sequential, local search over the entire input dataset.\nWe devise the first coreset-based algorithms for diversity maximization under\nmatroid constraints for various diversity functions, together with efficient\nsequential, MapReduce and Streaming implementations. Technically, our\nalgorithms rely on the construction of a small coreset, that is, a subset of\nS containing a feasible solution which is no more than a factor 1-\ε\naway from the optimal solution for S. While our algorithms are fully general,\nfor the partition and transversal matroids, if \ε is a constant in\n(0,1) and S has bounded doubling dimension, the coreset size is independent\nof n and it is small enough to afford the execution of a slow sequential\nalgorithm to extract a final, accurate, solution in reasonable time. Extensive\nexperiments show that our algorithms are accurate, fast and scalable, and\ntherefore they are capable of dealing with the large input instances typical of\nthe big data scenario.\n