it is possible to have a test ? gist to better understand the pb?

hmm, as it is an internal variable, I think it might be difficult to test it? Besides, I think this change should be straightforward.

@agramfort I actually think this is fixing an algorithm bug: we shouldn't need to visit the same point twice.

In this kind of search algorithm, push_map would better be a set named seen.

Benchmark with the following sample codes:

import time

import numpy as np

from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler


##############################################################################
# Generate sample data
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=10000, centers=centers, cluster_std=0.4,
                            random_state=0)

X = StandardScaler().fit_transform(X)
##############################################################################
# Compute DBSCAN
t1 = time.time()
db = DBSCAN(eps=0.1, algorithm="ball_tree", min_samples=10).fit(X)
t2 = time.time()
print "Time = %s" % (t2 - t1)

Without this patch: Time = 0.110082864761

With this patch: Time = 0.136781930923

@jnothman merge if you're happy. No strong feeling here.

@viirya can you confirm that this makes a substantial reduction to the memory usage in some reasonable cases? Can you give a sense of how much (by using memory_profiler, or counting the number of times seen.count() == 1)?

@jnothman Using the sample codes above, with 10000 sample data, I count the number of times seen.count(v) == 1, the number is 548248.

To clarify, in your initial description you say "the duplicate elements in this vector cause memory pressure". Is that because you actually had a problem where there was a memory shortage, which this patch fixes? It still seems surprising.

When you run the algorithm with more than 1 million sample data, with enough big eps, the vector will soon have many duplicate elements. It consumes much memory to cause the program killed if your memory is already occupied by the huge distance matrix or other variables. I am not sure if I answer your question. But it is the motivation of this patch.

I guess I'd like to clarify whether the big distance matrix is really the
issue there, for which this is small beans (costing a small increase in
runtime) relative to #6813.

On 26 May 2016 at 13:39, Liang-Chi Hsieh notifications@github.com wrote:

When you run the algorithm with more than 1 million sample data, with
enough big eps, the vector will soon have many duplicate elements. It
consumes much memory to cause the program killed if your memory is already
occupied by the huge distance matrix or other variables. I am not sure if I
answer your question. But it is the motivation of this patch.

—
You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub
#6799 (comment)

oh. Actually, this is also helpful even #6813 is applied. I applied #6813 but it can still fail under some cases due to the duplicate elements in the vector.

ping @jnothman any more concerns about this?

LGTM. Usually we get two reviews, but @agramfort's was a +0, so I'll wait for another.

ok fair enough

please fix the docstring and +1 for merge

@jnothman @agramfort Thanks! I've updated the document.

thanks @viirya