Optimizing response time in large scale similarity searches

Abstract

Similarity search is a core operation found in several online multimedia services. These services have to handle very large databases, while, at the same time, they must min imize the query response times observed by users. This is especially complex because those services deal with fluctuating query workloads (rates). Consequently, they must adapt at run-time to minimize the response times as the load varies. In this dissertation, we address the aforementioned challenges with a distributed memory parallelization of the product quantization nearest neighbor search, also known as IVFADC, for hybrid CPU-GPU machines. Our parallel IVFADC also implements an out-of-core scheme to use the GPU for databases in which the index does not fit in its memory, which is crucial for searching in very large databases. The careful use of CPU and GPU with work-stealing led to an average reduction of the response time of 1.6× as com pared to using the GPU only. Also, our approach to adapt the system to fluctuating loads, called Dynamic Query Processing Policy (DQPP), attained an average response time reduction of 7× vs. the greedy policy. Finally, in all settings, the system has been shown to attain high query processing rates and near-linear scalability. We have executed our system in an environment with up to 256 NVIDIA V100 GPUs and a database of 256 billion SIFT features vectors