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.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.