Most clustering algorithms I've seen start with creating a each-to-each distances among all points, which becomes problematic on larger datasets. Is there one that doesn't do it? Or does it in some sort of partial/approximate/staggered approach?
Which clustering algorithm/implemention takes less than O(n^2) space?
Is there a list of algorithms and their Time and Space requirements somewhere?
K-Means and Mean-Shift use the raw sample descriptors (no need to pre-compute an affinity matrix).
Otherwise, for spectral clustering or power iteration clustering, you can use a sparse matrix representation (e.g. Compressed Sparse Rows) of the k-nearest-neighbours affinity matrix (for some distance or affinity metric). If k is small (let say 5 or 10). You will get a very space efficient representation (2 * n_samples * k * 8 bytes for double precision floating point values).
Some clustering algorithms can use spatial index structures. This allows for example DBSCAN and OPTICS to run in $O(n\log n)$ time (as long as the index allows $O(\log n)$ queries).
Obviously, an algorithm that runs in this complexity does not build a $O(n^2)$ distance matrix.
For some algorithms, such as hierarchical clustering with single-linkage and complete-linkage, there are optimized algorithms available (SLINK, CLINK). It's just that most people use whatever they can get and whatever is easy to implement. And hierarchical clustering is easy to implement naively, using $n$ iterations over a $n^2$ distance matrix (resulting in an $O(n^3)$ algorithm ...).
I'm not aware of a complete list comparing clustering algorithms. There probably are 100+ clustering algorithms, after all. There are at least a dozen k-means variants, for example. Plus, there is run-time complexity as well as memory complexity; there is average-case and worst-case. There are huge implementation differences (e.g. single-link mentioned above; and DBSCAN implementations that do not use an index, and thus are in $O(n^2)$, and while they do not need to store the full $n\times n$ distance matrix, they then still need to compute all pairwise distances). Plus there are tons of parameters. For k-means, $k$ is critical. For pretty much any algorithm, the distance function make a huge difference (any many implementations only allow Euclidean distance ...). And once you get to expensive distance functions (beyond trivial stuff like Euclidean), the number of distance computations may quickly be the main part. So you'd then need to differentiate between the number of operations in total, and the number of distance computations needed. So an algorithm that is in $O(n^2)$ operations but only $O(n)$ distance computations may easily outperform an algorithm that is $O(n \log n)$ in both, when the distance functions are really expensive (say, the distance function itself is $O(n)$).
Good question. A straw man method for say 3 nearest neighbors is to sample Nsample neighbors of each data point, keeping the nearest 3. While trivial, running this for a few values of Nsample will give you some idea of signal / noise ratio, near / background noise, easily plotted for your data. An additional trick is to then check neighbors of neighbors, to see if any of those ar nearer than direct neighbors. Also, if the input data is already well-shuffled, sample in blocks, otherwise cache will thrash.
(Added): see fastcluster
in R and I believe in SciPy v0.11.
For text, see
google-all-pairs-similarity-search.
Repeat, "An appropriate dissimilarity measure is far more important in obtaining success with clustering than choice of clustering algorithm" — choosing-clustering-method.
