Tese

Processamento eficiente de consultas em sistemas de busca

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 si...

ver descrição completa

Autor principal: Daoud, Caio Moura
Outros Autores: http://lattes.cnpq.br/8569893814198940
Grau: Tese
Idioma: por
Publicado em: Universidade Federal do Amazonas 2017
Assuntos:
Processamento de consultas
Recuperação de informação
Máquina de Busca
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
Acesso em linha: http://tede.ufam.edu.br/handle/tede/5581
id oai:https:--tede.ufam.edu.br-handle-:tede-5581
recordtype dspace
spelling oai:https:--tede.ufam.edu.br-handle-:tede-55812017-03-15T05:04:59Z Processamento eficiente de consultas em sistemas de busca Daoud, Caio Moura Moura, Edleno Silva de http://lattes.cnpq.br/8569893814198940 http://lattes.cnpq.br/4737852130924504 Processamento de consultas Recuperação de informação Máquina de Busca CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO 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. Search systems have been one of the main forms of locating and retrieving information in digital environments in recent decades. They are present in a large number of applications, such as web search engines and e-commerce systems. Users of these systems more often than not have very specific information needs, only being satisfied with a few, highly relevant results. Due to this behavior, part of the recent research effort related to search systems aims to reduce computational costs to compute the top results of queries, which are the ones usually presented to most users. In this thesis, we study the problem of computing the top k results of a ranking in search engines. We present two novel document-at-a-time algorithms for fast computing of top-k query results in search systems, named as Block Max WAND with Candidate Selection and Preserving Top-K Results (BMW-CSP) and Waves. Both algorithms use multi-tier indexes for reducing the computational time required for processing queries. BMW-CSP is an extension of BMW-CS, a method previously proposed in the literature. Although very efficient, BMW-CS does not guarantee the preservation of the top-k results for a given query. Algorithms that do not preserve the top results may reduce the quality of ranking results in search systems. BMW-CSP extends BMW-CS to ensure that the top-k results will have their rankings preserved. In the experiments we performed for computing the top-10 results, the final average time required for processing queries with BMW-CSP was lesser than the ones required by the baselines adopted. As with BMWCS, the price paid by BMW-CSP, when compared to other document-at-a-time methods, is extra memory required to store partial scores of documents. Further studying the problem of query processing, we then proposed Waves. It performs successive tentative evaluations of results which we call waves. Each wave traverses the index, starting from a specific tier level i. Each wave i may insert only those documents that occur in that tier level into the answer. After processing a wave, the alv gorithm checks whether the answer achieved might be changed by successive waves or not. A new wave is started only if it has a chance of changing the top-k scores. We show through experiments that such lazy query processing strategy results in smaller query processing times when compared to previous approaches proposed in the literature. When compared to BMW-CSP, Waves presents the advantage of not requiring extra memory to store partial scores. We present experiments to compare the performance of Waves to BMW-CSP and to other state-of-the-art document-at-a-time query processing methods that preserve top-k results. These experiments indicate that the method can be an effective alternative algorithm for computing top-k results. CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior 2017-03-14T13:42:20Z 2016-12-02 Tese DAOUD, Caio Moura. Processamento eficiente de consultas em sistemas de busca. 2016. 80 f. Tese (Doutorado em Informática) - Universidade Federal do Amazonas, Manaus, 2016. http://tede.ufam.edu.br/handle/tede/5581 por Acesso Aberto http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Universidade Federal do Amazonas Instituto de Computação Brasil UFAM Programa de Pós-graduação em Informática
institution TEDE - Universidade Federal do Amazonas
collection TEDE-UFAM
language por
topic Processamento de consultas
Recuperação de informação
Máquina de Busca
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
spellingShingle Processamento de consultas
Recuperação de informação
Máquina de Busca
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
Daoud, Caio Moura
Processamento eficiente de consultas em sistemas de busca
topic_facet Processamento de consultas
Recuperação de informação
Máquina de Busca
CIÊNCIAS EXATAS E DA TERRA: CIÊNCIA DA COMPUTAÇÃO
description 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.
author_additional Moura, Edleno Silva de
author_additionalStr Moura, Edleno Silva de
format Tese
author Daoud, Caio Moura
author2 http://lattes.cnpq.br/8569893814198940
author2Str http://lattes.cnpq.br/8569893814198940
title Processamento eficiente de consultas em sistemas de busca
title_short Processamento eficiente de consultas em sistemas de busca
title_full Processamento eficiente de consultas em sistemas de busca
title_fullStr Processamento eficiente de consultas em sistemas de busca
title_full_unstemmed Processamento eficiente de consultas em sistemas de busca
title_sort processamento eficiente de consultas em sistemas de busca
publisher Universidade Federal do Amazonas
publishDate 2017
url http://tede.ufam.edu.br/handle/tede/5581
_version_ 1831969484573769728
score 11.753735

Registros relacionados