Projects per year
Abstract
Coresets are succinct summaries of large datasets such that, for a given problem, the solution obtained from a coreset is provably competitive with the solution obtained from the full dataset. As such, coresetbased data summarization techniques have been successfully applied to various problems, e.g., geometric optimization, clustering, and approximate query processing, for scaling them up to massive data. In this paper, we study coresets for the maxima representation of multidimensional data: Given a set P of points in R^d , where d is a small constant, and an error parameter ε ∈ (0, 1), a subset Q ⊆ P is an εcoreset for the maxima representation of P iff the maximum of Q is an εapproximation of the maximum of P for any vector u ∈ R^d , where the maximum is taken over the inner products between the set of points (P or Q) and u. We define a novel minimum εcoreset problem that asks for an εcoreset of the smallest size for the maxima representation of a point set. For the twodimensional case, we develop an optimal polynomialtime algorithm for the minimum εcoreset problem by transforming it into the shortestcycle problem in a directed graph. Then, we prove that this problem is NPhard in three or higher dimensions and present polynomialtime approximation algorithms in an arbitrary fixed dimension. Finally, we provide extensive experimental results on both real and synthetic datasets to demonstrate the superior performance of our proposed algorithms.
Original language  English 

Title of host publication  ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems (PODS) 
Publication status  Accepted/In press  Mar 2021 
MoE publication type  A4 Article in conference proceedings 
Projects
 1 Active

MLDB: Model Management Systems: Machine learning meets Database Systems
Mathioudakis, M. & Gionis, A.
01/09/2019 → 31/08/2023
Project: Research project