Optimizing response time in large scale similarity searches
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Otimizando tempo de resposta em buscas por similaridade em larga escala
Primeiro orientador
Membros da banca
Wagner Meira Júnior
William Robson Schwartz
Eduardo Alves do Valle Junior
William Robson Schwartz
Eduardo Alves do Valle Junior
Resumo
Busca por similaridade é uma operação fundamental encontrada em serviços de multimídia online. Estes serviços precisam lidar com bases de dados muito grandes, enquanto, ao mesmo tempo, eles tem que minimizar o tempo de resposta observado por
seus usuários. Isto é especialmente complexo porque esses serviços lidam com taxa
de consultas variáveis. Consequentemente, eles precisam se adaptar durante o tempo
de execução para minimizar o tempo de resposta a medida que a taxa de consultas
varia. Nesta dissertação, nós abordamos os desafios mencionados anteriormente com
a paralelização, em memória distribuída, da busca por vizinhos mais próximos com
quantização em produto, também conhecida como IVFADC, para máquinas híbridas
com CPU e GPU. Nosso IVFADC paralelo também implementa um mecanismo de
execução out-of-core, para permitir que a GPU processe bases de dados que não cabem
na memória, o que é crucial para realizar buscas em base de dados muito grandes. O
uso de CPU com GPU com roubo de trabalho gerou uma redução média no tempo
de resposta de 1.6× quando comparado a usar a GPU somente. Inclusive, a nossa
abordagem para adaptar o sistema para taxa de consultas variáveis, chamada de Dynamic Query Processing Policy (DQPP), alcançou uma redução média no tempo de
resposta de 7× vs a política gulosa. Finalmente, em todas as configurações, o sistema
se mostrou capaz de alcançar altas taxas de processamento de consultas e escalabilidade quase linear. Nós executamos o sistema em um ambiente com até 256 NVIDIA
V100 GPUs, e uma base de dados de 256 bilhões de vetores de características SIFT
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
Assunto
Computação – Teses, Computação distribuída – Teses, Busca por similaridade – Teses
Palavras-chave
Computation, Distributed Systems, Similarity Search