This paper presents a scalable method for automatically discovering frequent visual objects in large multimedia collections even if their size is very small. It first formally revisits the problem of mining or discovering such objects, and then generalizes two kinds of existing methods for probing candidate object seeds: weighted adaptive sampling and hashingbased methods. The idea is that the collision frequencies obtained with hashing-based methods can actually be converted into a prior probability density function given as input to a weighted adaptive sampling algorithm. This allows for an evaluation of any hashing scheme effectiveness in a more generalized way, and a comparison with other priors, e.g. guided by visual saliency concerns. We then introduce a new hashing strategy, working first at the visual level, and then at the geometric level. This strategy allows us to integrate weak geometric constraints into the hashing phase itself and not only neighborhood constraints as in previous works. Experiments conducted on a new dataset introduced in this paper will show that using this new hashing-based prior allows a drastic reduction of the number of tentative probes required to discover small objects instantiated several times in a large dataset.