Large Scale Disk-Based Metric Indexing Structure 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 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.ou