[pt] O crescimento explosivo e a acessibilidade generalizada da World Wide Web (WWW) levaram ao aumento da atividade de pesquisa na área da recuperação de informação para páginas Web. A WWW é um rico e imenso ambiente em que as páginas se assemelham a uma comunidade grande de elementos conectada através de hiperlinks em razão da semelhança entre o conteúdo das páginas, a popularidade da página, a autoridade sobre o assunto e assim por diante, sabendo-se que, em verdade, quando um autor de uma página a vincula à outra, está concebendo-a como importante para si. Por isso, a estrutura de hiperlink da WWW é conhecida por melhorar significativamente o desempenho das pesquisas para além do uso de estatísticas de distribuição simples de texto. Nesse sentido, a abordagem Hyperlink Induced Topic Search (HITS) introduz duas categorias básicas de páginas Web, hubs e autoridades, que revelam algumas informações semânticas ocultas a partir da estrutura de hiperlink. Em 2005, fizemos uma primeira extensão do HITS, denominada de Extended Hyperlink Induced Topic Search (XHITS), que inseriu duas novas categorias de páginas Web, quais sejam, novidades e portais. Na presente tese, revisamos o XHITS, transformando-o em uma generalização do HITS, ampliando o modelo de duas categorias para várias e apresentando um algoritmo eficiente de aprendizagem de máquina para calibrar o modelo proposto valendo-se de múltiplas categorias latentes. As descobertas aqui expostas indicam que a nova abordagem de aprendizagem fornece um modelo XHITS mais preciso. É importante registrar, por fim, que os experimentos realizados com a coleção ClueWeb09 25TB de páginas da WWW, baixadas em 2009, mostram que o XHITS pode melhorar significativamente a eficácia da pesquisa Web e produzir resultados comparáveis aos do TREC 2009/2010 Web Track, colocando-o na sexta posição, conforme os resultados publicados. / [en] The rapid growth and generalized accessibility of the World Wide Web (WWW) have led to an increase in research in the field of the information retrieval for Web pages. The WWW is an immense and prodigious environment in which Web pages resemble a huge community of elements. These elements are connected via hyperlinks on the basis of similarity between the content of the pages, the popularity of a given page, the extent to which the information provided is authoritative in relation to a given field etc. In fact, when the author of a Web page links it to another, s/he is acknowledging the importance of the linked page to his/her information. As such the hyperlink structure of the WWW significantly improves research performance beyond the use of simple text distribution statistics. To this effect, the HITS approach introduces two basic categories of Web pages, hubs and authorities which uncover certain hidden semantic information using the hyperlink structure. In 2005, we made a first extension of HITS, called Extended Hyperlink Induced Topic Search (XHITS), which inserted two new categories of Web pages, which are novelties and portals. In this thesis, we revised the XHITS, transforming it into a generalization of HITS, broadening the model from two categories to various and presenting an efficient machine learning algorithm to calibrate the proposed model using multiple latent categories. The findings we set out here indicate that the new learning approach provides a more precise XHITS model. It is important to note, in closing, that experiments with the ClueWeb09 25TB collection of Web pages, downloaded in 2009, demonstrated that the XHITS is capable of significantly improving Web research efficiency and producing results comparable to those of the TREC 2009/2010 Web Track.

[pt] Uma máquina de busca precisa constantemente revisitar páginas Web para manter seu repositório local atualizado. Uma política de revisitação deve ser empregada para construir um escalonamento de revisitações que mantenha o repositório o mais atualizado possível utilizando os recursos disponíveis. Para evitar sobrecarga de servidores Web, a política de revisitação deve respeitar um tempo mínimo entre requisições consecutivas a um mesmo servidor. Esta regra é chamada restrição de politeness. Devido ao porte do problema, consideramos que uma política de revisitação é eficiente se o tempo médio para escalonar uma revisitação é sublinear no número de páginas do repositório. Neste sentido, quando a restrição de politeness é considerada, não conhecemos política eficiente com garantia teórica de qualidade. Nesta pesquisa investigamos três políticas eficientes que respeitam a restrição de politeness, chamadas MERGE, RANDOM e DELAYED. Fornecemos fatores de aproximação para o nível de atualização do repositório quando empregamos as política MERGE ou RANDOM. Demonstramos que 0,77 é um limite inferior para este fator de aproximação quando empregamos a política RANDOM, e apresentamos uma conjectura de que 0,927 é um limite inferior para este fator de aproximação quando empregamos a política MERGE. As políticas também são avaliadas através da simulação da execução destas políticas para manter o nível de atualização de um repositório contendo 14,5 milhões de páginas Web. Um repositório contendo artigos da Wikipedia também é utilizado nos experimentos, onde podemos observar que a política MERGE apresenta melhores resultados que uma estratégia gulosa natural para este repositório. A principal conclusão desta pesquisa é que existem políticas simples e eficientes para o problema de revisitação de páginas Web, que perdem pouco em termos do nível de atualização do repositório mesmo quando consideramos a restrição de politeness. / [en] A search engine needs to continuously revisit web pages in order to keep its local repository up-to-date. A page revisiting schedule must be defined to keep the repository up-to-date using the available resources. In order to avoid web server overload, the revisiting policy must respect a minimum amount of time between consecutive requests to the same server. This rule is called politeness constraint. Due to the large number of web pages, we consider that a revisiting policy is efficient when the mean time to schedule a revisit is sublinear on the number of pages in the repository. Therefore, when the politeness constraint is considered, there are no existing efficient policies with theoretical quality guarantees. We investigate three efficient policies that respect the politeness constraint, called MERGE, RANDOM and DELAYED. We provide approximation factors for the repository’s up-to-date level for the MERGE and RANDOM policies. Based on these approximation factors, we devise a 0.77 lower bound for the approximation factor provided by the RANDOM policy and we present a conjecture that 0.927 is a lower bound for the approximation factor provided by the MERGE policy. We evaluate these policies through simulation experiments which try to keep a repository with 14.5 million web pages up-to-date. Additional experiments based on a repository with Wikipedia’s articles concluded that the MERGE policy provides better results than a natural greedy strategy. The main conclusion of this research is that there are simple and efficient policies that can be applied to this problem, even when the politeness constraint must be respected, resulting in a small loss of repository’s up-to-date level.

[pt] Links patrocinados são aqueles que aparecem em destaque nos resultados de pesquisas em máquinas de busca na Internet e são grande fonte de receita para seus provedores. Para os anunciantes, que fazem ofertas por palavras-chave para aparecerem em destaque nas consultas dos usuários, são uma oportunidade de divulgação da marca, conquista e manutenção de clientes. Um dos desafios das máquinas de busca neste modelo de negócio é selecionar os anunciantes que serão exibidos a cada consulta de modo a maximizar sua receita em determinado período. Este é um problema tipicamente online, onde a cada consulta é tomada uma decisão sem o conhecimento prévio das próximas consultas. Após uma decisão ser tomada, esta não pode mais ser alterada. Nesta dissertação avaliamos experimentalmente algoritmos propostos na literatura para solução deste problema, comparando-os à solução ótima offline, em simulações com dados sintéticos. Supondo que o conjunto das consultas diárias obedeça a uma determinada distribuição, propomos dois algoritmos baseados em informações estocásticas que são avaliados nos mesmos cenários que os outros algoritmos. / [en] Sponsored links are those that appear highlighted at Internet search engine results. They are responsible for a large amount of their providers’ revenue. To advertisers, that place bids for keywords in large auctions at Internet, these links are the opportunity of brand exposing and achieving more clients. To search engine companies, one of the main challenges in this business model is selecting which advertisers should be allocated to each new query to maximize their total revenue in the end of the day. This is a typical online problem, where for each query is taken a decision without previous knowledge of future queries. Once the decision is taken, it can not be modified anymore. In this work, using synthetically generated data, we do experimental evaluation of three algorithms proposed in the literature for this problem and compare their results with the optimal offline solution. Considering that daily query set obeys some well known distribution, we propose two algorithms based on stochastic information, those are evaluated in the same scenarios of the others.

[pt] A extração de entidades de páginas web é comumente utilizada para melhorar a qualidade de muitas tarefas realizadas por máquinas de busca como detecção de páginas duplicadas e ranking. Essa tarefa se torna ainda mais relevante devido ao crescente volume de informação da internet com as quais as máquinas de busca precisam lidar. Existem diversos algoritmos para detecção de conteúdo na literatura, alguns orientados a sites e outros que utilizam uma abordagem mais local e são chamados de algoritmos orientados a páginas. Os algoritmos orientados a sites utilizam várias páginas de um mesmo site para criar um modelo que detecta o conteúdo relevante da página. Os algoritmos orientados a páginas detectam conteúdo avaliando as características de cada página, sem comparar com outras páginas. Neste trabalho apresentamos um algoritmo, chamado NCE ( News Content Extractor), orientado a página e que se propõe a realizar extração de entidades em páginas de notícias. Ele utiliza atributos de uma árvore DOM para localizar determinadas entidades de uma página de notícia, mais especificamente, o título e o corpo da notícia. Algumas métricas são apresentadas e utilizadas para aferir a qualidade do NCE. Quando comparado com outro método baseado em página e que utiliza atributos visuais, o NCE se mostrou superior tanto em relação à qualidade de extração quanto no que diz respeito ao tempo de execução. / [en] The entity extraction of web pages is commonly used to enhance the quality of tasks performed by search engines, like duplicate pages and ranking. The relevance of entity extraction is crucial due to the fact that search engines have to deal with fast growning volume of information on the web. There are many algorithms that detect entities in the literature, some using site level strategy and others using page level strategy. The site level strategy uses many pages from the same site to create a model that extracts templates. The page level strategy creates a model to extract templates according to features of the page. Here we present an algorithm, called NCE (News Content Extractor), that uses a page level strategy and its objective is to perform entity extraction on news pages. It uses features from a DOM tree to search for certain entities, namely, the news title and news body. Some measures are presented and used to evaluate how good NCE is. When we compare NCE to a page level algorithm that uses visual features, NCE shows better execution time and extraction quality.