Scaling DBSCAN clustering - minHash?
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.