Maybe this is a silly question but I actually can't fulfill that by myself. I'm reading some papers about similarity metrics and I always find that for a distance function $d$ the triangle inequality is needed in order to support in indexing techniques and to implement, for instance, nearest neighbors queries.
Thus my question is: why is that property needed? Isn't indexing possible in presence of a distance function which does not fulfill the triangle inequality?
Thanks for your insights!