Indexing Metric Spaces for Exact Similarity Search

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.

Automated summary

With the increasing digitization of processes, the amount of available data, known as big data, is exploding. Volume, velocity, and variety are the three main challenges in enabling value creation from big data. Metric spaces provide an ideal solution for addressing variety as they can incorporate any data equipped with a distance notion satisfying the triangle inequality. Indexing techniques for metric data have been proposed to accelerate search in metric spaces, yet the existing surveys are limited and a comprehensive empirical study is yet to be reported. This article aims to offer a comprehensive survey of existing metric indexes supporting exact similarity search, provide complexity analyses of index construction, and offer empirical comparison of query processing performance. The importance of empirical studies in evaluating metric indexing performance is highlighted, as performance can depend heavily on pruning and validation effectiveness and data distribution.