Content deleted Content added
Line 17:
=== STREAM ===
STREAM is an algorithm for clustering data streams described by Guha, Mishra, Motwani and O'Callaghan <ref name="CDS"> S. Guha, N. Mishra, R. Motwani, L. O'Callaghan. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.1927 Clustering Data Streams]. Proceedings of the Annual Symposium on Foundations of Computer Science, 2000</ref> which achieves a constant factor approximation for the k-Median problem in a single pass and using small space.
'''''Theorem''': STREAM can solve the k-Median problem on a data stream with time O(n<sup>1+e</sup>) and space θ(n<sup>ε</sup>) up to a factor 2<sup>O(1/e)</sup>, where n the number of points and e<1/2''.
| |||