Large scale disk-based metric indexing structure for approximate information retrieval by content

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 indexing 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 precomputed 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 approximation 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 functions. The tuning of the index's parameters based on the analysis of the particular's data intrinsic dimensionality is also discussed