Sublinear time approximate clustering

Nina Mishra, Daniel Oblinger, Leonard PittSODA 2001 · OpenReview

Abstract

Clustering is of central importance in a number of disciplines including Machine Learning, Statistics, and Data Mining. This paper has two foci: (1) It describes how existing algorithms for clustering can benefit from simple sampling techniques arising from work in statistics [Pol84]. (2) It motivates and introduces a new model of clustering that is in the spirit of the “PAC (probably approximately correct)” learning model, and gives examples of efficient PAC-clustering algorithms.
BibTeX
@inproceedings{mishra2001sublinear,
  author = {Nina Mishra and Daniel Oblinger and Leonard Pitt},
  title = {{Sublinear time approximate clustering}},
  booktitle = {SODA},
  year = {2001},
  url = {https://openreview.net/forum?id=CBIvAdc99G},
}

Loading related content...

Figure