Space-Efficient Sampling

Sudipto Guha, Andrew McGregor
Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, PMLR 2:171-178, 2007.

Abstract

We consider the problem of estimating nonparametric probability density functions from a sequence of independent samples. The central issue that we address is to what extent this can be achieved with only limited memory. Our main result is a space-efficient learning algorithm for determining the probability density function of a piecewise-linear distribution. However, the primary goal of this paper is to demonstrate the utility of various techniques from the burgeoning field of data stream processing in the context of learning algorithms.

Cite this Paper


BibTeX
@InProceedings{pmlr-v2-guha07a, title = {Space-Efficient Sampling}, author = {Guha, Sudipto and McGregor, Andrew}, booktitle = {Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics}, pages = {171--178}, year = {2007}, editor = {Meila, Marina and Shen, Xiaotong}, volume = {2}, series = {Proceedings of Machine Learning Research}, address = {San Juan, Puerto Rico}, month = {21--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v2/guha07a/guha07a.pdf}, url = {https://proceedings.mlr.press/v2/guha07a.html}, abstract = {We consider the problem of estimating nonparametric probability density functions from a sequence of independent samples. The central issue that we address is to what extent this can be achieved with only limited memory. Our main result is a space-efficient learning algorithm for determining the probability density function of a piecewise-linear distribution. However, the primary goal of this paper is to demonstrate the utility of various techniques from the burgeoning field of data stream processing in the context of learning algorithms.} }
Endnote
%0 Conference Paper %T Space-Efficient Sampling %A Sudipto Guha %A Andrew McGregor %B Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2007 %E Marina Meila %E Xiaotong Shen %F pmlr-v2-guha07a %I PMLR %P 171--178 %U https://proceedings.mlr.press/v2/guha07a.html %V 2 %X We consider the problem of estimating nonparametric probability density functions from a sequence of independent samples. The central issue that we address is to what extent this can be achieved with only limited memory. Our main result is a space-efficient learning algorithm for determining the probability density function of a piecewise-linear distribution. However, the primary goal of this paper is to demonstrate the utility of various techniques from the burgeoning field of data stream processing in the context of learning algorithms.
RIS
TY - CPAPER TI - Space-Efficient Sampling AU - Sudipto Guha AU - Andrew McGregor BT - Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics DA - 2007/03/11 ED - Marina Meila ED - Xiaotong Shen ID - pmlr-v2-guha07a PB - PMLR DP - Proceedings of Machine Learning Research VL - 2 SP - 171 EP - 178 L1 - http://proceedings.mlr.press/v2/guha07a/guha07a.pdf UR - https://proceedings.mlr.press/v2/guha07a.html AB - We consider the problem of estimating nonparametric probability density functions from a sequence of independent samples. The central issue that we address is to what extent this can be achieved with only limited memory. Our main result is a space-efficient learning algorithm for determining the probability density function of a piecewise-linear distribution. However, the primary goal of this paper is to demonstrate the utility of various techniques from the burgeoning field of data stream processing in the context of learning algorithms. ER -
APA
Guha, S. & McGregor, A.. (2007). Space-Efficient Sampling. Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 2:171-178 Available from https://proceedings.mlr.press/v2/guha07a.html.

Related Material