Currently there are two approaches available to handle large datasets:

• sample weight support allows you to collapse near-duplicate points
• precomputed sparse matrix of neighbors allows the memory costs to be limited to those within the eps neighborhood, with the computation taken out of DBSCAN's control.

Is neither acceptable to you?

sample weight support allows you to collapse near-duplicate points

This seems not really resolve this issue and I think we still have this issue if dataset points are not so much duplicate in general.

precomputed sparse matrix of neighbors allows the memory costs to be limited to those within the eps neighborhood, with the computation taken out of DBSCAN's control.

For the option 2, as we choose ball-tree (or other tree-based nn), DBSCAN actually computes sparse matrix of neighbors within eps for us. However, with the example program on 1 million samples, the memory footprint of the matrix still causes the program failed. In order to make this option work for large-scale data, the allowed eps must be limited to very small range as I think. For such use cases, I think to provide an option that can significantly reduce memory pressure for large datasets is good.

@jnothman how explicit are the docs on the precomputed sparse matrix? I think some people are missing that possibility.

docstring:

"
93
94 Sparse neighborhoods can be precomputed using
95 :func:`NearestNeighbors.radius_neighbors_graph
"

narrative:

"""
This implementation is by default not memory efficient because it constructs a full pairwise similarity matrix in the case where kd-trees or ball-trees cannot be used (e.g. with sparse matrices). This matrix will consume n^2 floats. A couple of mechanisms for getting around this are:

• A sparse radius neighborhood graph (where missing entries are presumed to be out of eps) can be precomputed in a memory-efficient way and dbscan can be run over this with metric='precomputed'.
• The dataset can be compressed, either by removing exact duplicates if these occur in your data, or by using BIRCH. Then you only have a relatively small number of representatives for a large number of points. You can then provide a sample_weight when fitting DBSCAN.
  """

What's the status of this PR? I'd be very much interested in a memory-efficient version of DBSCAN and this seems to do it. But on 0.19.1 I get (after replicating all the example code above):

In [8]: db = DBSCAN(eps=1.3, algorithm="ball_tree", min_samples=10, mode="mem").fit(X)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-8-74361e839f84> in <module>()
----> 1 db = DBSCAN(eps=1.3, algorithm="ball_tree", min_samples=10, mode="mem").fit(X)

TypeError: __init__() got an unexpected keyword argument 'mode'

In [9]: 

If others think this is right way to go, I can continue this work.

Let me sync with current branch and address above comments first.

@jnothman I think I addressed your previous comments. Please help review this again. Thanks.

also cc @agramfort

Ok. Then I'm closing this.