We present a technical survey on the state of the art approaches in data reduction and the coreset framework. These include geometric decompositions, gradient methods, random sampling, sketching and random projections. We further outline their importance for the design of streaming algorithms and give a brief overview on lower bounding techniques.

Coresets-Methods and History: A Theoreticians Design Pattern for Approximation and Streaming Algorithms / Munteanu, Alexander; Schwiegelshohn, Chris. - In: KI - KÜNSTLICHE INTELLIGENZ. - ISSN 0933-1875. - STAMPA. - 32:1(2018), pp. 37-53. [10.1007/s13218-017-0519-3]

Coresets-Methods and History: A Theoreticians Design Pattern for Approximation and Streaming Algorithms

Schwiegelshohn, Chris
2018

Abstract

We present a technical survey on the state of the art approaches in data reduction and the coreset framework. These include geometric decompositions, gradient methods, random sampling, sketching and random projections. We further outline their importance for the design of streaming algorithms and give a brief overview on lower bounding techniques.
2018
Coresets, Sketching, Sampling, Gradient methods, Streaming, Clustering, Regression, Subspace approximation
01 Pubblicazione su rivista::01a Articolo in rivista
Coresets-Methods and History: A Theoreticians Design Pattern for Approximation and Streaming Algorithms / Munteanu, Alexander; Schwiegelshohn, Chris. - In: KI - KÜNSTLICHE INTELLIGENZ. - ISSN 0933-1875. - STAMPA. - 32:1(2018), pp. 37-53. [10.1007/s13218-017-0519-3]
File allegati a questo prodotto
File Dimensione Formato  
Munteanu_Coresets‑Methods_2018.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 3.32 MB
Formato Adobe PDF
3.32 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1085858
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 48
  • ???jsp.display-item.citation.isi??? 34
social impact