Abstract
The metric space model has represented a reasonable trade-off concerning the efficiency and effectiveness problem in similarity search. However, complex similarity models that do not hold the metric properties has been used in a wide variety of research domains like multimedia information retrieval, digital libraries, biological and chemical databases, time series analysis, and biometry [2].
All these domains require the management of very large data collections, but the algorithms and data structures for searching in metric spaces cannot be used directly in these new scenarios, as they require to use nonmetric similarity measures. As the term nonmetric simply means that a similarity function does not hold some (or all) properties of a metric distance, we restrict its definition to nonmetric similarity functions that are “context-free and static”, that is, the similarity between two objects is constant whatever the context is.