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