  Data series are a special type of multidimensional data present in numerous
domains, where similarity search is a key operation that has been extensively
studied in the data series literature. In parallel, the multidimensional
community has studied approximate similarity search techniques. We propose a
taxonomy of similarity search techniques that reconciles the terminology used
in these two domains, we describe modifications to data series indexing
techniques enabling them to answer approximate similarity queries with quality
guarantees, and we conduct a thorough experimental evaluation to compare
approximate similarity search techniques under a unified framework, on
synthetic and real datasets in memory and on disk. Although data series differ
from generic multidimensional vectors (series usually exhibit correlation
between neighboring values), our results show that data series techniques
answer approximate %similarity queries with strong guarantees and an excellent
empirical performance, on data series and vectors alike. These techniques
outperform the state-of-the-art approximate techniques for vectors when
operating on disk, and remain competitive in memory.
