Optimizing response time in large scale similarity searches

Detalhes bibliográficos
Ano de defesa: 2020
Autor(a) principal: Rafael Martins de Souza
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Universidade Federal de Minas Gerais
Brasil
ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
Programa de Pós-Graduação em Ciência da Computação
UFMG
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/1843/38399
Resumo: 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