Computer Engineering Commons^™

Minimum Coresets For Maxima Representation Of Multidimensional Data, Yanhao Wang, Michael Mathioudakis, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

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, coreset-based 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 �� of points in R �� , where �� is a small constant, and an error parameter �� ∈ (0, 1), a subset �� ⊆ �� …