Approximate Similarity Joins over Dense Vector Embeddings - Santana, Douglas Rolins de; Ribeiro, Leonardo Andrade (Anais do Simpósio Brasileiro de Banco de Dados (SBBD), 2023)
We consider the problem of efficiently answering similarity join queries over vector data generated by machine learning models. Owing to the high dimensionality and density of such vectors, approximate solutions are prevalent for dealing with large datasets. In this context, we investigate how to evaluate similarity joins using the Hierarchical Navigable Small World (HNSW), a state-of-the-art, graph-based index designed for approximate knearest neighbor (kNN) queries. We explore the design space of possible solutions, ranging from alternatives on top of HNSW to deeper integration of similarity join processing into this structure. Experimental results show that our proposal achieves substantial speedups with negligible accuracy loss.