Busca no site da UFMG

Nº 1572 - Ano 33
9.4.2007

Tese do DCC estuda mecanismos de busca na Web

Ana Rita Araújo

As ferramentas de busca são hoje instrumentos indispensáveis aos usuários da Internet, pois atuam como espécie de guia entre os nada menos que 20 bilhões de documentos atualmente distribuídos na rede mundial de computadores. Para as empresas de tecnologia de busca na Web, o grande desafio é desenvolver sistemas que consigam manter a qualidade e a rapidez das respostas, num cenário em que crescem tanto o número de consultas quanto o universo de documentos a ser analisado.

Mecanismo de buscaEm tese de doutorado defendida no final de fevereiro, no Programa de Pós-Graduação em Ciência da Computação da UFMG, a estudante Claudine Gonçalves desenvolveu um arcabouço para o projeto e análise da infra-estrutura de mecanismos de busca na Web. “Nosso objetivo é ter uma ferramenta simples e razoavelmente precisa que possa responder questões de planejamento de capacidade”, afirma a pesquisadora, ao lembrar que seu estudo é útil para estudantes de Ciência da Computação, especialmente no caso daqueles que estão se especializando em recuperação de informação e em análise e modelagem de desempenho de sistemas de computação, assim como para empresas de tecnologia de busca.

Segundo a autora, os mecanismos de busca requerem uma enorme quantidade de recursos computacionais para lidar com o tráfego de consultas, freqüentemente caracterizado por altos picos de acesso. “O problema é ainda mais desafiador se considerarmos que o número de documentos disponíveis na Web cresce constantemente”, diz a pesquisadora. Para lidar com tais exigências, os sistemas modernos de busca adotam um grupo de máquinas, ou cluster, composto por um conjunto de servidores de índice e uma máquina central, ou broker, que se comunica com os vários servidores de índice.

Arquitetura

A coleção de documentos é dividida entre os servidores de índice, de modo que cada um armazena parte da coleção e índice próprio. “Esta arquitetura, denominada particionamento por documento, é geralmente preferida porque simplifica a manutenção e a geração do índice”, comenta Claudine Gonçalves. Outra vantagem é que falhas em um servidor de índice não impedem que qualquer consulta seja respondida, embora o conjunto final de respostas possa não conter todos os documentos relevantes da coleção. Nesta arquitetura, o broker envia a consulta de um usuário para todos os servidores de índice e cada um deles retorna seus dez documentos mais relevantes. Com tais dados, o broker executa uma mesclagem em memória para determinar as dez respostas finais a serem enviadas para o usuário.

Na arquitetura caracterizada por particionamento por documento, a coleção inteira de arquivos é distribuída entre os servidores de índice de forma balanceada, de modo que cada um manipule quantidade similar de dados para processar certa consulta. Como conseqüência, espera-se que os tempos de serviço nos servidores de índice também sejam aproximadamente semelhantes. “Verificamos que este cenário idealizado de tempos de serviço balanceados nos servidores de índice com volumes de dados similares não é encontrado na prática”, afirma a pesquisadora. Esta é uma contribuição importante de seu estudo, porque contradiz a suposição usual de tempos de serviço balanceados adotada pelos modelos teóricos anteriores encontrados na literatura. Além disso, a pesquisadora identificou e analisou as principais fontes de desbalanceamento, ou diferença, nos tempos de serviço entre os servidores de índice que participam do processamento de uma dada consulta: o uso do cache do disco, o tamanho da memória principal nos servidores de índice e o número de servidores no cluster.

Capacidade

Outra importante contribuição da tese de Claudine foi a proposta de modelo de planejamento de capacidade para mecanismos de busca na Web, que considera o desbalanceamento nos tempos de serviço das consultas entre os servidores de índice. O modelo proposto pode ser usado para responder a questões importantes de planejamento de capacidade, tais como o limite superior para o tempo médio de resposta de uma consulta; tipo de otimização nos recursos da máquina capaz de produzir uma redução no tempo médio de resposta; e o número mínimo de réplicas do cluster capazes de garantir que o tempo de resposta de uma consulta num período de pico não excederá o limite definido pelo gerente do sistema de busca.

A utilidade do modelo para predizer o tempo de resposta de uma consulta foi ilustrada num cenário realístico, que considera coleção de 20 bilhões de documentos distribuída através de dois mil servidores de índice. “Em nosso exemplo, mostramos que o gerente de um mecanismo de busca pode rapidamente alcançar predições para o limite superior do tempo médio de resposta de uma consulta sem ter de executar quaisquer experimentos reais”, diz Claudine Gonçalves.

Tese: Projeto e análise de sistemas de busca na Web
Autora: Claudine Santos Badue Gonçalves
Defesa: 27 de fevereiro de 2007, no Programa de Pós-Graduação em Ciência da Computação (ICEx-UFMG)
Orientador: Professor Nivio Ziviani (DCC - UFMG)
Co-orientador: Professor Ricardo Baeza-Yates (Universitat Pompeu Fabra, Barcelona, Espanha)