Processamento eficiente de consultas em sistemas de busca

• Ano de defesa: 2016
• Autor(a) principal: Daoud, Caio Moura
• Outros Autores: http://lattes.cnpq.br/8569893814198940
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Amazonas; Instituto de Computação; Brasil; UFAM; Programa de Pós-graduação em Informática
• Palavras-chave em Português: Processamento de consultas; Recuperação de informação; Máquina de Busca; CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
• Link de acesso: http://tede.ufam.edu.br/handle/tede/5581

Trabalhos na literatura propõem diferentes técnicas para processamento de consultas em sistemas de busca. Esses sistemas são capazes de buscar informação relevante dentro de grandes coleções de dados e estão entre as principais formas de se obter informações na Internet. A popularização desses sistemas, associada ao crescimento constante de dispositivos eletrônicos para armazenamento e produção de informação, impulsionam pesquisas não apenas em relação à qualidade da resposta final fornecida aos usuários mas também com relação à redução no tempo de processamento de consultas. O foco principal deste trabalho é o desenvolvimento de soluções que reduzam o tempo de processamento de consultas sem afetar a qualidade de respostas fornecidas por sistemas de busca. Como usuários tipicamente estão interessado apenas em um determinado número de respostas do topo do ranking, estudamos o cenário mais comum onde busca-se computar rapidamente apenas os k documentos de maior escore dentre os que atendem às consultas dos usuários. São propostos, implementados e avaliados dois novos métodos de processamento de consultas, o método Block Max WAND with Candidate Selection and Preserving Top- K Results (BMW-CSP) e o método Waves. Os dois métodos utilizam uma abordagem documento-a-documento e índices em multi-camadas como base para reduzir o tempo de processamento de consultas. O método BMW-CSP é uma extensão do método BMW-CS, um método proposto anteriormente na literatura. Apesar de muito eficiente, o BMW-CS apresenta a desvantagem de não garantir a corretude dos resultados do topo das respostas em sistemas de busca por poder descartar documentos que estariam originalmente entre as melhores respostas. O métodoBMW-CSP modifica oBMW-CS para resolver o problema, tornando-se um método que calcula corretamente o escore de todos os documentos. Tanto o método BMW-CS quanto o BMW-CSP apresentam como desvantagem a necessidade de utilizar memória extra para armazenar resultados parciais obtidos pelos métodos durante o processamento de consultas. Estudando mais a fundo o problema, propôs-se aqui um novo algoritmo que não requer tal expaço extra de armazenamento, o algoritmo Waves. O métodoWaves realiza passadas sucessivas pelas diversas camadas dos índices. Cada passagem foi denominada aqui de wave (onda em inglês), o que deu origem ao nome do método. Cada passagem sobre o índice é numerada e dada uma i-ésima passagem, ela processa o índice apenas da i-ésima camada em diante. Após cada passagem, o algoritmo faz uma verificação para saber se já se pode garantir que os k maiores escores de documentos já foram computados corretamente. Se houver garantia, o algoritmo para o processamento. Do contrário, o algoritmo executa uma nova passagem no índice até que o resultado correto seja matematicamente garantido. Os experimentos realizados com diferentes bases e cenários indicam que os dois novos métodos podem processar consultas até duas vezes mais rápido que os principais métodos propostos anteriormente na literatura.