Indexing Metric Spaces For Exact Similarity Search

Abstract

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

Stats

• citations27
• S2 citations—
• github stars0
• HF likes0
• heat score10.85
• arxiv keychen2020indexing

Related papers

• Hilbert Exclusion: Improved Metric Search Through Finite Isometric Embeddings (2016)10.07
• Unconventional Application Of K-means For Distributed Approximate Similarity Search (2022)5.84
• Exact Trajectory Similarity Search With N-tree: An Efficient Metric Index For Knn And Range Queries (2024)0.00
• Accurate And Fast Retrieval For Complex Non-metric Data Via Neighborhood Graphs (2019)0.00
• Return Of The Lernaean Hydra: Experimental Evaluation Of Data Series Approximate Similarity Search (2020)0.00
• Climber++: Pivot-based Approximate Similarity Search Over Big Data Series (2024)2.26
• A New Family Of Near-metrics For Universal Similarity (2017)0.00
• Improving Distributed Similarity Join In Metric Space With Error-bounded Sampling (2019)0.00