A Comprehensive List of Similarity Search Algorithms

Similarity search algorithms serve the purpose of identifying items within a dataset that exhibit resemblance to a given query item. These algorithms find application in diverse domains, including information retrieval, recommendation systems, and data mining. Importantly, similarity search is not constrained to text data; it extends its utility to various data types, encompassing numerical data, images, audio, and beyond. The critical aspect is the establishment of a pertinent similarity measure tailored to the specific data domain.

Here’s a comprehensive list of similarity search algorithms organized by category.

Exact Search Algorithms

Exact search algorithms are designed to find exact matches within a dataset. These algorithms find application in a wide range of domains, from basic data structures used in programming to advanced text processing and database management systems.

Linear Search: Linear search is used in many scenarios where a simple, straightforward search is required. One common use case is searching for a specific item in an unsorted list or array.
Binary Search: Binary search is commonly used in ordered datasets, such as phonebooks or dictionaries. It’s also applied in computer science for efficient searching in sorted arrays.
Hash-Based Methods: Hash tables are used in various applications, including database indexing and dictionary implementations. They provide fast access to values based on their keys.
Bloom Filter: Bloom filters are used for membership testing in large datasets, like checking if a URL is part of a known set of malicious websites without storing the entire list.
Trie (Prefix Tree): Tries are often used in text processing applications, such as autocomplete in search engines or spell-checking systems.
Aho-Corasick Algorithm: Aho-Corasick is used in string matching, particularly in text processing applications like keyword searching and pattern recognition.
Suffix Array: Suffix arrays are used in bioinformatics for sequence alignment and string matching in genomic data.
Boyer-Moore Algorithm: Boyer-Moore is applied in text searching and is known for its efficiency in searching for patterns in large texts, such as in text editors and search engines.
Karp-Rabin Algorithm: Karp-Rabin or Rabin-Karp is used for pattern matching and string searching. It’s applied in plagiarism detection and finding similarities between documents. Useful in text editors and content processing systems.
Knuth-Morris-Pratt (KMP) Algorithm: KMP is widely used in text searching and string matching applications. It’s efficient for tasks like finding substrings in texts.
Sphinx Search: Sphinx Search is a full-text search engine that is commonly used in applications requiring fast and efficient search capabilities, like online forums and e-commerce platforms.
B-Trees and Variants: B-trees are widely used in database management systems to efficiently search, insert, and delete records. They are the basis for file systems and databases like PostgreSQL.
AVL Trees: AVL trees are used for self-balancing binary search, making them suitable for applications requiring ordered data retrieval, such as database indexing.
Splay Trees: Splay trees are employed in scenarios where frequently accessed elements should be moved to the root of the tree for faster access. Applications include cache management.
Radix Tree (Patricia Trie): Radix trees are used in IP routing tables, string matching, and dictionary storage, as they efficiently organize data for fast lookups.

Distance-Based Algorithms

Distance-based algorithms are used to measure the similarity or dissimilarity between data points in a given space, such as Euclidean space. These algorithms play a crucial role in a wide range of applications across various domains, including data analysis, information retrieval, machine learning, geospatial analysis, and more.

Euclidean Distance: Euclidean distance is widely used in various fields, including image processing for measuring color similarity, computer vision for object recognition, and geographic information systems for calculating distances between coordinates.
Manhattan Distance (L1 Norm): Manhattan distance is used in route planning and transportation, like finding the shortest path on a grid-based city map. It’s also employed in feature selection for machine learning.
Minkowski Distance: Minkowski distance, which generalizes both Euclidean and Manhattan distances, is applied in pattern recognition, image analysis, and clustering tasks.
Cosine Similarity: Cosine similarity is widely used in information retrieval and natural language processing, including text document similarity, recommendation systems, and search engine ranking.
Jaccard Similarity: Jaccard similarity is used for set-based data, such as document retrieval, plagiarism detection, and collaborative filtering in recommendation systems.
Hamming Distance: Hamming distance is used in error detection and correction codes, network security for comparing binary strings, and genomics for comparing DNA sequences.
Levenshtein Distance (Edit Distance): Levenshtein distance is applied in spell-checkers, string similarity for information retrieval, and data deduplication in databases.
Chebyshev Distance (L∞ Norm): Chebyshev distance is used in chessboard distance calculations, network delay measurements, and anomaly detection in time series data.
Mahalanobis Distance: Mahalanobis distance is used in multivariate statistics for clustering, classification, and outlier detection, such as in healthcare for disease detection.
Canberra Distance: Canberra distance is applied in ecological and biological studies for species diversity measurements, as well as text clustering for document similarity.
Bray-Curtis Dissimilarity: Bray-Curtis dissimilarity is used in ecological community analysis for measuring compositional dissimilarity between species, as well as in market basket analysis for shopping patterns.
Haversine Distance: Haversine distance is used in geographic information systems (GIS) for calculating distances between two points on the Earth’s surface, such as for location-based services.
Chi-Squared Distance: Chi-squared distance is applied in feature selection for machine learning, image analysis, and text classification for document similarity.
Earth Mover’s Distance (Wasserstein Distance): Earth Mover’s Distance is used in image retrieval, computer vision, and transportation logistics to measure the distance between two probability distributions.
Bhattacharyya Distance: Bhattacharyya distance is applied in statistics for measuring the similarity between probability distributions, image recognition, and document classification.

Approximate Search Algorithms

Approximate search algorithms are designed to find approximate matches or similarities in data, trading off some degree of accuracy for efficiency. These algorithms find application in a wide range of domains, including recommendation systems, content deduplication, image and video retrieval, data analytics, and more. They are particularly valuable when dealing with high-dimensional data or when fast retrieval is essential.

Locality-Sensitive Hashing (LSH): LSH is applied in near-duplicate document detection, image retrieval, and recommendation systems to efficiently identify similar items.
MinHash: MinHash is used in estimating Jaccard similarity between sets, making it valuable in recommendation engines, content deduplication, and genomics for comparing gene expression profiles.
SimHash: SimHash is employed in near-duplicate detection for web pages and documents, as well as in detecting spam content.
Random Projection: Random projection is used for dimensionality reduction in high-dimensional data, such as text document clustering and image retrieval.
Product Quantization: Product quantization is applied in large-scale image and video retrieval systems, content-based recommendation, and multimedia databases.
Annoy (Approximate Nearest Neighbors Oh Yeah): Annoy is used for finding approximate nearest neighbors in recommendation systems, natural language processing, and image retrieval.
Hierarchical Navigable Small-World (HNSW) Graphs: HNSW graphs are employed in approximate nearest neighbor search, enabling efficient search in high-dimensional spaces, often used in recommendation systems and data analytics.
Randomized Algorithms for Nearest Neighbors: Randomized algorithms are used in applications like image retrieval, recommendation systems, and anomaly detection for efficient similarity search.
KD-Tree and Variants: KD-Trees and their variants are used in multidimensional nearest neighbor search, such as in computer graphics, image processing, and data mining.
Cover Trees: Cover trees are applied in nearest neighbor search, clustering, and data analysis, including bioinformatics for protein structure matching.
Product Quantization for Nearest Neighbor Search: This technique is commonly used in content-based recommendation systems and image retrieval for approximate similarity search.
Collision-Sensitive Hashing: Collision-sensitive hashing is applied in image and video retrieval, large-scale content-based recommendation, and multimedia databases.
Semantic Hashing: Semantic hashing is used in text document retrieval, image search, and content recommendation systems for approximating document or image similarities.
Bloom Filters: Bloom filters are used for membership testing, often in applications like spell-checking, web caching, and network packet filtering.
T-digest: T-digest is used for approximate quantile and summary statistics estimation, particularly in data analytics, machine learning, and financial applications.
Random Forests and Approximate Nearest Neighbors: Random forests can be used to approximate nearest neighbor search in recommendation systems and content-based filtering.
Fast Library for Approximate Nearest Neighbors (FLANN): FLANN is applied in image recognition, machine learning, and recommendation systems to find approximate nearest neighbors efficiently.

Graph-Based Algorithms

Graph-based algorithms can be employed in similarity search when data can be represented as a graph or network. These algorithms are valuable for similarity search when dealing with data that can be represented as a graph or network structure. They can help identify nodes or entities that are similar based on their connections and characteristics within the graph.

Graph Matching Algorithms: Graph matching is used in chemical compound similarity search, where the goal is to find molecules with similar structures.
Graph Neural Networks (GNNs): GNNs are applied in social network analysis for finding users with similar behavior or interests.
Random Walk and Personalized PageRank: Random walks and personalized PageRank algorithms are used in recommendation systems to find items similar to a user’s past interactions.
Community Detection Algorithms (e.g., Louvain Modularity, Girvan-Newman): Community detection algorithms are used in social network analysis to identify groups of users with similar interests or relationships.
Link Prediction Algorithms: Link prediction algorithms are used in recommendation systems and network analysis to suggest connections or friendships between users.
Graph Edit Distance Algorithms: Graph edit distance is used in bioinformatics for comparing molecular structures and in image recognition for content-based image retrieval.
Graph Clustering Algorithms: Graph clustering is used in social network analysis and image segmentation to find groups of nodes with similar properties.
Spectral Graph Theory Algorithms: Spectral graph theory is applied in recommendation systems and image recognition for measuring the similarity between nodes in a graph.
Heterogeneous Graph Mining Algorithms: Heterogeneous graph mining is used in e-commerce recommendation systems to find products similar to what a user has viewed.
Graph-Based Document Similarity Algorithms: Graph-based document similarity methods can be used in text document retrieval and content recommendation.
Word Embedding and Graph Embedding: Word embedding and graph embedding techniques are used in natural language processing for finding semantically similar words or documents.
Graph Convolutional Networks (GCNs): GCNs are applied in recommendation systems and content recommendation to find similar items or users in a graph.
Hierarchical Navigable Small-World (HNSW) Graphs: HNSW graphs are used for approximate nearest neighbor search and recommendation systems.
Bipartite Graph Matching Algorithms: Bipartite graph matching is used in recommendation systems for matching users to products or job matching.
Max Flow and Min Cut Algorithms (e.g., Ford-Fulkerson, Edmonds-Karp): Max flow and min cut algorithms are applied in network flow optimization, such as in transportation networks and network design.

Text Search Algorithms

Text search algorithms are designed to find and retrieve specific pieces of text or documents from a collection based on user-defined queries. These algorithms play a vital role in information retrieval, natural language processing, and document management across a wide range of applications, including search engines, recommendation systems, content management, and more.

Keyword-Based Search: Keyword-based search is widely used in web search engines, document management systems, and databases for retrieving documents that contain specific keywords or phrases.
Inverted Index: Inverted indexes are used in search engines, web crawling, and content retrieval systems for efficient document lookup based on terms.
Term Frequency-Inverse Document Frequency (TF-IDF): TF-IDF is employed in information retrieval systems, document ranking, and text classification to measure the relevance of documents to a query.
Boolean Retrieval: Boolean retrieval is used in database systems, advanced search engines, and document retrieval for precise querying using logical operators (AND, OR, NOT).
Proximity Search: Proximity search is applied in legal document search, molecular biology, and linguistics to find documents where keywords are located close to each other.
Vector Space Model (VSM): VSM is used in information retrieval systems, document clustering, and recommendation systems for ranking documents based on their similarity to a query.
BM25 (Best Matching 25): BM25 is used in search engines, document retrieval, and content recommendation to rank documents by relevance to a query.
Okapi BM25: Okapi BM25 is applied in information retrieval systems for improved document ranking and relevance ranking.
BM25F (BM25 with Fields): BM25F is used in search engines and document retrieval systems where documents have multiple fields, and each field contributes differently to relevance.
Latent Semantic Analysis (LSA) and Latent Dirichlet Allocation (LDA): LSA and LDA are used in topic modeling, content recommendation, and document clustering.
Hamming Distance: Hamming distance is used in error detection and correction codes, network security for comparing binary strings, and genomics for comparing DNA sequences.
Levenshtein Distance (Edit Distance): Levenshtein distance is used in spell-checkers, data deduplication, and DNA sequence alignment.
Damerau-Levenshtein Distance: A string similarity metric that measures the minimum number of edit operations (insertions, deletions, substitutions, and transpositions of adjacent characters) required to transform one string into another. It is used in applications like spell-checking, data cleansing, and record linkage to quantify the similarity between two strings, allowing for the detection and correction of typographical errors and textual discrepancies in datasets and documents.
Jaro Similarity: Measures the similarity between two strings based on the number of common characters and the number of transpositions required to match the strings. It is commonly used in record linkage, data deduplication, and fuzzy string matching applications to identify and group similar strings, such as names or addresses, in databases and datasets.
Jaro-Winkler Similarity: An extension of the Jaro Similarity algorithm, which measures the similarity between two strings, taking into account the common characters and their positions. It is often used in record linkage and data cleansing to improve the accuracy of string matching, particularly for names and addresses, by giving more weight to the common prefix of the strings and penalizing longer string differences.
Smith-Waterman Similarity: A local sequence alignment algorithm used to find the optimal local alignment between two sequences, typically biological sequences like DNA, RNA, or proteins. It is widely used in bioinformatics for tasks such as identifying similar regions within sequences, detecting sequence similarities between genes or proteins, and searching for patterns or motifs within biological data.
Jaccard Similarity: Jaccard similarity is used in plagiarism detection, recommendation systems, and content similarity analysis.
Sorensen-Dice Similarity: Used to measure the similarity between two sets or lists of items based on the size of their intersection relative to their total size. It is commonly used in various fields, including information retrieval, document similarity analysis, and natural language processing, to compare the similarity between two sets, such as words in documents, tags in content, or features in data.
Tversky Similarity: Extends Jaccard and Dice coefficients by introducing parameters to control the sensitivity to common elements and differences between sets. It is used in various fields, including information retrieval, recommendation systems, and network analysis, to compare and measure the similarity between sets, such as user preferences, tags, or item associations, with tunable parameters that allow fine-grained control over the matching criteria.
Overlap Similarity: Measures the similarity between two sets by calculating the size of their intersection relative to the size of the smaller set, commonly used in information retrieval and text analysis to find common terms between documents or elements in datasets.
Cosine Similarity: Cosine similarity is widely used in search engines, document clustering, and recommendation systems to measure document similarity.
N-gram Matching: N-gram matching is applied in DNA sequence analysis, text plagiarism detection, and spelling correction.
Ratcliff-Obershelp Similarity: A string similarity metric that measures the similarity between two strings by identifying common substrings, often used in record linkage and data cleansing to match and group similar strings based on their shared substrings.
Longest Common Substring/Subsequent Similarity: measures the similarity between two strings by finding the longest contiguous substring or subsequence shared between them, frequently used in text comparison and plagiarism detection to identify common text segments and similarities between documents.
Semantic Search: Semantic search algorithms, including Word Embeddings and Sentence-BERT, are used in question-answering systems, content recommendation, and natural language understanding tasks.
K-Means Text Clustering: K-means text clustering is applied in content recommendation, topic modeling, and document categorization.
Soundex and Metaphone: Soundex and Metaphone are employed in name matching, phonetic search, and fuzzy name matching in genealogy databases.
Rabin-Karp Algorithm: Rabin-Karp or Karp-Rabin is used in search engines and string matching applications for finding substrings in texts.

Spatial Indexing Algorithms

Spatial indexing algorithms are used to efficiently organize and search for spatial data, such as geographic coordinates, 2D or 3D points, and other spatial objects. These algorithms are important for performing efficient similarity search in various domains, including geospatial analysis, computer graphics, recommendation systems, and multidimensional data analysis.

Quadtree: Quadtrees are used in geographic information systems (GIS) for efficient spatial data storage, map rendering, and collision detection in computer graphics.
Octree: Octrees are used in 3D computer graphics for voxel-based modeling, ray tracing, and terrain representation in GIS.
R-tree: R-trees are widely used in GIS for indexing geographic data, spatial databases for location-based services, and image retrieval based on spatial similarity.
R*-tree: R*-trees are used in spatial databases for efficient indexing of geographic data and querying nearest neighbors.
kd-Tree: kd-trees are used in ray tracing for computer graphics, nearest neighbor search in machine learning, and multidimensional indexing in databases.
Grid Index: Grid indexing is applied in geographic databases for point-in-polygon queries, as well as in climate modeling and spatial analytics.
Geohash: Geohash is used in location-based services, geospatial data storage, and real-time spatial data indexing for applications like ride-sharing and geofencing.
Hilbert Curve Indexing: Hilbert curve indexing is applied in geographic information systems for map compression and efficient spatial query processing.
MVR-tree (Minimum Volume R-tree): MVR-trees are used in spatial databases and GIS for efficient storage and retrieval of spatial data, such as regions and polygons.
BVH (Bounding Volume Hierarchy): BVHs are used in computer graphics for ray tracing, collision detection, and rendering of complex 3D scenes.
X-tree: X-trees are used in spatial databases and geographic information systems for efficient query processing of spatial data.
Z-order Curve Indexing: Z-order curve indexing is applied in geographic databases, image retrieval, and map rendering for efficient storage and query processing.
ST-tree (Space-Time Tree): ST-trees are used in spatiotemporal databases for indexing and querying data with both spatial and temporal attributes, such as tracking moving objects.
Voronoi Diagram:mVoronoi diagrams are used in GIS, computational geometry, and facility location analysis to determine proximity relationships and optimal locations.
Geospatial Voronoi Diagrams: Geospatial Voronoi diagrams are used in location-based services, territorial analysis, and facility planning.
M-tree: M-trees are used in similarity search for multimedia data, such as image retrieval and content-based recommendation systems.
BSP (Binary Space Partitioning): BSP trees are used in computer graphics for efficient rendering and spatial partitioning of 3D scenes.

Machine Learning-Based Algorithms

Machine learning-based algorithms can be used for similarity search in various applications where finding similar items or data points is important. These algorithms are valuable in various domains, including recommendation systems, content similarity analysis, image retrieval, and content matching.

Siamese Networks: Siamese networks are used for face recognition in security systems and image similarity search in e-commerce.
Triplet Networks: Triplet networks are applied in image retrieval systems, where a query image is used to find similar images in a database.
Contrastive Learning: Contrastive learning is used for content-based recommendation systems to find items similar to what a user has interacted with.
Cosine Similarity and Vector Space Models: Cosine similarity and vector space models are widely used in text retrieval systems, such as search engines, to find documents similar to a query.
Siamese Recurrent Neural Networks (RNNs): Siamese RNNs are used in speech recognition for identifying similar spoken phrases or voice patterns.
Sequence-to-Sequence Models (Seq2Seq): Seq2Seq models are used in machine translation to find translations similar to a source sentence.
Content-Based Filtering: Content-based filtering is applied in recommendation systems to find items (e.g., movies, products) similar to what a user has previously shown interest in.
Collaborative Filtering: Collaborative filtering is used in recommendation systems to find items that similar users have liked or interacted with.
Matrix Factorization: Matrix factorization is applied in recommendation systems for finding similar users or items by decomposing user-item interaction matrices.
Neural Collaborative Filtering (NCF): NCF is used in recommendation systems to find similar users or items based on neural network models.
Graph-Based Models: Graph-based models are applied in social network analysis for finding similar nodes or users based on network structure and interactions.
Anomaly Detection Models (Isolation Forests, One-Class SVM): Anomaly detection models are used to identify outliers or unusual data points, such as fraudulent transactions in financial systems or defective products in manufacturing.
Autoencoders: Autoencoders are applied in content-based recommendation systems to find items similar to those a user has interacted with, as well as for data compression.
Word Embeddings (Word2Vec, GloVe): Word embeddings are used in natural language processing for finding semantically similar words or phrases, as well as in document similarity analysis.
Doc2Vec: Doc2Vec is applied in document similarity analysis, text classification, and recommendation systems to find similar documents or content.
Word Movers’ Distance (WMD): WMD is used in natural language processing for text document similarity and recommendation systems.
Sentence-BERT: Sentence-BERT is used for sentence and document similarity in natural language processing and content recommendation.
Product Quantization for Nearest Neighbor Search: Product quantization is applied in image retrieval systems to find similar images based on visual features.