Sublinear time approximate clustering

Nina Mishra, Dan Oblinger, Leonard B Pitt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages439-447
Number of pages9
StatePublished - Dec 1 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2001 Operating Section Proceedings, American Gas Association
CountryUnited States
CityDallas, TX
Period4/30/015/1/01

Keywords

  • Algorithms
  • Measurement
  • Performance
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Sublinear time approximate clustering'. Together they form a unique fingerprint.

Cite this