Automatically linking multimedia documents that contain one or several instances of the same visual object has many applications including: salient events detection, relevant patterns discovery in scientific data or simply web browsing through hyper-visual links. Whereas efficient methods now exist for searching rigid objects in large collections, discovering them from scratch is still challenging in terms of scalability, particularly when the targeted objects are small compared to the whole image. In this PhD, we first revisited formally the problem of mining or discovering such objects, and then generalized two kinds of existing methods for probing candidate object seeds: weighted adaptive sampling and hashing based methods. We then introduced a new high-dimensional data hashing strategy, that works first at the visual level, and then at the geometric level. We conducted large-scale experiments on millions of images and on a new dedicated evaluation dataset (FlickrBelgaLogos.html) that we shared with the community. We did show that our method outperforms the reference method Geometric Min Hash. Based on this contribution, we then address the problem of suggesting object-based visual queries in a multimedia search engine. State-of-the-art visual search systems are usually based on the query-by-window paradigm: a user selects any image region containing an object of interest and the system returns a ranked list of images that are likely to contain other instances of the query object. User's perception of these tools is however affected by the fact that many submitted queries actually return nothing or only junk results (complex non-rigid objects, higher-level visual concepts, etc.).
