If you have a very large data set of $n$ vectors and you want to cluster them according to some metric measure, what is the current state of the art when you can not afford to do more than $\Theta(n)$ work? I am interested in methods that work well in practice as well as having nice theoretical properties.

A web search brings up "A sublinear time approximation scheme for clustering in metric spaces" by P. Indyk as the most cited paper in the area.

  • $\begingroup$ THere's also lots of work on sampling and streaming-based methods. These tend to work best when the metric is the Euclidean distance (or relatives). I'm not sure what your situation is. $\endgroup$ – Suresh Venkat Mar 7 '13 at 12:49
  • $\begingroup$ @SureshVenkat Weighted Euclidean distance works for me. I can find lists of papers, what I am not clear on is which are considered the current state of the art from an algorithms/practice point of view. $\endgroup$ – Majid Mar 7 '13 at 13:04

At the risk of sounding immodest, I wrote a short survey on stream clustering a few years ago. It's a little out of date, but not overly so, and doing forward citations will get you to the recent work in the area.

| cite | improve this answer | |
  • $\begingroup$ Thank you. I can see that people are very interested in streams. In my problem I have access to all the data, it is just very large. $\endgroup$ – Majid Mar 14 '13 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.