2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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, 2013 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, 2013 at 13:04

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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, 2013 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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