  With the continued digitization of societal processes, we are seeing an
explosion in available data. This is referred to as big data. In a research
setting, three aspects of the data are often viewed as the main sources of
challenges when attempting to enable value creation from big data: volume,
velocity, and variety. Many studies address volume or velocity, while fewer
studies concern the variety. Metric spaces are ideal for addressing variety
because they can accommodate any data as long as it can be equipped with a
distance notion that satisfies the triangle inequality. To accelerate search in
metric spaces, a collection of indexing techniques for metric data have been
proposed. However, existing surveys offer limited coverage, and a comprehensive
empirical study exists has yet to be reported. We offer a comprehensive survey
of existing metric indexes that support exact similarity search: we summarize
existing partitioning, pruning, and validation techniques used by metric
indexes to support exact similarity search; we provide the time and space
complexity analyses of index construction; and we offer an empirical comparison
of their query processing performance. Empirical studies are important when
evaluating metric indexing performance, because performance can depend highly
on the effectiveness of available pruning and validation as well as on the data
distribution, which means that complexity analyses often offer limited
insights. This article aims at revealing strengths and weaknesses of different
indexing techniques to offer guidance on selecting an appropriate indexing
technique for a given setting, and to provide directions for future research on
metric indexing.
