Applying density based clustering (DBSCAN) on $50k$ data points and about $2k$-$4k$ features, I achieve the desired results.

However, scaling this to $10$ million data points requires a creatively efficient implementation since DBSCAN requires $O(n^2)$ to calculate the distance matrix and crushes my memory.

There must be some efficient sampling-based method to overcome this, ideally something similar to minHash - but I'm not sure how to approach this, and if there exists a solution that can work on existing sklearn DBSCAN algorithm. Any ideas?


DBSCAN is O(n) times the cost of a neighbor search.

If you use an index like LSH that could answer neighborhood search in O(1) (assuming a very even data distribution, with O(1) neighbors per point) then DBSCAN can run in O(n) plus the time needed to build such an index.

Yes, minHash indexes could be used if they are appropriate for your data and distance.

  • $\begingroup$ Could you please elaborate how to use LSH for this purpose? $\endgroup$
    – Adam
    Dec 26 '17 at 13:54
  • $\begingroup$ Use LSH to provide the RangeQuery function. $\endgroup$ Dec 27 '17 at 11:50

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.