DBSCAN - Space complexity of O(n)?
You can run DBSCAN without storing the distances in a matrix. This has the drawback that each time you visit a point, you have to recalculate all the relevant distances, which requires more time. However, the space complexity stays $O(n)$, since the only things you have in memory at any single time are the positions of the n points, their various labels, the neighbors of the current point and the neighbors of a particular neighbour in the case that the point turns out to be a core point.