CRANBERRY: Memory-Effective Search in 100M High-Dimensional CLIP Vectors

TY - GEN

T1 - CRANBERRY: Memory-Effective Search in 100M High-Dimensional CLIP Vectors

AU - Mic, Vladimir

AU - Sedmidubsky, Jan

AU - Zezula, Pavel

N1 - Conference code: 16

PY - 2023

Y1 - 2023

N2 - Recent advances in cross-modal multimedia data analysis necessarily require efficient similarity search on the scales of hundreds of millions of high-dimensional vectors. We address this task by proposing the CRANBERRY algorithm that specifically combines and tunes several existing similarity search strategies. In particular, the algorithm: (1) employs the Voronoi partitioning to obtain a query-relevant candidate set in constant time, (2) applies filtering techniques to prune the obtained candidates significantly, and (3) re-rank the retained candidate vectors with respect to the query vector. Applied to the dataset of 100 million 768-dimensional vectors, the algorithm evaluates 10NN queries with 90\,\% recall and query latency of 1.2\,s on average, all with a throughput of 15 queries per second on a server with 56 core-CPU, and 4.7 q/sec. on a PC.

AB - Recent advances in cross-modal multimedia data analysis necessarily require efficient similarity search on the scales of hundreds of millions of high-dimensional vectors. We address this task by proposing the CRANBERRY algorithm that specifically combines and tunes several existing similarity search strategies. In particular, the algorithm: (1) employs the Voronoi partitioning to obtain a query-relevant candidate set in constant time, (2) applies filtering techniques to prune the obtained candidates significantly, and (3) re-rank the retained candidate vectors with respect to the query vector. Applied to the dataset of 100 million 768-dimensional vectors, the algorithm evaluates 10NN queries with 90\,\% recall and query latency of 1.2\,s on average, all with a throughput of 15 queries per second on a server with 56 core-CPU, and 4.7 q/sec. on a PC.

KW - approximate similarity searching

KW - high-dimensional data

KW - indexing

KW - filtering

KW - LAION dataset

UR - http://www.scopus.com/inward/record.url?scp=85177197812&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-46994-7_26

DO - 10.1007/978-3-031-46994-7_26

M3 - Article in proceedings

SN - 978-3-031-46993-0

T3 - Lecture Notes in Computer Science

SP - 300

EP - 308

BT - Similarity Search and Applications - 16th International Conference, SISAP 2023, Proceedings

A2 - Pedreira, Oscar

A2 - Estivill-Castro, Vladimir

PB - Springer

CY - Cham

T2 - 16th International Conference on Similarity Search and Applications

Y2 - 9 October 2023 through 11 October 2023

ER -