Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-03-14T13:41:39Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Caio M. Daoud.pdf: 14164794 bytes, checksum: ad296e0b97a339ac0b0b30ff6da7e344 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-03-14T13:41:58Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Caio M. Daoud.pdf: 14164794 bytes, checksum: ad296e0b97a339ac0b0b30ff6da7e344 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-03-14T13:42:20Z (GMT) No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Caio M. Daoud.pdf: 14164794 bytes, checksum: ad296e0b97a339ac0b0b30ff6da7e344 (MD5) / Made available in DSpace on 2017-03-14T13:42:20Z (GMT). No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertação - Caio M. Daoud.pdf: 14164794 bytes, checksum: ad296e0b97a339ac0b0b30ff6da7e344 (MD5)
Previous issue date: 2016-12-02 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / 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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:http://localhost:tede/5581 |
| Date | 02 December 2016 |
| Creators | Daoud, Caio Moura |
| Contributors | Moura, Edleno Silva de |
| Publisher | Universidade Federal do Amazonas, Programa de Pós-graduação em Informática, UFAM, Brasil, Instituto de Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFAM, instname:Universidade Federal do Amazonas, instacron:UFAM |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -312656415484870643, 600, 500, 1052477850274827528 |
Page generated in 0.0133 seconds