Beyond the metric space model

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 satisfy the metric properties have 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, as they require to use nonmetric similarity measures. As the term nonmetric simply means that a similarity function does not satisfy some (or all) the properties of a metric, we restrict its definition to nonmetric similarity functions that are "context-free and static", that is, the similarity between two objects is constant regardless of the context (time, user, query, other objects in the collection, etc.).