Introduction to Core-sets: an Updated Survey
This survey is significant for researchers and practitioners in optimization and machine learning who need to process large, streaming, or distributed datasets efficiently, providing a unified and simplified view of core-set constructions.
This survey paper addresses the challenge of processing large datasets in real-time and distributed environments by summarizing the input "big data" into a smaller "core-set." The core-set is designed to provide approximately the same answer for any query as the original dataset, enabling traditional algorithms to be applied efficiently.
In optimization or machine learning problems we are given a set of items, usually points in some metric space, and the goal is to minimize or maximize an objective function over some space of candidate solutions. For example, in clustering problems, the input is a set of points in some metric space, and a common goal is to compute a set of centers in some other space (points, lines) that will minimize the sum of distances to these points. In database queries, we may need to compute such a some for a specific query set of $k$ centers. However, traditional algorithms cannot handle modern systems that require parallel real-time computations of infinite distributed streams from sensors such as GPS, audio or video that arrive to a cloud, or networks of weaker devices such as smartphones or robots. Core-set is a "small data" summarization of the input "big data", where every possible query has approximately the same answer on both data sets. Generic techniques enable efficient coreset \changed{maintenance} of streaming, distributed and dynamic data. Traditional algorithms can then be applied on these coresets to maintain the approximated optimal solutions. The challenge is to design coresets with provable tradeoff between their size and approximation error. This survey summarizes such constructions in a retrospective way, that aims to unified and simplify the state-of-the-art.