Efficient approximate search for sets of lineage vectors
Michael Leybovich, Oded Shmueli · 2022
One can approximate the lineage of a Database (DB) tuple using a small set of low dimensional vectors. To identify actual lineage tuples using these vector sets, given a set of vectors (of the target tuple), one needs to locate "close" sets of vectors associated with the lineage tuples. We first 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. The proposed similarity measure is intuitive and permutation invariant. 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 k-closest sets Bi1 ..., Bik that maximize 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. We utilize the mathematical properties of the cosine distance measure to transform the set-set search problem into a vector-vector search problem. However, this abovementioned transformation cannot handle the Euclidean-based version of the similarity measure. For this version, we devise a more elaborate transformation. For this latter transformation, we present algorithms for the general case, with sets of differing cardinalities. The underlying idea in both of these transformations is encoding a set of vectors A via |A| "long" independent representative vectors. Then, we are able to transform the set-set search problem into the well-studied approximate (ordinary) vector search problem. For both cosine-based and Euclidean-based similarity measures, the proposed approximate search achieves significant performance gains over an optimized, exact search on vector sets.