This special issue contains four selected papers from the conference titled The Second International Workshop on Similarity Search and Applications (SISAP) and held in Prague in August, 2009. These contributions have been significantly extended and cover the theoretical as well as practical issues of similarity searching in metric spaces.