Streaming-model clustering

Status: dormant; 2007-2008 (supersedes any conflicting remarks left on this page; see the home page for definitions)

I have been working with Samir Khuller on streaming algorithms for variations of the k-center clustering problem.  Our paper titled "Streaming algorithms for k-center clustering with outliers and with anonymity" appeared in the APPROX2008 conference.  Here is its SpringerLink page; you can download the published paper there if you have a subscription.  In addition, the authors' version is available here; I may make corrections and updates to it in the future.

Note: Springer holds the copyright to this paper.  I am offering it here pursuant to the copyright transfer agreement, but further distribution may require copyright permission from Springer.

Last update: On 2008-08-28, I updated the publication notice and added a reference to this Web page.

Here are my slides from the conference, which include nice demonstrations of the parallelized Scaling Algorithm and the streaming algorithm for outliers but do not describe the streaming algorithm for anonymity (see the paper for that).

Clusterer code[Top]

Here is a package of supplementary code in Haskell.  Currently it contains an implementation of the essential parts of the streaming algorithm for clustering with outliers and a simple demonstration.

Last update: On 2008-06-18, initial posting.

Simplified outliers proof[Top]

Here is a simplified proof of correctness of the offline algorithm for k-center clustering with outliers.  (The algorithm is described in this paper.)  I found this proof on 2008-08-16.  I may add it to the main clustering paper at some point.