View source for Coreset

{{Short description|Computational geometry concept}}
In [[computational geometry]], a '''coreset''' of an input set is a subset of points, such that solving a problem on the coreset provably yields similar results as solving the problem on the entire point set, for some given family of problems.<ref>{{Citation |last=Jubran |first=Ibrahim |title=Introduction to Coresets: Accurate Coresets |date=2019-10-19 |url=https://arxiv.org/abs/1910.08707 |access-date=2025-02-22 |publisher=arXiv |doi=10.48550/arXiv.1910.08707 |id=arXiv:1910.08707 |last2=Maalouf |first2=Alaa |last3=Feldman |first3=Dan}}</ref> Coresets are commonly used in [[Mathematical optimization]], [[Cluster analysis]] and [[Range Queries]] to reduce computational complexity while maintaining high accuracy. They allow algorithms to operate efficiently on large datasets by replacing the original data with a significantly smaller representative subset.<ref>{{Citation |last=Feldman |first=Dan |title=Introduction to Core-sets: an Updated Survey |date=2020 |url=https://arxiv.org/abs/2011.09384 |access-date=2025-02-22 |publisher=arXiv |doi=10.48550/ARXIV.2011.09384}}</ref>

Many natural geometric optimization problems have coresets that approximate an optimal solution to within a factor of {{math|1 + ''ε''}}, that can be found quickly (in [[linear time]] or near-linear time), and that have size bounded by a function of {{math|1/''ε''}} independent of the input size, where {{math|''ε''}} is an arbitrary positive number. When this is the case, one obtains a linear-time or near-linear time approximation scheme, based on the idea of finding a coreset and then applying an exact optimization algorithm to the coreset. Regardless of how slow the exact optimization algorithm is, for any fixed choice of {{math|''ε''}}, the running time of this approximation scheme will be {{math|''O''(1)}} plus the time to find the coreset.<ref name="Agarwal">{{citation
 | last1 = Agarwal | first1 = Pankaj K. | author1-link = Pankaj K. Agarwal
 | last2 = Har-Peled | first2 = Sariel | author2-link = Sariel Har-Peled
 | last3 = Varadarajan | first3 = Kasturi R.
 | editor1-last = Goodman | editor1-first = Jacob E. | editor1-link = Jacob E. Goodman
 | editor2-last = Pach | editor2-first = János | editor2-link = János Pach
 | editor3-last = Welzl | editor3-first = Emo | editor3-link = Emo Welzl
 | contribution = Geometric approximation via coresets
 | contribution-url = http://sarielhp.org/p/04/survey/
 | mr = 2178310
 | pages = 1–30
 | publisher = Cambridge Univ. Press, Cambridge
 | series = Mathematical Sciences Research Institute Publications
 | title = Combinatorial and Computational Geometry
 | volume = 52
 | year = 2005}}.</ref><ref>{{cite book |first=Frank |last=Nielsen | title=Introduction to HPC with MPI for Data Science |  year=2016 
| publisher=Springer |isbn=978-3-319-21903-5 | pages=259–272
|chapter=10. Fast approximate optimization in high dimensions with core-sets and fast dimension reduction | url=https://www.springer.com/gp/book/9783319219028 
|chapter-url=https://www.researchgate.net/publication/313162957 }}</ref>

== Definition ==
A coreset is a subset <math>S \subseteq P</math> of a point set <math>P</math>, possibly with associated weights, that preserves an optimization cost function within a factor of <math>1 \pm \epsilon</math>, where <math>\epsilon > 0</math> is some user defined approximation parameter. Formally, for an optimization problem with some cost function COST<math>\left( P \right)</math>, a coreset <math>S</math> satisfies the following inequality:<ref>{{Cite journal |last=Frahling |first=Gereon |last2=Sohler |first2=Christian |date=2005-05-22 |title=Coresets in dynamic geometric data streams |url=https://dl.acm.org/doi/10.1145/1060590.1060622 |journal=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing |series=STOC '05 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=209–217 |doi=10.1145/1060590.1060622 |isbn=978-1-58113-960-0}}</ref> 

<math>(1 - \epsilon)  \cdot </math> COST<math>\left( P \right)</math> <math>\leq</math> COST<math>\left( S \right)</math> <math>\leq</math> (1 + <math>\epsilon</math>) <math>\cdot</math> COST<math>\left( P \right)</math> 

== Applications ==
Coresets are used in a variety of problems, a few key examples include:<ref>{{Cite web |last=Nijsten |first=Sam |date=2024-07-10 |title=Range-Centric Coresets in Dynamic Geometric Streams |url=https://research.tue.nl/en/studentTheses/range-centric-coresets-in-dynamic-geometric-streams |url-status=live |access-date=2025-02-21 |website=Research Portal Eindhoven University of Technology}}</ref>

* '''Clustering''': Approximating solutions for [[K-means clustering]], [[K-medians clustering]] and [[Metric k-center|K-center clustering]] while significantly reducing computation.
* '''Range Queries''': Speeding up spatial searches in [[Geographic information system|Geographic Information Systems]] or large databases by efficiently summarizing data.
* '''Machine Learning:''' Enhancing performance in [[Hyperparameter optimization]] by working with a smaller representative set.

== References ==
{{reflist}}

[[Category:Computational geometry]]

{{algorithm-stub}}