Résumé (EN)

In order to achieve large scalability, indexing structures are usually distributed to incorporate more of expensive main memory during the query processing. In this paper, an in- dexing structure, that does not su er from a performance degradation by its transition from main memory storage to hard drive, is proposed. The high e ciency of the index is achieved using a very e ective pruning based on precom- puted distances and so called locality phenomenon which substantially diminishes the number of retrieved candidates. The trade-o s for the large scalability are, rstly, the ap- proximation and, secondly, longer query times, yet both are still bearable enough for recent multimedia content-based search systems, proved by an evaluation using visual and audio data and both metric and semi-metric distance func- tions. The tuning of the index's parameters based on the analysis of the particular's data intrinsic dimensionality is also discussed.