# Efficient Approximate Search for Sets of Vectors

arXiv: https://arxiv.org/abs/2107.06817 · HTML: https://mlsanity.com/paper/2107.06817/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 14 Jul 2021.

## Builds on (most cited first, 8 of 8)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Quantization based Fast Inner Product Search](https://mlsanity.com/paper/1509.01469/) (2015)
- [Enabling Cognitive Intelligence Queries in Relational Databases using Low-dimensional Word Embeddings](https://mlsanity.com/paper/1603.07185/) (2016)
- [Cognitive Database: A Step towards Endowing Relational Databases with Artificial Intelligence Capabilities](https://mlsanity.com/paper/1712.07199/) (2017)

## Built on by (most cited first, 1 of 1)

- [ML Based Lineage in Databases](https://mlsanity.com/paper/2109.06339/) (2021)

## Abstract (arXiv)

We consider a similarity measure between two sets A and B of vectors, that balances the average and maximum cosine distance between pairs of vectors, one from set A and one from set B. As a motivation for this measure, we present lineage tracking in a database. To practically realize this measure, we need an approximate search algorithm that given a set of vectors A and sets of vectors B1,...,Bn, the algorithm quickly locates the set Bi that maximizes the similarity measure. For the case where all sets are singleton sets, essentially each is a single vector, there are known efficient approximate search algorithms, e.g., approximated versions of tree search algorithms, locality-sensitive hashing (LSH), vector quantization (VQ) and proximity graph algorithms. In this work, we present approximate search algorithms for the general case. The underlying idea in these algorithms is encoding a set of vectors via a "long" single vector. The proposed approximate approach achieves significant performance gains over an optimized, exact search on vector sets.