Made available in DSpace on 2014-06-12T15:58:52Z (GMT). No. of bitstreams: 2 arquivo4736_1.pdf: 1906932 bytes, checksum: aa7a99e257aca29fb1c18db5712ba23e (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2003 / A explosão de uso da World Wide Web (Web) e seu crescimento exponencial são fatos reais hoje em dia. A grande quantidade de dados em formato textual disponível de forma dispersa na Web tornou o uso de sistemas de busca bastante popular. Pesquisas mostram que cerca de 57% de usuários da internet fazem uma consulta a cada dia. Esta necessidade de uso tem sido a alavanca da popularidade dos sistemas de busca que, mesmo tendo evoluído de forma significativa nos últimos anos, precisam manter-se atualizados com estruturas capazes de indexar toda essa informação para atender esta demanda de crescimento da Web. Esta dissertação apresenta um levantamento de técnicas no estado-da-arte sobre estruturas de índices para sistemas de Recuperação de Informação (RI) apresentando as estruturas: Arquivo invertido, que é o foco principal deste trabalho; Array de sufixos. que, mesmo oferecendo facilidades na busca em consultas por proximidade, tem um custo de espaço de armazenamento muito alto; e Arquivo de assinaturas, que foi amplamente utilizada em sistemas de RI na década de 80, porém foi superada pelas técnicas modernas aplicadas a estruturas de arquivo invertido. Dentre estas técnicas cita-se a compressão do índice através do uso de codificação Elias e Golomb os quais, além de trazer economia de espaço, melhoram o desempenho tanto no processo de consulta quanto no processo de construção do índice. Além disso, são descritos em detalhes métodos eficientes de acesso e de construção e manipulação do índice. Como resultado do trabalho é proposto o VIF - Vertical Inverted File - implementado na prática a partir de experiência pessoal adquirida durante o trabalho realizado no engenho de busca Radix. O VIF é uma estrutura de índice invertido organizada em blocos baseada em uma estrutura de dados dinâmica B+-Tree que possibilita a inserção eficiente de pequenas quantidades de documentos HTML e, também, oferece uma forma nativa de otimização no processamento de consultas através de salto de blocos. No Radix foram feitos testes sobre a estrutura onde obteve-se ganhos de cerca de 78% de espaço utilizado comparado com a estrutura utilizada anteriormente. Outros testes mostraram melhoria média de 26.5% no tempo de processamento consultas usando salto em blocos comparado com processamento sem otimização, considerando o tempo no processamento das consultas mais realizadas pelos usuários do sistema

A busca por documentos relevantes ao usuário é um problema que se torna mais custoso conforme as bases de conhecimento crescem em seu ritmo acelerado. Este problema passou a resolvido por sistemas distribuídos, devido a sua escalabilidade e tolerância a falhas. O desenvolvimento de sistemas voltados a estas enormes bases de conhecimento -- e a maior de todas, a Internet -- é uma indústria que movimenta bilhões de dólares por ano no mundo inteiro e criou gigantes. Neste trabalho, são apresentadas e discutidas estruturas de dados e arquiteturas distribuídas que tratem o problema de indexar e buscar grandes coleções de documentos em sistemas distribuídos, alcançando grande desempenho e escalabilidade. Serão também discutidos alguns dos grandes sistemas de busca da atualidade, como o Google e o Apache Solr, além do planejamento de uma grande aplicação com protótipo em desenvolvimento. Um projeto próprio de sistema de busca distribuído foi implementado, baseado no Lucene, com idéias coletadas noutros trabalhos e outras novas. Em nossos experimentos, o sistema distribuído desenvolvido neste trabalho superou o Apache Solr com um vazão 37,4\\% superior e mostrou números muito superiores a soluções não-distribuídas em hardware de custo muito superior ao nosso cluster. / The search for relevant documents for the final user is a problem that becomes more expensive as the databases grown faster. The solution was brought by distributed systems, because of its scalability and fail tolerance. The development of systems focused on enormous databases -- including the World Wide Web -- is an industry that involves billions of dollars in the world and had created giants. In this work, will be presented and discussed data structures and distributed architectures related to the indexes and searching in great document collections in distributed systems, reaching high performance and scalability. We will also discuss some of the biggest search engines, such as Google e Apache Solr, and the planning of an application with a developing prototype. At last, a new project of a distributed searching system will be presented and implemented, based on Lucene, with ideas from other works and new ideas of our own. On our tests, the system developed in this work had throughput 37.4\\% higher than Apache Solr and revealed higher performance than non-distributed solutions in a hardware more expensive than our cluster.

A busca por documentos relevantes ao usuário é um problema que se torna mais custoso conforme as bases de conhecimento crescem em seu ritmo acelerado. Este problema passou a resolvido por sistemas distribuídos, devido a sua escalabilidade e tolerância a falhas. O desenvolvimento de sistemas voltados a estas enormes bases de conhecimento -- e a maior de todas, a Internet -- é uma indústria que movimenta bilhões de dólares por ano no mundo inteiro e criou gigantes. Neste trabalho, são apresentadas e discutidas estruturas de dados e arquiteturas distribuídas que tratem o problema de indexar e buscar grandes coleções de documentos em sistemas distribuídos, alcançando grande desempenho e escalabilidade. Serão também discutidos alguns dos grandes sistemas de busca da atualidade, como o Google e o Apache Solr, além do planejamento de uma grande aplicação com protótipo em desenvolvimento. Um projeto próprio de sistema de busca distribuído foi implementado, baseado no Lucene, com idéias coletadas noutros trabalhos e outras novas. Em nossos experimentos, o sistema distribuído desenvolvido neste trabalho superou o Apache Solr com um vazão 37,4\\% superior e mostrou números muito superiores a soluções não-distribuídas em hardware de custo muito superior ao nosso cluster. / The search for relevant documents for the final user is a problem that becomes more expensive as the databases grown faster. The solution was brought by distributed systems, because of its scalability and fail tolerance. The development of systems focused on enormous databases -- including the World Wide Web -- is an industry that involves billions of dollars in the world and had created giants. In this work, will be presented and discussed data structures and distributed architectures related to the indexes and searching in great document collections in distributed systems, reaching high performance and scalability. We will also discuss some of the biggest search engines, such as Google e Apache Solr, and the planning of an application with a developing prototype. At last, a new project of a distributed searching system will be presented and implemented, based on Lucene, with ideas from other works and new ideas of our own. On our tests, the system developed in this work had throughput 37.4\\% higher than Apache Solr and revealed higher performance than non-distributed solutions in a hardware more expensive than our cluster.