VIF - Uma estrutura de índice invertido em blocos baseada ... · Dissertação de Mestrado sob o título VIF - Uma Estrutura de Índice Invertido em Bloosc Baseada em uma B +-Tree

Oscar Gomes de Miranda

VIF - Uma Estrutura de Índice Invertido emBlocos Baseada em uma B+-Tree

Recife, PE - BrasilAgosto de 2003

Oscar Gomes de Miranda

VIF - Uma Estrutura de Índice Invertido emBlocos Baseada em uma B+-Tree

Dissertação apresentada à Coordenação docurso de Mestrado em Ciência da Computa-ção da Universidade Federal de Pernambucopara a obtenção do título de Mestre em Ci-ência da Computação.

Orientadora:Profa. Dra. Ana Carolina Salgado

Universidade Federal de PernambucoCentro de Informática

Recife, PE - BrasilAgosto de 2003

i

Dissertação de Mestrado sob o título �VIF - Uma Estrutura de Índice Invertido emBlocos Baseada em uma B+-Tree�, defendida por Oscar Gomes de Miranda e aprovadaem 8 de Setembro de 2003, em Recife, Pernambuco, pela banca examinadora constituídapelos doutores:

Profa. Dra. Ana Carolina SalgadoOrientadora

Profa. Dra. Kátia Silva GuimarãesUniversidade Federal de Pernambuco

Prof. Dr. Jones Oliveira de AlbuquerqueUniversidade Federal Rural de Pernambuco

ii

À minha mãe.

iii

Agradecimentos

Dedico meus sinceros agradecimentos:� Aos meus pais e toda minha família pelo apoio;� À Profa. Ana Carolina Salgado por ter me orientado e me apoiado no desenvolvi-

mento deste trabalho;� A meus amigos por terem me apoiado e me ajudado diretamente, Thiago Santos,

Luciano Barbosa, Fernando Trinta, Mariano Cravo, Rodrigo Teixeira;� À empresa Mobile e ao antigo Grupo Radix por terem oferecido os recursos neces-

sários para a conclusão deste trabalho;� A todos os amigos do Grupo Radix, Mobile e CIn-UFPE que tive o prazer de

conhecer por terem participado no desenvolvimento deste trabalho, mesmo que de formaindireta, ou por terem me apoiado;

� À Deus sobretudo.

iv

�Só se encontra o que se busca,o que nos é indiferente foge-nos.�

Sócrates

v

Resumo

A explosão de uso da World Wide Web (Web) e seu crescimento exponencial sãofatos reais hoje em dia. A grande quantidade de dados em formato textual disponível deforma dispersa na Web tornou o uso de sistemas de busca bastante popular. Pesquisasmostram que cerca de 57% de usuários da internet fazem uma consulta a cada dia. Estanecessidade de uso tem sido a alavanca da popularidade dos sistemas de busca que, mesmotendo evoluído de forma signi�cativa nos últimos anos, precisam manter-se atualizadoscom estruturas capazes de indexar toda essa informação para atender esta demanda decrescimento da Web.

Esta dissertação apresenta um levantamento de técnicas no estado-da-arte sobre es-truturas de índices para sistemas de Recuperação de Informação (RI) apresentando asestruturas: Arquivo invertido, que é o foco principal deste trabalho; Array de su�xos.que, mesmo oferecendo facilidades na busca em consultas por proximidade, tem um custode espaço de armazenamento muito alto; e Arquivo de assinaturas, que foi amplamenteutilizada em sistemas de RI na década de 80, porém foi superada pelas técnicas modernasaplicadas a estruturas de arquivo invertido. Dentre estas técnicas cita-se a compressãodo índice através do uso de codi�cação Elias e Golomb os quais, além de trazer economiade espaço, melhoram o desempenho tanto no processo de consulta quanto no processo deconstrução do índice. Além disso, são descritos em detalhes métodos e�cientes de acessoe de construção e manipulação do índice.

Como resultado do trabalho é proposto o VIF - Vertical Inverted File - implemen-tado na prática a partir de experiência pessoal adquirida durante o trabalho realizadono engenho de busca Radix. O VIF é uma estrutura de índice invertido organizada emblocos baseada em uma estrutura de dados dinâmica B+-Tree que possibilita a inserçãoe�ciente de pequenas quantidades de documentos HTML e, também, oferece uma formanativa de otimização no processamento de consultas através de salto de blocos. No Radixforam feitos testes sobre a estrutura onde obteve-se ganhos de cerca de 78% de espaçoutilizado comparado com a estrutura utilizada anteriormente. Outros testes mostrarammelhoria média de 26.5% no tempo de processamento consultas usando salto em blocoscomparado com processamento sem otimização, considerando o tempo no processamentodas consultas mais realizadas pelos usuários do sistema.

Palavras-chave: Recuperação de Informação, Web, Estrutura de Dados, ArquivoInvertido, B-Tree.

vi

Abstract

The explosion of the use of the World Wide Web (Web) and its exponential growthare true facts nowadays. The huge amount of data in textual format available widespreadover the Web have made the use of search systems very popular. Statistics show thatabout 57% of the internet users do a query to a search engine everyday. This need ofinformation turned out to be the reason that drives the Web search engines popularity.Even thought the Web search engines have had signi�cant evolution in the last years,they still need to keep up-to-date their data structures in order to re�ect the constantlychanging Web.

This master thesis presents a research describing state-of-the-art techniques aboutindexing structures for Information Retrieval (IR) systems such as: Inverted File, whichis the main focus of this work; Su�x arrays that, even o�ering facilities in searching ofproximity queries, need a high quantity of storage space; and Signature �les, althoughthis approach is no longer in use since it was overtaken by the modern techniques appliedto inverted �le structures, the Signature �les were widely used in IR systems in the 80's.Between those techniques are the index compression methods using, for instance, Eliasand Golomb coding. Such methods decrease the space needed to store the index datawhile increase the performance of the index in query and construction processing time.Moreover, e�cient methods for access, construction and updating of the inverted indexare described.

As result of the work we present the VIF - Vertical Inverted File - actually imple-mented based on the personal experience working on the Radix search engine. The VIFis an inverted �le structure organized in blocks based on a dynamic data structure B+-Tree which made possible the e�cient insertion of small quantity of HTML documents.It also o�ers a native optimization for faster query processing using blocks-jumps. In thetests performed on the structure, the index achieved savings of about 78% of the storagespace used compared with the space spent by the previous data structure used in theRadix search engine. Other tests show savings in query processing time of approxima-tely 26.5% using the optimization of block-jumps compared with the classic approachconsidering only the most requested queries of the system.

Keywords: Information Retrieval, Web, Data Structure, Inverted File, B-Tree.

vii

Sumário

Lista de Figuras xi

Lista de Tabelas xiii

1 Introdução 1

1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Trabalho Proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Organização do Documento . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Sistemas de Indexação e Busca para Web 5

2.1 Recuperação de Informação . . . . . . . . . . . . . . . . . . . . . . . . . . 52.1.1 De�nições Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.2 Visão Lógica dos Documentos . . . . . . . . . . . . . . . . . . . . . 92.1.3 Processo de Recuperação de Informação . . . . . . . . . . . . . . . 11

2.2 Modelos de Recuperação de Informação . . . . . . . . . . . . . . . . . . . . 122.2.1 Modelo Booleano . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.2 Modelo Vetorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.2.3 Modelo Booleano Estendido . . . . . . . . . . . . . . . . . . . . . . 142.2.4 Modelo Probabilístico . . . . . . . . . . . . . . . . . . . . . . . . . 142.2.5 Considerações Sobre Os Modelos . . . . . . . . . . . . . . . . . . . 14

2.3 Sistemas de Recuperação de Informação para Web . . . . . . . . . . . . . . 152.3.1 Modelo do Grafo da Web . . . . . . . . . . . . . . . . . . . . . . . . 152.3.2 O Dinamismo da Web . . . . . . . . . . . . . . . . . . . . . . . . . 17

Sumário viii

2.3.3 Desa�os da Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.4 Arquitetura Centralizada . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4 Consulta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.5 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Índices e Técnicas para Sistemas de Recuperação de Informação 21

3.1 Índices para Sistemas de RI . . . . . . . . . . . . . . . . . . . . . . . . . . 213.1.1 Arquivo de Assinaturas . . . . . . . . . . . . . . . . . . . . . . . . . 213.1.2 Array de Su�xos e Árvore de Su�xos . . . . . . . . . . . . . . . . . 223.1.3 Arquivos Invertidos . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.1.4 Granularidade do Índice . . . . . . . . . . . . . . . . . . . . . . . . 263.1.5 Índice Baseado em Endereçamento de Blocos . . . . . . . . . . . . . 263.1.6 Considerações Sobre As Estruturas Apresentadas . . . . . . . . . . 27

3.2 Estrutura de Índice Dinâmico B+-Tree . . . . . . . . . . . . . . . . . . . . 303.2.1 Busca na B+-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2.2 Inserção na B+-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . 323.2.3 Remoção na B+-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3 Compressão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.3.1 Métodos de Compressão de Índices . . . . . . . . . . . . . . . . . . 363.3.2 Codi�cação com Quantidade Variável de Bytes . . . . . . . . . . . . 363.3.3 Codi�cação Elias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.3.4 Codi�cação Golomb . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.4 Construção do Índice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.4.1 Construção Linear Baseada em Partições . . . . . . . . . . . . . . . 393.4.2 Multi-way In-place Merge . . . . . . . . . . . . . . . . . . . . . . . 403.4.3 Construção em Pipeline . . . . . . . . . . . . . . . . . . . . . . . . 43

3.5 Atualização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Sumário ix

3.5.1 Atualização Incremental sobre B-Tree . . . . . . . . . . . . . . . . . 443.5.2 Atualização em Tempo de Consulta . . . . . . . . . . . . . . . . . . 45

3.6 Processamento de Consultas . . . . . . . . . . . . . . . . . . . . . . . . . . 463.6.1 Processamento de Consultas Booleanas . . . . . . . . . . . . . . . . 463.6.2 Processamento Rápido de Consultas . . . . . . . . . . . . . . . . . 47

3.7 Considerações �nais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4 Especi�cação do VIF 50

4.1 Descrição do Problema e Objetivo . . . . . . . . . . . . . . . . . . . . . . . 504.2 Arquitetura do Radix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.2.1 Módulo de Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.2.2 Função de Termos e de Urls . . . . . . . . . . . . . . . . . . . . . . 534.2.3 Módulo de Indexação . . . . . . . . . . . . . . . . . . . . . . . . . . 544.2.4 Atualização de Base . . . . . . . . . . . . . . . . . . . . . . . . . . 554.2.5 Estrutura IF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.2.6 Estrutura PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.2.7 Atualização dos Índices IF e PL . . . . . . . . . . . . . . . . . . . . 564.2.8 Processamento de Consultas no IF e PL . . . . . . . . . . . . . . . 57

4.3 Especi�cação VIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.3.1 Estrutura VIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.3.2 Organização blocos VIF . . . . . . . . . . . . . . . . . . . . . . . . 594.3.3 Processamento de Consulta no VIF . . . . . . . . . . . . . . . . . . 604.3.4 Processamento com Fila de Prioridade . . . . . . . . . . . . . . . . 614.3.5 Salto de Blocos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.3.6 Construção e Atualização do VIF . . . . . . . . . . . . . . . . . . . 62

4.4 Projeto e Implementação do VIF . . . . . . . . . . . . . . . . . . . . . . . 624.4.1 Ambiente de Desenvolvimento . . . . . . . . . . . . . . . . . . . . . 63

Sumário x

4.4.1.1 Linguagem de Implementação e de Modelagem . . . . . . 634.4.1.2 Plataforma Operacional . . . . . . . . . . . . . . . . . . . 63

4.4.2 Arquitetura VIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.4.3 Modelo Acesso e Manipulação do Índice VIF . . . . . . . . . . . . . 644.4.4 Servidor de Indexação . . . . . . . . . . . . . . . . . . . . . . . . . 684.4.5 Processador de Consultas . . . . . . . . . . . . . . . . . . . . . . . 704.4.6 Árvore de Processamento de Consultas . . . . . . . . . . . . . . . . 734.4.7 Processo de Release no VIF . . . . . . . . . . . . . . . . . . . . . . 77

4.5 Testes e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814.5.1 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814.5.2 Ambiente do Experimento . . . . . . . . . . . . . . . . . . . . . . . 834.5.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.6 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5 Conclusões 88

5.1 Principais Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885.2 Di�culdades Encontradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 895.3 Limitações e Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . 89

Referências Bibliográ�cas 91

Anexo A -- Algoritmo de Counting-Sort 96

Anexo B -- Fila de Prioridades 97

Anexo C -- Tabelas do Teste de Processamento de Consultas 99

Anexo D -- Grá�cos do Teste de Carga 101

xi

Lista de Figuras

1 Processo de recuperação de informação . . . . . . . . . . . . . . . . . . . . 112 Modelo Vetorial baseado na função de cosseno do ângulo . . . . . . . . . . 133 A web vista como uma gravata borboleta . . . . . . . . . . . . . . . . . . . 164 Arquitetura centralizada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 Exemplo de uma consulta booleana . . . . . . . . . . . . . . . . . . . . . . 206 Su�xos de exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Árvore de su�xos do exemplo . . . . . . . . . . . . . . . . . . . . . . . . . 238 Array de su�xos do exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Exemplo arquivo invertido . . . . . . . . . . . . . . . . . . . . . . . . . . . 2510 Estrutura do nó da árvore B+-Tree de grau 2 . . . . . . . . . . . . . . . . 3111 Inserção simples em B+-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . 3312 Inserção em B+-Tree com nó cheio . . . . . . . . . . . . . . . . . . . . . . 3313 Inserção em B+-Tree com nó interno cheio e aumento da profundidade . . 3414 Compressão de texto usando modelo . . . . . . . . . . . . . . . . . . . . . 3515 Procedimento de inversão em memória . . . . . . . . . . . . . . . . . . . . 3916 Procedimento de inversão linear . . . . . . . . . . . . . . . . . . . . . . . . 4117 Procedimento de inversão via multi-way in-place merge . . . . . . . . . . . 4218 Processamento de consulta booleana . . . . . . . . . . . . . . . . . . . . . 4719 Arquitetura Básica do Engenho de Busca Radix . . . . . . . . . . . . . . . 5120 Componentes do módulo de busca do Radix . . . . . . . . . . . . . . . . . 5321 Estrutura IF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5522 Estrutura PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Lista de Figuras xii

23 Estrutura básica índice VIF . . . . . . . . . . . . . . . . . . . . . . . . . . 5924 Organização dos blocos no VIF . . . . . . . . . . . . . . . . . . . . . . . . 6025 Atualização localizada no VIF . . . . . . . . . . . . . . . . . . . . . . . . . 6226 Componentes modi�cados para usar o VIF . . . . . . . . . . . . . . . . . . 6427 Diagrama de Classes dos componentes de acesso e manipulação do índice

VIF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6528 Diagrama de seqüência do Servidor de Indexação do Radix . . . . . . . . . 6929 Diagrama de Classes do Processador de Consultas . . . . . . . . . . . . . . 7030 Diagrama de Seqüência do Processador de Consultas . . . . . . . . . . . . 7231 Diagrama de Classes dos Nós de Processamento da Busca . . . . . . . . . . 7432 Diagrama de Colaboração para Árvore de Processamento . . . . . . . . . . 7633 Diagrama de Colaboração para o Passo 1 do Release do VIF . . . . . . . . 7834 Diagrama de Atividades da Atualização em Blocos no Índice VIF . . . . . 7935 Pseudo-código do algoritmo de divisão dos blocos VIF . . . . . . . . . . . . 8036 Pseudo-código do algoritmo de counting sort . . . . . . . . . . . . . . . . . 9637 Código-fonte em Linguagem Java para a Fila de Prioridades . . . . . . . . 9838 Tempo de resposta com carga de 1000 ms . . . . . . . . . . . . . . . . . . . 10139 Tempo de resposta com carga de 500 ms . . . . . . . . . . . . . . . . . . . 10240 Tempo de resposta com carga de 250 ms . . . . . . . . . . . . . . . . . . . 10241 Tempo de resposta com carga de 125 ms . . . . . . . . . . . . . . . . . . . 10342 Fluxo de consultas com carga de 1000 ms . . . . . . . . . . . . . . . . . . . 10343 Fluxo de consultas com carga de 500 ms . . . . . . . . . . . . . . . . . . . 10444 Fluxo de consultas com carga de 250 ms . . . . . . . . . . . . . . . . . . . 104

xiii

Lista de Tabelas

1 Comparação entre recuperação de dados e recuperação de informação . . . 62 Repositório Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Vocabulário e lista invertida completa do texto exemplo . . . . . . . . . . . 84 Documento codi�cado em um Arquivo de assinaturas . . . . . . . . . . . . 225 Texto exemplo dividido em blocos de 20 palavras . . . . . . . . . . . . . . 266 Vocabulário exemplo com índice de endereçamento de blocos . . . . . . . . 277 Exemplo de codi�cação para números usando as codi�cações unário, Elias-

γ, Elias-δ e Golomb (b=3) . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 Componentes de busca e suas características . . . . . . . . . . . . . . . . . 539 Atributos de uma entrada VIF . . . . . . . . . . . . . . . . . . . . . . . . . 5810 Detalhe dos corpus de testes . . . . . . . . . . . . . . . . . . . . . . . . . . 8211 Espaço utilizado pelo VIF para a BASE1 . . . . . . . . . . . . . . . . . . . 8412 Teste de carga para índice VIF e índice IF mais PL . . . . . . . . . . . . . 8413 Desempenho do índice com a variação do tamanho do bloco . . . . . . . . 8514 Comparação Tempo de Busca usando Otimização de salto em blocos . . . . 8515 Percentual de consultas por quantidade de termos . . . . . . . . . . . . . . 9916 Tempo de Processamento da cache estática com otimização de salto em

blocos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9917 Tempo de Processamento da cache estática sem otimização . . . . . . . . . 10018 Tempo de processamento da cache estática com salto de blocos para con-

sultas com mais de um termo . . . . . . . . . . . . . . . . . . . . . . . . . 10019 Tempo de processamento da cache estática sem otimização para consultas

com mais de um termo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

1

1 Introdução

Sistemas de recuperação de informação automatizados foram originalmente desenvol-vidos para ajudar no gerenciamento da grande quantidade de informação literária emuniversidades e bibliotecas públicas [1]. Hoje em dia a grande número de documentos dis-poníveis na Internet é um desa�o para a área de Recuperação de Informação no sentido demanter estruturas capazes de armazenar, recuperar e gerenciar essa quantidade de dados.Em fevereiro de 1999, a estimativa do tamanho da Web era de 800 milhões de páginas[2], o que representava mais que o dobro do tamanho estimado em dezembro de 1997 (320

milhões). Estimativas mais recentes, em julho de 2000, indicavam que o tamanho da Webera de 2.1 bilhões de páginas únicas e que a sua taxa de crescimento era de 7.3 milhões depáginas adicionais por dia [3]. Estes fatos mostram um crescimento exponencial da Web,Levene [4] mostra um modelo estocástico para identi�car o expoente de crescimento daWeb. Atualmente, a Web tem, por baixo, mais de 3.3 bilhões de páginas [5].

1.1 Motivação

A explosão de uso da 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 Webtornou o uso de sistemas de busca bastante popular. Pesquisas mostram que cerca de 57%de usuários da internet fazem uma consulta a cada dia1. Esta necessidade de uso tem sidoa alavanca da popularidade dos sistemas de busca que, mesmo tendo evoluído de formasigni�cativa nos últimos anos, precisam manter-se atualizados com estruturas capazes deindexar toda essa informação, pois a Web continua crescendo com taxas semelhantes.

Mesmo diante de das di�culdades econômicas observadas no mundo e no Brasil nesteprimeiro semestre de 2003, o uso da internet continua crescendo em níveis elevados quandofoi registrado um aumento de 27% do número de usuários da internet brasileira2. Este

1The Search Engine Index: http://www.searchenginewatch.com/reports/article.php/21564712IBOPE e-Ratings: http://www.ibope.com.br/imprensa/noticias_2003_internetjun_no.htm

1.1 Motivação 2

crescimento, que vem sendo notado nos últimos anos, indica um potencial para a conti-nuação no crescimento tanto do uso diário de engenhos de busca quanto do tamanho daWeb.

Outro ponto importante é a característica dinâmica do conteúdo da internet. Umestudo sobre a freqüência de modi�cação das páginas da Web [6] feito no ano 2000 indicouque 23% das páginas são modi�cadas todos os dias e que o tempo de meia-vida das páginasé de onze dias, isto é, em 11 dias metade das páginas deixam de existir. Este fato deveser considerado quando se busca uma estrutura capaz de indexar a Web.

O Trabalho realizado nesta dissertação também re�ete a experiência pessoal adquiridadurante o desenvolvimento do engenho de busca Radix [7]. Além dos problemas atreladosde forma intrínseca à Web, existem os problemas práticos que foram notados no projeto,onde, por exemplo, o uso de diferentes abordagens de armazenamento quando, no começodo projeto BRight!3 foi utilizado uma estrutura de arquivo invertido armazenando emum sistema baseado em modelo relacional usando um sistema de banco de dados genérico(SGBD) que se apresentou não escalável. Isto acontecia porque a atualização do índiceera feita em tempo de indexação atualizando diretamente cada lista invertida na base dedados fazendo com que o tempo de adição de cada documento novo aumentasse a medidaque a base crescia. O protótipo chegou a armazenar uma quantidade de páginas da ordemde 10.000 (dez mil) apenas. Este foi um dos motivos de migração inicial do protótipo doBRight! para que fosse utilizada uma estrutura de índice especí�ca, no caso foi utilizadauma abordagem simples de arquivo invertido descrita na Seção 4.2.5.

Outras mudanças relacionadas à escalabilidade da estrutura utilizada foram efetuadasdurante a evolução do protótipo do BRight! para o Radix. Outro conceito inserido nodesenvolvimento do sistema foi a atualização de base (release) que, inicialmente, era feitade forma direta on-line e foi atualizada para ser feita em batch. O índice de busca era criadode forma separada do que era coletado na fase de indexação, fazendo com que pudesse serutilizado um procedimento mais e�ciente durante o release que era semelhante ao descritona Seção 3.4.1. Indo mais além, houve uma evolução deste procedimento para um chamadode atualização �incremental� que na realidade se assemelhava a uma construção baseadaem várias uniões de pequenas quantidades de documentos, conforme descrito na Seção3.4.2 sem considerar o uso de compressão do índice e de atualização direta (inplace).

Mesmo tendo evoluído signi�cativamente o engenho apresentava vários problemas degerenciamento das estruturas causados principalmente pelo espaço utilizado pelas estru-

3BRight! foi o projeto de pesquisa [8] que deu origem ao engenho de busca Radix.

1.2 Trabalho Proposto 3

turas. Problema que se tornou mais grave com a utilização de uma estrutura extra paraarmazenar lista de posições das palavras nos documentos criada para possibilitar consul-tas por proximidade (Seção 2.4). Esta estrutura, descrita na Seção 4.2.6, juntamente como índice invertido simples gerava uma sobrecarga de espaço alta. Por exemplo, uma dasbases do Radix com 11 milhões de páginas precisava de um total de 35.1GB para arma-zenar somente estas duas estruturas (Tabela 11). Este custo era muito elevado sendo quenecessitava de muito esforço para gerenciar as duas estruturas, pois eram necessários 7

(sete) dias para a realização do release4.

1.2 Trabalho Proposto

Esta dissertação tem como objetivo principal expor o projeto da estrutura de índiceinvertido VIF - Vertical Inverted File - implementada para incorporar o engenho de buscaRadix. Abaixo segue a lista de objetivos relacionados ao projeto:

• Realizar o levantamento de técnicas no estado-da-arte sobre estruturas de índicespara sistemas de Recuperação de Informação (RI). Foram consideradas as estru-turas: Arquivo invertido, que é o foco principal deste trabalho; Array de su�xos,que, mesmo oferecendo facilidades na busca em consultas por proximidade, tem umcusto de espaço de armazenamento muito alto; e Arquivo de assinaturas, que foiamplamente utilizada em sistemas de RI na década de 80, porém foi superada pelastécnicas modernas aplicadas a estruturas de arquivo invertido. Dentre estas técni-cas cita-se a compressão do índice através do uso de codi�cação Elias e Golomb,os quais, além de trazer economia de espaço, melhoram o desempenho tanto noprocesso de consulta quanto no processo de construção do índice;• Expor a arquitetura utilizada no engenho Radix onde se encaixa todo o projetoapresentado nesta dissertação descrevendo a estrutura utilizada anteriormente, osíndices IF e PL detalhados na Seção 4.2;• Descrever os detalhes da estrutura VIF que, basicamente, é uma estrutura de índiceinvertido organizada em blocos baseada em uma estrutura de dados dinâmica B+-Tree que possibilita a inserção e�ciente de pequenas quantidades de documentosHTML e, também, oferece uma forma nativa de otimização no processamento deconsultas através de salto de blocos;

4Este era o tempo total para criação do novo índice e para atualização das máquinas de busca

1.3 Organização do Documento 4

• Apresentar todos os passos do projeto realizado para a implementação do VIF desdea especi�cação ao projeto;• Fazer a comparação do índice VIF implementado em relação à estrutura anteriorutilizada e fazer os testes de veri�cação do desempenho da estrutura considerandocomo medidas o espaço utilizado, tempo de construção e processamento de consultas.

1.3 Organização do Documento

Este documento está organizado nos seguintes capítulos:Capítulo 2 - Sistemas de Indexação e Busca para Web

São descritos conceitos básicos sobre o assunto Recuperação de Informação (RI) ondesão descritos os modelos �clássicos� para sistemas de RI sendo abordada a aplicação desistemas de RI na Web.

Capítulo 3 - Índices e Técnicas para Sistemas de Recuperação de Informa-ção

Este capítulo descreve as principais estruturas de dados para índices de sistemas deRI e, também, descreve a estrutura de dados B+-Tree que é utilizada no projeto do VIF.Este capítulo também aborda de forma detalhada técnicas em estado-da-arte aplicadas aíndices de arquivo invertido onde são descritas técnicas de compressão de índices, métodose�cientes de construção e atualização do índice e métodos de processamento de consultasem índices invertidos.

Capítulo 4 - Especi�cação do VIF

Apresenta a estrutura de índice VIF resultado da proposta descrita neste documento.Inicialmente é descrita a arquitetura do engenho de busca Radix e a estrutura utilizadapreviamente no engenho. Em seguida é descrita a especi�cação do VIF para depois seremexpostos os detalhes do projeto de implementação do índice VIF. Por �m, são apresentadosos resultados dos testes aplicados à estrutura implementada.

Capítulo 5 - Conclusão

Expõe as conclusões �nais do trabalho apresentado neste documento mostrando asprincipais contribuições alcançadas, as di�culdades encontradas durante o trabalho e pos-síveis trabalhos futuros que possam ser usados para dar continuidade ao que foi realizadoneste trabalho.

5

2 Sistemas de Indexação e Buscapara Web

Este capítulo trata de sistemas de recuperação de informação para Web e conceitosfundamentais que servem de embasamento para a compreensão do trabalho proposto nestadissertação. A Seção 2.1 de�ne Recuperação de informação e terminologias gerais; a Seção2.2 descreve os modelos de sistemas de recuperação de informação; a Seção 2.3 descreveum modelo de arquitetura e modelagem genérica para de Sistemas de RI para Web easpectos relacionados; a Seção 2.4 descreve basicamente como é de�nida uma consulta nosistema. E, por �m, a Seção 2.5 cita algumas considerações �nais do conteúdo tratadoneste capítulo.

2.1 Recuperação de Informação

Recuperação de Informação (RI) é a área que trata da representação, armazenamento,organização e acesso a itens de informação. Um Sistema de RI tem como objetivo básicoresponder ao seu usuário com uma representação e organização de itens de informação demodo que satisfaça os interesses desse usuário [9].

Um Sistema de RI não informa o usuário com conhecimento sobre o assunto de suainvestigação, mas ele informa a existência e o local onde se encontram documentos rela-cionados com sua requisição [10].

Existem outras várias de�nições para Recuperação de Informação que vêm sofrendoalterações durante os anos devido à evolução dos problemas tratados pela área. A falta deuma de�nição formal é algo que já foi discutido por Raghavan [11] onde o autor encorajauma discussão mais pontual sobre uma de�nição que identi�que de forma satisfatória otermo RI. O autor aconselha como ponto de partida o texto de Heaps [12] que resume RIda seguinte forma:

. . . Informação é comumente recuperada por meio de dados que repre-

2.1 Recuperação de Informação 6

sentam documentos. É a ênfase dada na informação relevante a umarequisição que caracteriza recuperação de informação moderna ao invésde ser apenas um ponteiro direto a um documento.

As de�nições modernas de RI sempre tentam destacar as diferenças em relação aRecuperação de Dados (RD) visando esclarecer melhor o que realmente é RI. A Tabela 1resume essas diferenças. Primeiramente, RD consiste em determinar quais documentos deuma coleção contêm o casamento exato das palavras chaves de uma consulta de usuárioenquanto RI recupera informações sobre algum assunto que satisfazem à consulta tentandodescobrir os documentos que interessem ao usuário, i.e., RI visa resolver a necessidade deinformação do usuário. RD retorna todos os documentos usando consultas que satisfazemclaramente condições que estão bem de�nidas em sua estrutura e em sua semântica,inverso de RI que trata de informações textuais em linguagem natural onde as consultasnão são bem de�nidas estruturalmente e muitas vezes também não estão bem de�nidasna sua semântica. Outra diferença é que em RI um erro em milhares de respostas éaceitável enquanto em RD um erro qualquer implica em falha total. Para Sistemas de RIserem mais efetivos eles fazem uma interpretação sintática e semântica no conteúdo dosdocumentos com o objetivo de classi�cá-los de alguma forma relativa a alguma funçãode relevância (Seção 2.2) enquanto em RD os itens de resposta normalmente não sãoclassi�cados, a não ser que o usuário especi�que na sua consulta a classi�cação que deveser usada.

Recuperação de Dados Recuperação de InformaçãoCasamento Exato Parcial, melhor casamentoInferência Dedução InduçãoModelo Determinístico ProbabilísticoLinguagem de Consulta Arti�cial NaturalEspeci�cação da Consulta Completa IncompletaItens Desejáveis Matching Relevantes

Tabela 1: Comparação entre recuperação de dados e recuperação de informação - adaptadade [13]

2.1.1 De�nições Iniciais

Os elementos básicos tratados em um sistema de Recuperação de Informação são:

• Palavra-chave ou termo: É uma seqüência de caracteres (string) que formamuma palavra;


Documento Texto1 Caranguejo não é peixe, Caranguejo peixe é;2 Caranguejo só é peixe na enchente da maré.3 Ora, palma, palma, palma! Ora, pé, pé, pé!4 Ora, roda, roda, roda, Caranguejo peixe é!5 Cai, Cai, balão! Cai, Cai, Balão! Aqui na minha mão.6 Não cai, não! Não cai, não! Não cai, não! Cai no meio do salão!

Tabela 2: Repositório Exemplo: Um documento por linha com seu texto na segundacoluna.

• Página ou Documento: Uma página é uma seqüência de palavras identi�cadapor um endereço. Um documento é a tupla (E, W*) onde E é o endereço da páginae W* é a seqüência de nenhum termo ou vários termos representando o conteúdodo documento1;• Corpus ou Repositório ou Coleção: É o conjunto de documentos armazenadosno sistema. A Tabela 2 apresenta um corpus exemplo com 6 (seis) documentos;• Vocabulário: É o conjunto de todos os termos distintos encontrados no corpus.No campo �palavra-chave� da Tabela 3 estão listados todos os termos que formamo vocabulário do corpus exemplo (Tabela 2);• Endereço de uma Página ou simplesmente endereço: É o identi�cador únicono corpus de um documento. O endereço de uma página é considerado como sendouma URL2, a partir da qual pode-se recuperar o documento;• Lista invertida: É a lista de documentos em que um termo da coleção ocorre;• Posição do termo ou Posição: Indica a posição relativa do termo a partir doinício do documento em quantidade de termos. Por exemplo, posição 1 (um) parao primeiro termo, posição 2 (dois) para o segundo e assim por diante;• Lista de Posições: Para um termo t qualquer do vocabulário e um documento

d qualquer pertencente ao corpus. A lista de posições plt,d é a lista com todos osvalores de posição do termo t no documento d.

1Alguns sistemas não armazenam o documento original, mas apenas o texto interno deixando de lado,por exemplo, informações de formatação do documento e caracteres de pontuação, já que a partir doendereço pode-se recuperar o documento original.2Apesar de identi�car unicamente um documento na coleção, várias URLs podem apontar para omesmo documento. Até porque não existe uma forma canônica de representação de uma URL, por exem-plo as URLs http://www.cin.ufpe.br/ ou http://cin.ufpe.br/ ou http://www.cin.ufpe.br/welcome.htmlou http://www.cin.ufpe.br:80/ apontam para o mesmo documento físico.


Código Palavra-Chave Documentos Total de Ocorrências (Documento: posições)1 aqui 1 1 (5:7)2 balão 1 2 (5:3,6)3 cai 2 8 (5:1,2,4,5)(6:2,5,8,10)4 caranguejo 3 4 (1:1,5)(2:1)(4:5)5 da 1 1 (2:7)6 do 1 1 (6:13)7 enchente 1 1 (2:6)8 maré 1 1 (2:8)9 meio 1 1 (6:12)10 minha 1 1 (5:9)11 mão 1 1 (5:10)12 na 2 2 (2:5)(5:8)13 no 1 1 (6:11)14 não 2 7 (1:2)(6:1,3,4,6,7,9)15 ora 2 3 (3:1,5)(4:1)16 palma 1 3 (3:2,3,4)17 peixe 3 4 (1:4,6)(2:4)(4:6)18 pé 1 3 (3:6,7,8)19 roda 1 3 (4:2,3,4)20 salão 1 1 (6:14)21 só 1 1 (2:2)22 é 3 4 (1:3,7)(2:3)(4:7)

Tabela 3: Vocabulário e lista invertida completa do texto exemplo

Além destas de�nições, os valores numéricos bastante utilizados são:

• Tamanho do corpus (N): É o número total de documentos da coleção. Usadocomo parâmetro indicador do tamanho da coleção;• Tamanho total do texto (B): É a soma do tamanho do texto original de cadadocumento presente no corpus;• Tamanho do Vocabulário (n): É a quantidade de termos distintos que ocorremna coleção. Usado como parâmetro indicador do tamanho da coleção. Textos escri-tos em linguagem natural têm a tendência de seguirem a distribuição de Zipf [14].Desta forma, o valor de n tende a ser muito menor que o tamanho do corpus, porexemplo, uma coleção com 10 Megabytes de texto tem um vocabulário menor que1% do tamanho do texto;• Freqüência em documentos (df): O df de um termo é um valor indicando aquantidade distinta de páginas em que o termo aparece. Para cada termo t ocorrendo


no corpus o valor de df limita-se em 1 ≤ dft ≤ n. O campo �Documentos� da Tabela3 equivale ao df do termo;• Identi�cador de página (docid) e Identi�cador de termo (termid): Estesidenti�cadores são valores internos em um sistema de recuperação de informaçãoque representam unicamente cada documento (identi�cador de página) e cada termo(identi�cador de termo). Para cada termo e para cada documento é atribuído umvalor numérico que será usado no sistema para tornar o processamento interno maise�ciente. Para o usuário �nal estes códigos não são visíveis. Estes identi�cadores sãoutilizados nos índices para evitar o armazenamento das strings dos termos ou dosendereços das páginas. Os valores limitam-se em 1 ≤ docid ≤ N e 1 ≤ termid ≤ n;• Número de entradas (f): É a quantidade de pares (termid, docid) existentes nocorpus. Podendo ser calculado a partir dos valores de df , onde f =

∑nt=1 dft.

2.1.2 Visão Lógica dos Documentos

Um documento, basicamente, é modelado por um conjunto de palavras chaves outermos (como descrito na seção anterior) retirados diretamente do documento original ou,também, podem ser adicionados por meio externo, como por exemplo, através de adiçãode informação extra ao documento via interação humana. O sistema de recuperaçãode informação deve ser responsável pela extração da informação textual do documento.Além disso, o sistema pode extrair outros dados que representem a estrutura sintáticaou semântica do documento. A estrutura sintática equivale a estrutura organizacionalformada por elementos que de�nem a formatação do documento, enquanto a estruturasemântica equivale ao signi�cado do conteúdo descrito no documento. Por exemplo,um documento pode ser indexado usando conceitos no lugar de palavras-chaves, estesconceitos identi�cam o signi�cado da palavra e, dessa forma, é possível recuperar umdocumento mesmo sem especi�car exatamente as palavras-chaves presentes no documento.Isto é possível fazendo uma busca por por conceitos que estejam descritos no documento.

A extração dos elementos do texto pode identi�car informação relevante que podeser usada para classi�car de forma mais efetiva a relevância do documento em relaçãoà consulta do usuário ou até mesmo extrair dados úteis ou �ltros como, por exemplo, alíngua do texto, localização geográ�ca, assunto do documento.

Além disso, o sistema também pode fazer outros tratamentos antes de gerar a repre-sentação interna �nal do documento, neste tratamento pode-se usar técnicas de operações


sobre o texto, tais como: extração de stopwords, stemming, case folding e thesaurus [1].

• Extração de Stopwords: Stopwords são palavras com elevada freqüência de ocor-rência nos textos. Normalmente são elementos da gramática das línguas utilizadasnos textos que não de�nem nenhum conceito e não são úteis para identi�cação deassuntos especí�cos. Por exemplo, artigos, conjunções, advérbios são consideradosstopwords e são adicionados na chamada lista de stopwords ou simplesmente stoplist.Todas as palavras pertencentes a esta lista são removidas do texto e não fazem partedo índice;• Case folding : técnica que visa uni�car palavras com diferentes capitalizações, porexemplo, as palavras chaves Página e página e PÄGINA e qualquer outra combinaçãoseriam tratadas todas como página;• Stemming : técnica utilizada para extrair os radicais de cada palavra do texto;• Thesaurus: Esta técnica visa encontrar sinônimos das palavras do texto, destemodo pode-se usar apenas uma de�nição para os mesmos sinônimos economizandoespaço.

Witten, Mo�at e Bell [1] citam que o principal efeito causado pelo uso destas técnicasé a diminuição do tamanho do índice, principalmente quando aplicado a índices invertidos(Capítulo 3). Existem dois motivos para esta redução: o primeiro é que com o uso destemming e case folding, o número de termos diminui consideravelmente; segundo, afreqüência média de termos no documento tende a aumentar de modo que o número deentradas total(f) do índice diminua. Os autores citam que o efeito destas duas técnicasna coleção TREC3 com 741 mil documentos reduz o número de entradas(f) em 16%e o número de termos distintos(n) em 40%, fazendo com que o tamanho do índice sejareduzido para 30% do seu tamanho original. Eles também citam o efeito do uso da técnicade remoção de stopwords que proporciona um ganho signi�cativo ao tamanho �nal doíndice, pois estes termos praticamente aparecem em todos os documentos na coleção.Por exemplo, na mesma coleção TREC com um vocabulário com 535 mil termos distintosexistem 33 termos que aparecem em mais de 38.2% dos documentos. Uma pequena fraçãodo vocabulário que ocupa cerca de 11% do total de entradas do índice(f). Além dissoa eliminação das stopwords afeta o tempo de processamento onde não é mais necessário

3A coleção TREC, um acrônimo para Text REtrieval Conference, é uma coleção disponibilizada nainternet para ser usada por grupos de pesquisa com objetivo de fornecer uma base para comparação entreexperimentos na área de recuperção de informação.


processar consultas com termos de stoplist diminuindo o tempo de processamento destasconsultas.

2.1.3 Processo de Recuperação de Informação

A Figura 1 ilustra os componentes básicos de uma arquitetura genérica para sistemasde recuperação de informação.

Inicialmente existe o corpus do sistema que contém os documentos com toda a infor-mação textual usada pelo sistema. A estrutura textual de cada documento do corpus éanalisada e são retirados os elementos do texto para formar a visão lógica do documento.Sobre esta visão lógica é gerado o índice do sistema usado para responder as consultasdos usuários. A estrutura mais popular utilizada neste índice é o arquivo invertido maspodem ser usadas outras estruturas como as descritas na Seção 3.1.

Figura 1: Processo de recuperação de informação

Com o índice pronto, o usuário pode consultar o sistema. Para isto, o usuário uti-liza uma interface de consulta onde ele especi�ca sua necessidade de informação. Estanecessidade de informação é tratada e interpretada pelo sistema para depois ser feita abusca no índice onde são gerados os documentos recuperados que são classi�cados pelo

2.2 Modelos de Recuperação de Informação 12

sistema e listados para o usuário em ordem de relevância julgada pelo sistema relativa ànecessidade de informação do usuário. Além disso o usuário pode interagir com o sistemaexaminando a resposta que lhe é mostrada e indicando ao sistema alguns destes docu-mentos que realmente são relevantes e os que não são relevantes. O sistema pode usaresta informação para reformular a consulta e retornar outro conjunto de respostas maisaprimorado.

2.2 Modelos de Recuperação de Informação

Modelos de recuperação de informação são formas sistemáticas que de�nem como umsistema faz o cálculo da relevância dos documentos, ou seja, basicamente tais modelosde�nem uma função de ordenamento e um framework de como é feita a representação dosdocumentos, das consultas e a relação entre eles.

Um dos principais problemas de sistemas de recuperação de informação é predizerquais documentos são relevantes e quais não são. Esta decisão depende do algoritmo decálculo de relevância utilizado, considerado como o núcleo do sistema, onde é de�nida afunção de ordenamento do sistema. Esta função é uma relação que associa um númeroreal a uma consulta e a um item de resposta. Tal função de�ne uma ordem entre ositens de resposta de modo que os itens que estejam no topo sejam os considerados maisrelevantes.

Na literatura surgiram vários modelos para este problema. Os modelos clássicos deRI são descritos nas próximas seções.

2.2.1 Modelo Booleano

O modelo booleano [9] é um modelo de recuperação de informação simples baseadoem teoria de conjuntos e algebra booleana. Por usar o conceito de conjuntos que é bemintuitivo, sistemas de RI baseados neste modelo tem uma interface de consultas fácil deser utilizada por um usuário comum. Além disto, as consultas no modelo booleano sãodescritas como expressões booleanas tendo uma semântica precisa. Por estes motivos omodelo booleano foi adotado por vários sistemas de recuperação no passado. Entretanto,este modelo peca em usar uma estratégia de ordenamento baseado em decisão binária(um documento ou é relevante ou não) onde o sistema não consegue distinguir o grau derelevância dos itens de resposta de uma consulta. Outra desvantagem do modelo booleanoé di�culdade de fazer a tradução de uma necessidade de informação de usuário em uma


expressão booleana.

2.2.2 Modelo Vetorial

O Modelo Vetorial [15, 9] faz uso de modelagem em espaço vetorial possibilitando ouso de pesos como critério de ordenamento entre itens de resposta de uma consulta, etambém, possibilita a recuperação por casamento parcial. Neste modelo os documentos eas consultas são tratados como vetores de um espaço n-dimensional onde cada dimensãoé relativa a um termo distinto na coleção. O valor da função de ordenamento é calculadoa partir de uma função de similaridade que opera sobre dois argumentos: a consulta e odocumento; esta função é usada para de�nir o grau de correlação entre cada documentoe a consulta.

Uma medida simples que pode ser usada é a função do cosseno do ângulo formadoentre os vetores da consulta e do documento como ilustrado na Figura 2. Existem váriasoutras funções de similaridade [16] sendo que esta função de cosseno é a mais utilizada.

Figura 2: Modelo Vetorial baseado na função de cosseno do ângulo

Os pesos usados nos vetores dos termos na função de similaridade podem ser calculadosde várias formas. O esquema mais conhecido para estes pesos é o tf-idf que é baseado nasmedidas de (i) tfi,j que é a freqüência do termo i no documento j, ou seja, a quantidade devezes que o termo i aparece no documento j; e (ii) dfi que é a quantidade de documentosem que o termo i aparece. Estas duas medidas têm suas utilidades no cálculo da funçãode ordenamento. Para o tf , quanto maior a freqüência de um termo maior será o seu pesode ordenamento. O df é útil para indicar no valor da função de ordenamento os termosque ocorrem em muitas páginas. Estes tipos de termos são considerados pouco úteis pois


não servem para distinguir se um documento é relevante ou não.

2.2.3 Modelo Booleano Estendido

O modelo booleano Estendido [15] é basicamente a união do modelo clássico booleanocom o cálculo de relevância usado no modelo vetorial evitando o problema de decisãobinária de relevância. No modelo booleano estendido a consulta continua sendo represen-tada por uma expressão booleana. Além disso, este modelo utiliza os critérios do modelovetorial para classi�car os itens de resposta que integram o espaço vetorial dos termos daconsulta e satisfazem a expressão booleana da consulta.

2.2.4 Modelo Probabilístico

O Modelo probabilístico tem como objetivo encontrar o conjunto de resposta quecontenha todos os documentos relevantes e nenhum outro além destes. Este conjunto éde�nido como o conjunto ideal de respostas. Para encontrar este conjunto ideal o modeloprobabilístico calcula a probabilidade de relevância de cada documento. Para gerar estasprobabilidades o modelo assume que, para uma certa consulta q e um documento d,esta probabilidade depende de q e d apenas. As probabilidades de relevância de cadadocumento são calculadas a partir do índice de termos dos documentos classi�cados comorelevantes.

2.2.5 Considerações Sobre Os Modelos

Existe uma di�culdade na escolha do melhor modelo a ser usado em um sistema deRI, principalmente porque não se sabe de que forma os modelos afetam o usuário. Alémdos modelos clássicos citados nesta seção, existem vários outros de�nidos na literatura quepodem ser considerados[9] e, dentre estes modelos, vários fatores podem ser consideradosdurante a escolha do modelo, não apenas o aspectos relacionados ao próprio corpus mastambém os aspectos relacionados aos usuários do sistema. Observa-se que um sistemade RI para a Web possui características peculiares (Seção 2.3.3) e além disso os usuáriosas vezes nem sabem sequer o que procuram ou não sabem como formular uma consulta.Esta dissertação se baseia no modelo de Booleano Estendido por usar uma interface deconsulta simples baseado em teoria dos conjuntos (Seção 2.4) e por possibilitar uma formade cálculo de relevância baseado em de�nições de documentos e palavras-chaves como asdescritas na Seção 2.1.1.

2.3 Sistemas de Recuperação de Informação para Web 15

2.3 Sistemas de Recuperação de Informação para Web

Sistemas de recuperação de informação automatizados foram originalmente desenvol-vidos para ajudar no gerenciamento da grande quantidade de informação literária emuniversidades e bibliotecas públicas. Hoje em dia a grande quantidade de documentosdisponíveis na Internet é um desa�o para a área de Recuperação de Informação no sen-tido de manter estruturas capazes de armazenar, recuperar e gerenciar essa quantidadede dados. São mais de três bilhões de páginas Web indexadas [5] em 40 milhões de sitese sendo acessadas por 605 milhões de usuários. E até mesmo hoje em dia este númerocresce continuamente de forma exponencial [17].

Sistemas de recuperação de informação para Web, os conhecidos engenhos de busca,são bastante populares nos dias atuais chegando a obter alto nível de �delidade entre osusuários onde cerca de 75% dos usuários da Web usam engenhos de busca para navegarpela rede 4. Sem dúvida o mais popular engenho de busca no momento é o google [5]que vem se mantendo líder entre os maiores engenhos de busca da atualidade por serum dos mais e�cientes no tratamento dos principais fatores críticos em um engenho debusca. Entre os fatores estão relevância, tamanho do índice, índice recente, desempenhoe facilidade de uso 5.

Nestes últimos anos, essa popularidade dos engenhos de busca chamou a atenção tantoda comunidade cientí�ca quanto do mercado �nanceiro quando houve vários investimentosna área e a criação de sistemas de busca pelo mundo. Um deles foi o Radix6 que surgiudo projeto de pesquisa BRight [8] desenvolvido no Centro de Informática da UniversidadeFederal de Pernambuco, que era um sistema de busca especializado em indexar a Webbrasileira onde foi desenvolvido todo o trabalho desta dissertação.

2.3.1 Modelo do Grafo da Web

AWeb pode ser vista como uma grande biblioteca virtual, e além dos aspectos citadosnos itens anteriores, a Web tem características únicas que vêm sendo modeladas pelacomunidade cientí�ca. Um dos modelos que é bem difundido atualmente é o modelo daGravata Borboleta [18] que de�ne o grafo de hyperlinks dos documentos existentes naWeb da seguinte forma. Nele existem três classes básicas de páginas como ilustrado naFigura 3 que são:

4http://www.searchenginewatch.com/sereport/article.php/21626815http://searchenginewatch.com/searchday/article.php/22199916www.radix.com.br


Figura 3: A web vista como uma gravata borboleta

• Núcleo: é composto dos documentos com links entre si, ou seja, é um componentefortemente conexo;• IN: é a classe das páginas que existe um caminho dela para o núcleo, mas não existecaminho inverso. Também chamada de classe da web invisível ;• OUT: são as páginas que podem ser alcançadas a partir do núcleo, mas não têmcaminho de volta. São os pontos �nais, sem saída;• Dendritos: são as páginas restantes que não têm ligações para o núcleo e nemligações do núcleo para elas.

O grafo daWeb é útil para se compreender a disposição dos documentos pela rede.Estudostêm utilizado a estrutura de links para tentar identi�car o comportamento da Web. Estesestudos visam identi�car melhorias em sistemas de RI como, por exemplo, formas maise�cientes de crawling [19] e formas de ordenamento de páginas como algoritmo de Page-Rank [20] utilizado no google ou o algoritmo de HITS [21, 22] onde ambos utilizam o grafode links da Web para fazer o cálculo de relevância dos documentos.


2.3.2 O Dinamismo da Web

Além de estudos que modelem o Grafo de links da Web existem os que analisam ocomportamento das páginas. O estudo do comportamento do dinamismo das páginas é útilporque ele pode ser usado como base para otimizações de estruturas ou de outros processosde modo geral. Em 2000 foi realizado um estudo sobre a freqüência de modi�cação daspáginas da Web onde foram observadas meio milhão de páginas durante quatro meses [6].Este estudo indicou que 23% das páginas são modi�cadas todos os dias e que o tempo demeia-vida das páginas foi de onze dias, isto é, em 11 dias metade das páginas deixam deexistir. Estudo semelhante sobre a Web brasileira em 2002 [23] de�niu uma metodologiausando técnicas de IA para classi�cação de grupos de páginas de acordo com a freqüênciade atualização das páginas Web para diminuir o desperdício de recursos de rede gastosdurante o crawling.

2.3.3 Desa�os da Web

Baeza-Yates e Ribeiro-Neto [24] descrevem os principais problemas associados aosdados da Web. Entre eles:

• Dados distribuídos: Em virtude da natureza intrínseca da Web, os dados estãoespalhados em vários computadores em várias plataformas diferentes conectadoscom links de diferentes largura de banda;• Alto percentual de dados voláteis: Grande parte dos dados na Web mudambastante como descrito na Seção 2.3.2;• Grande quantidade de dados: O crescimento exponencial da Web acarreta umagrande di�culdade na manipulação de tamanha quantidade de dados;• Dados não estruturados e redundantes: Grande parte dos documentos na Webnão são bem estruturados e, além disso, a maioria dos documentos são repetidos(sites espelhos ou cópias simples) onde cerca de 30% das páginas da Web são cópiasou copias aproximadas (near duplicates) [25, 26];• Qualidade dos dados: Grande parte da informação textual presente na Web éfeita com uma escrita pobre e muitos documentos contêm vários erros. São erros degra�a, erros gramaticais e outros. Além disso, a informação pode ser falsa;


• Dados heterogêneos: O conteúdo da Web pode estar disponível em vários tiposde arquivos (vídeo, texto, imagem, som) e também em vários tipos de formatos (gif,jpg, png, ...). Além disto, os documentos são escritos em várias línguas, escritas edialetos.

2.3.4 Arquitetura Centralizada

A maior parte dos engenhos de busca utiliza uma arquitetura centralizada de Indexa-ção. Esta arquitetura se baseia no uso de crawlers que são programas que percorrem aWeb coletando as páginas atualizadas e enviando-as para um servidor de indexação quemantém o índice do engenho. Os crawlers também são processos locais, normalmenteexecutando na mesma máquina ou numa máquina na rede local. Eles recuperam os dadosdas páginas da Web via requisições HTTP. O Servidor de indexação mantém o índiceatualizado e envia ao servidor de links os links que foram coletados para novas páginas.O servidor de links por sua vez alimenta os crawlers com novos endereços. Este processoé contínuo, e é deste modo que o sistema se auto-alimenta como ilustrado na Figura 4.

Figura 4: Arquitetura centralizada

Este tipo de arquitetura ainda oferece alguns problemas. O primeiro é que esta arqui-tetura gera um tráfego intenso de dados nas proximidades do engenho de busca saturandoa rede usando os recursos de rede da Web de forma dispendiosa. Outro problema está

2.4 Consulta 19

associado com o tamanho da Web que torna impraticável o custo da capacidade de pro-cessamento e armazenamento para manter uma arquitetura central que suporte toda aWeb7.

2.4 Consulta

Uma consulta é a forma de uma usuário exprimir sua necessidade de informação.Os engenhos de busca utilizam consultas baseadas em palavras chaves indicando que ousuário procura por documentos que contenham os termos especi�cados na consulta [9].Os tipos básicos de consultas são:

• Consulta por uma única palavra: é uma consulta onde é especi�cado apenasum termo e onde são retornados os documentos que contêm este termo;• Consulta por vários palavras: é uma consulta onde são especi�cados váriostermos e são retornados documentos que contêm todas as palavras da consulta;• Consulta por frase: é uma consulta formada por uma lista de palavras-chave quecompõem uma frase e são retornados apenas os documentos que contêm esta frase,i.e., os documentos que contêm os termos na mesma seqüência que foram de�nidospelo usuário;• Consulta por proximidade: é uma consulta formada por palavras e frases eum parâmetro indicando a maior distância permitida entre elas. São retornadosos documentos que contêm estas palavras ou frases não necessariamente na mesmaordem de�nida na consulta contanto que obedeça o limite da distância entre eles;• Consulta booleana: é uma consulta formada por uma expressão lógica compalavras-chave e conectivos E, OU e NÃO, onde são retornados documentos quesatisfazem a expressão formada pela consulta, cada conectivo equivale a uma ope-ração lógica. A operação �a E b� recupera os documentos que contêm �a� e �b�, aoperação �a OU b� recupera os documentos que contêm �a� ou �b� e a operação �aNÃO b� recupera os documentos que contêm �a� mas não contêm �b�8. Por exem-plo, a Figura 5 ilustra a árvore sintática da consulta booleana �(índice OU arquivo)

7Para se ter uma idéia, o google com um índice de 3 bilhões de páginas usa mais de 10.000 servidoresem um cluster linux (http://www.google.com/press/highlights.html)8A operação lógica clássica unária �NÃO a� indica que são retornados todos os documentos menosos que contêm �a� o que retornaria bastante documentos que provavelmente não seria o que o usuáriogostaria. Por este motivo se usa a versão binária mais restrita.

2.5 Considerações Finais 20

E invertido� que representa uma consulta por documentos que contêm as palavras�arquivo� ou �índice� e também contêm a palavra �invertido�.

Figura 5: Exemplo da consulta booleana �(índice OU arquivo) E invertido�

2.5 Considerações Finais

Este capítulo descreve um breve resumo do que é um Sistema de Recuperação deInformação para a Web com intuito de esclarecer os desa�os acerca da implementaçãodo sistema, listando as de�nições e conceitos básicos associados a um sistema de RI. ASeção 2.2 descreve os modelos para sistemas de RI onde é destacado o modelo BooleanoEstendido, que é utilizado como base do conteúdo tratado nos próximos capítulos. Alémdisso, este capítulo descreve também, uma arquitetura genérica de um engenho de buscapara a Web que é utilizada como molde para o sistema Radix descrito no Capítulo 4.

21

3 Índices e Técnicas para Sistemasde Recuperação de Informação

Neste capítulo são descritas estruturas de dados utilizadas em índices para sistemas deRecuperação de Informação e técnicas para gerenciar estes índices de forma e�ciente comfoco na estrutura de arquivo invertido. Inicialmente são descritas três estruturas de índi-ces: Arquivo de Assinaturas, Array de Su�xos e Arquivo Invertido. A Seção 3.1 descreveestas estruturas e faz uma comparação entre elas. A Seção 3.2 descreve a estrutura dedados B+-Tree que é utilizada na elaboração do índice VIF descrito no próximo capítulo.A Seção 3.3 aborda técnicas de compressão de índices. A Seção 3.4 descreve métodose�cientes para construção de índices invertidos. Na Seção 3.5 são abordadas técnicas paraatualização do índice. A Seção 3.6 descreve como é realizado o processamento de consultausando o índice invertido. Por �m, a Seção 3.7 segue com algumas considerações �naissobre este capítulo.

3.1 Índices para Sistemas de RI

Esta seção cita as estruturas de dados mais utilizadas para índices em sistemas derecuperação de informação na Web, dentre eles: arquivo invertido, array de su�xo earquivo de assinaturas.

3.1.1 Arquivo de Assinaturas

Arquivo de Assinaturas [27] é a estrutura de índice que se baseia no uso de assinaturashash. Nas estruturas de índices de arquivos de assinatura existe uma função de hash queé usada para gerar as assinaturas das palavras. Além da assinatura das palavras existemas assinaturas dos documentos que são formadas pela união das assinaturas dos termosque ocorrem no documento usando a operação OR bit a bit ilustrada na Tabela 4. Paradescobrir as páginas onde um termo qualquer aparece deve-se fazer uma operação AND

3.1 Índices para Sistemas de RI 22

de bits entre a assinatura do termo e a assinatura da página. Deste modo, se todos osbits da assinatura do termo estiverem presentes na assinatura da página, esta páginaé quali�cada como possível resposta. Para saber se a página foi uma resposta real ouapenas um casamento incorreto, um false match, isso deve ser con�rmado recuperandoo documento. Por exemplo, uma consulta pelo termo �inadequado� cuja assinatura é0110 0001 0010 0010 quando for comparado com a assinatura do documento da Tabela 4acontece um false match que será apenas veri�cado quando o documento for recuperadoe for comprovado que o termo �inadequado� foi um engano. Quando não houver umcasamento das assinaturas, então a página é classi�cada como não tendo o termo, sendodescartada de imediato.

Além de uma busca simples, a estrutura é capaz de processar consultas com expressõesbooleanas. Para isto, basta realizar um processamento lógico em cima da assinatura decada página. Essas estruturas têm custo de armazenamento baixo, cerca de 10% a 20%do texto, entretanto tem custo alto de processamento de consultas pois é necessária umabusca seqüencial no índice.

Termo Assinaturaexemplo 0110 0000 1010 0010arquivo 1100 0001 0010 1010assinatura 0010 0101 1110 0010

Assinatura do documento 1110 0101 1110 1010

Tabela 4: Documento codi�cado em um Arquivo de assinaturas

3.1.2 Array de Su�xos e Árvore de Su�xos

Árvores de su�xos1 são estruturas capazes de armazenar su�xos do texto dos do-cumentos possibilitando não somente recuperar palavras-chave, mas também encontrarfacilmente textos com partes de palavras ou frases exatas.

A estrutura de árvores de su�xos foi descrita pela primeira vez por Morrison, em1968 [28], tendo Weiner [29] apresentado uma versão mais completa em 1973. Váriasabordagens foram criadas visando melhorar o desempenho da estrutura, sendo que em1976, McCreight expôs um algoritmo para a construção da árvore de su�xos em tempo deexecução linear [30]. Mais recentemente, em 1995, Ukkonen [31] apresentou um algoritmoon-line para a construção desta estrutura.

1Adotaremos esta terminologia para estruturas em Árvore de su�xo(su�x tree) e Array de su�xo(su�xarray) também conhecidas como PAT tree e PAT array, respectivamente.


Figura 6: Su�xos de exemplo

Figura 7: Árvore de su�xos do exemplo

Numa árvore de su�xo cada posição do texto é um su�xo diferente. Não necessari-amente todas as posições estão presentes na árvore, são escolhidas preferencialmente asposições iniciais de palavras. A Figura 6 demonstra alguns su�xos retirados do texto deexemplo. A árvore de su�xo é semelhante a uma estrutura Trie de strings mas de formacompactada em uma Patricia Tree. Nas árvores de su�xo os nós folhas contêm a posiçãoinicial do su�xo no texto e os nós internos direcionam a busca até os nós folhas baseadosnos caracteres do su�xo. Cada nó interno possui ligações para sub-árvores e cada ligaçãoé nomeada por uma cadeia de caracteres especi�cando o pre�xo do su�xo da sub-árvore.A Figura 7 ilustra a árvore de su�xos resultante do texto exemplo. Entretanto, árvoresde su�xos não são utilizadas na prática para textos muito grandes por causa do alto custode armazenamento onde é necessário alocar espaço para todos os nós e links da árvore.


Array de su�xos [32, 33] é uma implementação de Árvore de su�xos com uso e�cientede espaço em disco. Um array de su�xos pode ser visto como uma forma compactadada árvore de su�xos onde é usada apenas uma parte da árvore. O array de su�xoscontem apenas os nós folhas armazenados em um array na ordem presente na árvore desu�xos. A Figura 8 ilustra o array de su�xos do texto exemplo. Sobre o array de su�xospode ser utilizada uma estrutura auxiliar chamada de supra-index [9], ela é útil paraindexar diretamente palavras do texto limitando o espaço da busca binária por padrõesna estrutura. Este supra-index armazena para cada palavra chave do texto um ponteiroindicando o início da lista de su�xos para esta palavra no array de su�xos.

Figura 8: Array de su�xos do exemplo

Em uma árvore de su�xos a busca por um padrão qualquer de m caracteres pode serencontrada em tempo O(m) com uma busca simples na árvore. Esta busca pode ser umabusca por uma palavra-chave, assim como o uso de arquivos invertidos, ou uma busca poruma frase exata ou até uma busca por parte de uma palavra. Nos arrays de su�xos otempo de busca é equivalente a uma busca binária no array em tempo O(log n) onde n éo número total de su�xos. Uso do supra-index e de otimizações na busca binária utilizadapodem diminuir este custo a algo em torno de 40% a 60% no tempo de processamento.

3.1.3 Arquivos Invertidos

Arquivo invertido [15, 34] é um mecanismo para indexar coleções textuais ao nível depalavras. Arquivos invertidos são as estruturas mais utilizadas em sistemas de RI por se-rem a forma mais intuitiva de modelar e estruturar o acesso aos dados. A função principalde um arquivo invertido é retornar a lista de documentos onde ocorre um termo tendocomo idéia básica o armazenamento do mapeamento inverso de termos para documentos.

A estrutura de arquivo invertido é composta por dois elementos: o vocabulário ea lista invertida como ilustrado na Figura 9. O vocabulário contém o conjunto de to-das as palavras distintas que aparecem no corpus, o vocabulário é muito menor quando


comparado com a lista invertida e, dependendo do tamanho do texto original, pode sergerenciado por completo em memória principal por uma estrutura Trie ou uma hashtableou uma B+-Tree (Seção 3.2). Para o caso do texto não caber em memória, é necessáriousar uma estrutura secundária normalmente uma B+-Tree ou um hashtable em arquivo.No vocabulário comumente são armazenados o número de documentos que o termo ocorre(df) e o ponteiro para a sua lista invertida.

Figura 9: Exemplo arquivo invertido

A lista invertida contém a relação de documentos onde cada palavra aparece. Ainformação presente em cada lista invertida são apontadores para os documentos que apalavra chave ocorre e, geralmente, são adicionadas outras informações que podem serúteis durante o processamento de consultas como, por exemplo, a lista de posições decada palavra que é adicionada para que seja possível processar consultas por frases exatasou consultas por proximidade.

Os índices de arquivos invertidos normalmente são criados a partir de um processoem batch, deste modo sempre que se deseja atualizar a base é necessário inverter2 a basepor completo. Existe um procedimento com tempo de execução proporcional ao tamanhodo corpus para esta inversão [13]. Entretanto, este procedimento é útil apenas para basespequenas ou que sejam estáticas ou semi-estáticas, isto é, que modi�quem pouco e poucasvezes, mas para a Web este processo não é e�ciente o su�ciente. Outros trabalhos de�nemestruturas de índices invertidos otimizadas para operações de acréscimo de páginas, istoé, apenas com adição de novas páginas, e o resultado experimental foi um procedimentocom tempo de execução proporcional ao tamanho do texto a ser adicionado [35, 36]. Maisdetalhes sobre a estrutura de arquivo invertido serão tratados no próximo capítulo.

2usamos o termo �inverter� ou �inversão� para indicar o processo de gerar o arquivo invertido


3.1.4 Granularidade do Índice

Granularidade de um índice [1] é o nível de precisão de um índice em localizar umapalavra. Existem três níveis básicos de granularidade de índices que são: (a) no nível depalavras, presente no índice chamado índice invertido completo e (b) no nível de docu-mento, o mais popular, presente no índice chamado arquivo invertido ou índice invertidoe (c) no nível de blocos, presente no índice baseado no endereçamento de blocos. Em(a) cada palavra é armazenada com a informação de localização completa da palavra nodocumento, neste caso, o índice armazena todas as posições de palavras existentes, estetipo de índice serve de apoio para poder processar consultas por frases. Mas no nívelde documentos (b) todas as entradas de uma mesma palavra em um documento são co-lapsadas em uma entrada única. Dependendo da granularidade, o índice pode precisarde menos espaço de armazenamento. Entretanto a quantidade de casamentos inválidos(false matches) durante o processamento pode aumentar gerando a necessidade de leiturado texto original com impacto direto no tempo de processamento. E, por �m, existe agranularidade no nível de blocos (c) que é ainda mais esparso que no nível de documen-tos, onde o repositório é dividido em blocos sendo que cada bloco pode conter parte depáginas ou até várias páginas pequenas. Este nível de granularidade é utilizado no índicede endereçamento de blocos descrito na próxima seção.

Bloco Texto1 Caranguejo não é peixe, Caranguejo peixe é;

Caranguejo só é peixe Na enchente da maréOra, palma, palma, palma! Ora

2 pé, pé, pé!Ora, roda, roda, roda, Caranguejo peixe é!Cai, Cai, balão! Cai, Cai, Balão! Aqui na minha mão.

3 Não cai, não! Não cai, não! Não cai, não! Cai no meio do salão!Tabela 5: Texto exemplo dividido em blocos de 20 palavras

3.1.5 Índice Baseado em Endereçamento de Blocos

O índice baseado em endereçamento de blocos [9] é fundamentado no agrupamento depáginas em blocos sobre um índice invertido. Neste índice, cada bloco contém parte dotexto de uma página ou vários textos de várias páginas pequenas. Quando uma palavra-chave ocorre várias vezes no mesmo bloco esta entrada é armazenada apenas uma únicavez no índice. Deste modo, o índice se torna mais compacto que um índice invertidoque aponta para todas as ocorrências, os chamados índices invertidos completos. Esta


técnica, além de colapsar todas as entradas de uma mesma palavra-chave dentro de umbloco fazendo com que haja menos ponteiros, também utiliza ponteiros menores pois hámenos blocos do que entradas. Usando esta técnica o índice chega a 5% do texto. ATabela 6 mostra o vocabulário e a lista de blocos do corpus exemplo dividido em blocosde 20 (vinte) palavras (Tabela 5) onde a lista de blocos é claramente menor que a lista dedocumentos e posições completa mostrada na Tabela 3. Mesmo ocupando pouco espaço,comparado com o índice invertido completo, com este índice não é possível processarconsultas sem apoio ou do texto ou de outra estrutura. Ele serve de apoio à buscadiminuindo a quantidade de páginas que serão veri�cadas.

Código Palavra-Chave Blocos Lista de Blocos1 aqui 1 22 balão 1 23 cai 2 2,34 caranguejo 2 1,25 da 1 16 do 1 37 enchente 1 18 maré 1 19 meio 1 310 minha 1 211 mão 1 212 na 2 1,213 no 1 314 não 2 1,315 ora 2 1,216 palma 1 117 peixe 2 1,218 pé 1 219 roda 1 220 salão 1 321 só 1 122 é 2 1,2

Tabela 6: Vocabulário exemplo com índice de endereçamento de blocos

3.1.6 Considerações Sobre As Estruturas Apresentadas

As estruturas apresentadas nos itens anteriores têm suas vantagens e desvantagens.Esta seção faz uma comparação super�cial destas estruturas utilizando como base o ar-tigo de Zobel [37] que mostra a comparação entre índices de arquivo invertido e arquivode assinaturas. No artigo são considerados os seguintes aspectos: espaço utilizado pela


estrutura, memória extra necessária durante o processamento, tempo de criação do ín-dice, tempo de atualização, escalabilidade, aspectos em relação a função de ordenamentoe extensibilidade da estrutura. Estes aspectos são considerados a seguir com um breveresumo comparativo entre as estruturas, conforme seguem:

• Espaço: Em 1981, Haskin estimou que o espaço ocupado pelo arquivo invertidoseria cerca de 50% a 300% do tamanho do texto indexado [38] mas com uso detécnicas atuais de compressão (Seção 3.3) o índice chega a ocupar aproximadamentede 6% a 10% do espaço do texto indexado pelo índice [39]. O tamanho de índice dearquivo de assinaturas chega a ocupar de 25% a 40% do espaço do texto indexadopelo arquivo de assinaturas [40, 41]. Para o índice de árvore de su�xos o aspecto deespaço utilizado é o que tem maior peso onde o tamanho do índice chega a ocuparde 120% a 240% do tamanho do texto [9]. Este aspecto torna inviável o uso destaestrutura, Entretanto, o uso de array de su�xos não é tão dispendioso, necessitacerca de 40% do tamanho do texto;• Memória: Um índice invertido utiliza memória extra para armazenar o vocabulárioque não necessariamente precisa estar em memória por ocupar pouco espaço, entre-tanto, normalmente o vocabulário é mantido em memória para evitar uma operaçãode leitura à disco extra a cada acesso às listas invertidas. O mesmo acontece paraa estrutura de array de su�xos, caso seja utilizada a estrutura auxiliar supra-indexpara armazenar o início das palavras indexadas no array de su�xos. De forma aná-loga, comparado com arquivo invertido, o supra-index funciona como o vocabulárioe pode ser armazenado em memória para evitar uma operação de acesso a disco amais. Já arquivo de assinaturas não necessitam de memória extra;• Tempo de Criação: Basicamente o tempo de criação em índices de arquivo in-vertido e arquivo de assinaturas são equivalentes, os procedimentos para construçãodos dois índices são semelhantes, ambos baseados em leitura e divisão do arquivo deentrada como o procedimento descrito na Seção 3.4.1. Entretanto, nos experimen-tos realizados por Zobel [37], o tempo de construção do arquivo invertido foi de 40

minutos, muito menor que os 86 minutos necessários para gerar o arquivo de assi-naturas para uma mesma base textual. Isto acontece basicamente por dois motivos.Primeiro o arquivo invertido tem a vantagem de precisar de menos espaço e comisso a quantidade de dados processadas é menor. E, segundo, arquivo de assinaturastem a desvantagem de precisar gerar várias vezes valores de hash durante a criaçãoque precisa de mais processamento comparado com operações de lookup em tabelas


realizadas na construção do arquivo invertido. Em relação ao array de su�xos, otempo de criação chega a ser de 5 a 10 vezes maior que o tempo necessário paracriar o arquivo invertido para mesma base [9];• Atualização: Atualização de índices invertidos é uma operação complexa, depen-dendo do nível de atualização que se procura, pode-ser utilizar um estrutura dinâ-mica para manipular o índice como uma B+-Tree(Seção 3.2). Entretanto, usandouma estrutura como esta geram novos overheads de espaço extra, pois, a propriaestrutura utiliza cerca de 67% espaço extra e gera também um tempo maior deleitura. Para a atualização de um arquivo de assinaturas e array de su�xos serianecessário também uma estrutura de B+-Tree. Mesmo assim, métodos de atualiza-ção do índice podem ser mais e�cientes quando são usados atualizações em batchescomo, por exemplo, usando técnicas descritas nas Seções 3.4 e 3.5;• Escalabilidade: Para uma consulta qualquer, o número de acessos ao disco nosíndices de arquivo invertido quanto e arquivo de assinaturas são independentes deescala, isto é, o custo assintótico de processamento do índice é a quantidade de dadosa ser transferida do índice. Entretanto, para arquivos de assinaturas, o custo deprocessamento é linear em relação ao tamanho do corpus sem levar em consideraçãoa consulta realizada. Em contrapartida, no arquivo invertido, o tamanho médio daslistas invertidas é sublinear em relação ao tamanho do corpus, já que a medida quenovos termos aparecem são criadas novas listas vazias para estes termos. De formaanáloga um array de su�xos os blocos que armazenam as entradas do array temcrescimento sublinear. Conseqüentemente, os índices de arquivo invertido e arrayde su�xos têm melhor escalabilidade que o arquivo de assinaturas;• Ordenamento: Para uma consulta qualquer, é utilizada uma função de ordena-mento para gerar um valor de relevância em cada documento do corpus em relação aconsulta. Então, os documento são ordenados em relação a este valor e são retorna-dos os melhores para o usuário. Neste aspecto, o índice invertido possui a vantagemda simplicidade, principalmente considerando a função de ordenamento baseada nocálculo de t�df (Seção 2.2). Neste aspecto, o array de su�xos têm vantagem de ofe-recer de forma inata informações necessárias para processamentos de consultas porfrase exatas e consultas por proximidades (Seção 2.4). Além disso, um array de su-�xos pode ser utilizado para realizar consultas por casamento aproximado diferentede arquivo invertido que precisa fazer um pré-processamento sobre o vocabuláriopara resolver este tipo de consulta[9];

3.2 Estrutura de Índice Dinâmico B+-Tree 30

• Extensibilidade: Basicamente, o arquivo de assinaturas pode ser visto como umaestrutura binária indicando que propriedades estão presentes ou não. Deste modo,este tipo de índice pode ser considerado menos extensível do que o arquivo invertidoe um array de su�xos. No arquivo invertido, pode-se adicionar propriedades extrasà estruturas agregadas a cada entrada na estrutura, como, por exemplo, a lista deposições (como mostrado na Seção 4.2.6) possibilitando processamento de consultaspor frases exatas ou por proximidade (Seção 2.4). De forma semelhante, pode-se adicionar informações extras às entradas no array de su�xos. Pode-se colocar,por exemplo, informações de como cada palavra está formatada no texto original(tamanho da fonte, se esta em negrito, itálico, etc).

Fundamentado nos aspectos evidenciados acima, a partir desta seção o arquivo in-vertido será usado como índice a ser estudado onde são descritas técnicas de construção,atualização e processamento de consultas sobre este índice. Esta escolha se baseia, prin-cipalmente, pelos fatores de espaço ocupado com uso de técnicas de compressão descritasna Seção 3.3, e também por sua simplicidade. Além disso, a estrutura de índice VIF des-crita no próximo capítulo que utiliza como base outros dois índices sendo um deles umaestrutura de arquivo invertido simples. Mais além, a estrutura do índice VIF se baseiaem uma B+-Tree(descrita na próxima seção) fundamentalmente por ser uma estruturadinâmica com o objetivo de oferecer atualização do índice de forma mais e�ciente.

3.2 Estrutura de Índice Dinâmico B+-Tree

B+-Tree [42, 43, 44] é uma estrutura dinâmica para índices baseada em árvore debusca criada com intuito de gerenciar dados armazenados em memória secundária. Aestrutura da B+-Tree se baseia numa árvore balanceada onde os nós internos direcionama busca e os nós folhas armazenam as entradas de dados. Cada nó contém no máximo D

entradas, onde este parâmetro D é chamado de grau da árvore ou a ordem da B+-Tree.O número de entradas M de cada nó varia entre D

2≤M ≤ D para todos os nós exceto a

raiz que pode armazenar 1 ≤ M ≤ D quando a árvore está vazia ou com poucos dados.Essa condição faz com que a ocupação mínima de 50% seja garantida.

Cada nó interno da B+-Tree inclui chaves de busca e ponteiros para outros nós, sendoque cada nó armazena M valores de chaves de busca (K1, K2, ..., KM) e M + 1 ponteiros(P1, P2, ..., PM+1). As chaves de busca dos nós internos servem apenas para guiar a buscapela árvore e os ponteiros indicam o endereço físico em disco onde se localiza o próximo nó.


Nos nós folhas são armazenadas M chaves de busca e para cada chave Ki é armazenadoum valor Di do dado associado a esta chave. Além disto, nos nós folhas existem ponteirosPP apontando para o próximo nó folha fazendo com que todos os nós folhas formem umaestrutura de lista encadeada facilitando a listagem seqüencial3. Estruturalmente os nósinternos e nós folhas são iguais como mostrado na Figura 10 apesar de um armazenarponteiros e outro armazenar dados. Na �gura são mostradas as estruturas do nó internoe folha para uma B+-Tree de grau 2.

Figura 10: Estrutura do nó da árvore B+-Tree de grau 2

3.2.1 Busca na B+-Tree

As operações de busca oferecidas pela B+-Tree são:

• Busca por um elemento: Onde dada uma chave K deve-se encontrar o nó onde achave se encontra e recuperar a entrada de dados associada à chave;• Busca por todos os elementos: Recupera uma listagem completa e ordenada de todosos elementos contidos no índice. Esta operação é executada fazendo uma busca peloprimeiro nó folha existente, i.e., o nó onde não existe nenhuma outra chave menorque a menor chave deste nó. Então, a partir deste nó, é feita uma leitura seqüencialna lista de todos os nós folhas usando os ponteiros de encadeamento entre folhas;• Busca por um intervalo de elementos: Nesta operação são passados dois argumentosnecessários A e B que são chaves especi�cando a fronteira da lista que será recupe-rada. Ao �nal serão retornados de forma ordenada todos os elementos onde a chavede busca do elemento esteja no intervalo [A, B] onde A ≤ B . Para isto faz-se umabusca na árvore pelo nó folha que contenha o primeiro elemento da lista, isto é, onó que contenha o menor elemento L existente no intervalo que satisfaça a condição

3algumas implementações adicionam um ponteiro para o nó folha anterior criando uma lista dupla-mente encadeada


L ∈ [A, B] e ∀i ∈ [A, B]•L ≤ i. a partir deste elemento se faz uma busca seqüencialna lista encadeada dos nós folhas de forma ordenada retornando todos os elementosE enquanto a condição esteja satisfeita(E ∈ [A, B]). Esta operação pode ser vistacomo uma generalização das duas buscas anteriores onde a primeira operação podeser modelada como uma busca onde A = B = K e a segunda operação uma buscaonde A = −∞ e B = +∞.

Estas operações de busca podem ser divididas em duas etapas: (a) uma busca nos nósinternos da árvore até encontrar o nó folha desejado e (b) uma busca seqüencial na listaencadeada dos nós folha (menos para o caso de recuperar apenas um elemento). Na buscapelo nó folha o procedimento recursivo da busca por um elemento de chave K tendo iníciono nó raiz é de�nido como:

• Caso Base: Se o nó atual for um nó folha a busca termina.• Indução: Se o nó atual for um nó interno com M chaves K1, K2, . . . , KM com

M + 1 ponteiros P1, P2, . . . , PM+1 deve-se encontrar o primeiro ponteiro para Pj talque K < Kj, caso K seja maior que KM então se deve usar o ponteiro de PM+1 econtinuar o procedimento recursivamente no nó �lho de ponteiro escolhido.

Desta forma, as chaves presentes nos nós internos servem como guias para encontraras folhas. No exemplo da Figura 10 existe apenas um nó interno que é a própria raíz.Neste nó existe uma chave apenas com o valor �E�. Esta chave indica que existem doisnós �lhos da raíz. Um nó cujo valores são menores que �E� e outro nó cujo valores sãomaiores ou igual a �E� com localização indicada pelos primeiro e segundo ponteiros daraíz, respectivamente P1 e P2.

3.2.2 Inserção na B+-Tree

A inserção de um elemento visa adicionar o elemento na estrutura de modo que semantenham as características de uma árvore balanceada. Uma inserção é feita em doispassos, o primeiro é encontrar f , o nó folha da árvore onde o elemento deve ser inserido.Para isto basta fazer uma busca como descrito na seção anterior. Com o nó em mãos,o dado deve ser inserido no nó. Quando o nó não está cheio então é feita uma inserçãosimples, basta adicionar o novo elemento na árvore no nó f , como ilustrado na Figura 11.

Caso ocorra um over�ow, isto é, o nó esteja no limite de sua capacidade, então seránecessário realizar uma operação de divisão do nó, que consiste em criar um novo nó vazio


Figura 11: Inserção simples em B+-Tree

v e distribuir igualmente as entradas do nó f mais a nova entrada que está sendo inseridaentre os nós f e v. Em seguida, deve ser inserido o ponteiro de v no nó pai de f com achave do primeiro elemento de v. Na Figura 12 a adição do elemento (D, 5) gera over�owem f , o ponteiro de v é inserido na raíz que é o pai de f . Além disso, o ponteiro dopróximo nó folha é atualizado em f , onde o novo nó v é inserido entre f e o nó apontadopor PP de f .

Figura 12: Inserção em B+-Tree com nó cheio

À medida que a árvore vai crescendo pode acontecer over�ow nos nós internos casoos nós estejam cheios. Nesse caso, deve-se realizar uma operação de divisão no nó interno(o pai de f). Este processo pode ocorrer recursivamente duplicando e inserindo novosponteiros no nó pai até que se encontre um nó interno que não esteja cheio. O pior casoda inserção acontece quando os nós internos e a raiz estão todos cheios, neste caso, aárvore é acrescida de um novo nível, um novo nó extra é criado e este nó passa a ser anova raíz da árvore como mostrado na Figura 13 com a inserção do elemento (G, 6) ocorreum over�ow na raíz quer é dividida sendo criado um novo nó interno e uma nova raízonde a raíz anterior passa a ser um nó interno comum.

3.2.3 Remoção na B+-Tree

Remoção em B+-Tree é a operação mais complexa e, muitas vezes, é simplesmenteignorada. A complexidade desta operação está em apagar dados sem quebrar as pro-

3.3 Compressão 34

Figura 13: Inserção em B+-Tree com nó interno cheio e aumento da profundidade

priedades de balanceamento da árvore. Por isto, na maioria das vezes, é utilizada umaabordagem mais simples onde o espaço utilizado pelos itens removidos são apenas libera-dos sem que seja feito o re-balanceamento da árvore a cada operação de remoção. Comoeste tipo de operação é pouco utilizada, o balanceamento da árvore sofre pouca modi�ca-ção com o tempo. Mesmo assim é aconselhado que a árvore seja reconstruída para evitarque o desempenho da árvore degrade demasiadamente.

3.3 Compressão

Mesmo com o crescente aumento na capacidade tanto de armazenamento de mídiassecundárias quanto de banda de transmissão de dados, muito esforço tem sido alocado nouso de compressão de dados. O problema de compressão não é novo, métodos de com-pactação têm sido inventados e reinventados ao longo dos anos. Um dos primeiros e maisconhecidos métodos de compressão de texto é a codi�cação de Hu�man [45] que usa idéiaque lembra o código Morse. Na codi�cação de Hu�man caracteres mais comuns são codi-�cados usando menos bits, enquanto caracteres que aparecem raramente são codi�cados

3.3 Compressão 35

com mais bits. Este método foi publicado nos anos 50 e permaneceu por décadas comouma das melhores técnicas de compressão existentes até o aparecimento, nos anos 70, dacompressão Ziv-Lempel [46] e codi�cação aritmética [47] com maiores taxas de compres-são. Estas duas técnicas usam compactação adaptável onde o texto é compactado comum modelo que é construído dinamicamente baseado no texto que está sendo codi�cado(Figura 14) e durante a decodi�cação o modelo é reconstruído simultaneamente com otexto que está sendo descompactado. O método Ziv-Lempel é rápido e obtém boa taxa decompressão com uso moderado de memória. Apesar da codi�cação aritmética ter muitoboa taxa de compressão o tempo de codi�cação e decodi�cação é lento [1].

Figura 14: Compressão de texto usando modeloAlgoritmos de compressão modernos como block sorting, LZW, PPM [1] chegam a

diminuir o espaço necessário para armazenamento de texto em até 25% do tamanhooriginal. Apesar desta economia de espaço, o custo agregado de codi�cação e decodi�caçãodo texto fazia com que compressão e processamento on-line de consultas fossem utilizadosde forma exclusiva. Entretanto, atualmente, técnicas de compressão especializadas têmsido fundamentais em sistemas de RI. Um fator para isto é que o aumento do poder deprocessamento das máquinas cresceu bastante enquanto o tempo de leitura e escrita emdispositivos de armazenamento secundário teve um crescimento inferior. Em engenhos debusca o tempo gasto é predominantemente em operações em disco e a CPU é normalmentesub-utilizada. Hoje em dia, e com o poder computacional das arquiteturas modernas, otempo de espera para recuperar um byte em memória está entre 12 e 150 ciclos de CPUenquanto uma leitura em disco precisa de 10.000.000 (dez milhões) ciclos de CPU. Essepoder de processamento latente pode ser usado com algoritmos de compressão. Alémdisso, o uso de compressão diminui a quantidade de operações necessárias na leitura emdisco com impacto sensível no tempo necessário para as principais operações em engenhosde busca, entre elas busca e construção do índice. Ou seja, a compressão traz economiade espaço utilizado e também traz economia de tempo de processamento [48, 49, 50].

A compressão pode ser usada tanto para armazenar o texto original compactado

3.3 Compressão 36

quanto também na compressão do índice. Existem várias técnicas de compressão, masapenas algumas se aplicam ao problema de Recuperação de Informação. Uma técnicaboa é aquela que oferece características de boa velocidade de codi�cação e decodi�cação,alta taxa de compressão, possibilidade de decodi�cação aleatória e não seja gulosa nouso do espaço em memória. Em Sistemas de RI, por armazenarem grande quantidade detexto, a economia é bastante signi�cativa. Para alcançar esta melhoria no desempenhoé necessário que o algoritmo de compressão escolhido seja e�ciente, de forma que nãodegrade o desempenho anulando o ganho de operações em disco. Dependendo do modelode compressão utilizado não haverá perdas, mas sim ganho de espaço e ganho de tempo deindexação e consulta. As próximas seções descrevem técnicas de compressão de índices.

3.3.1 Métodos de Compressão de Índices

Técnicas de compressão de índices têm os pré-requisitos de serem velozes e de con-sumirem pouco tempo de processador. Uma vantagem dos índices invertidos é o fatode serem estruturados de modo que as informações armazenadas são listas de númerosordenados. Esta característica possibilita armazenar apenas as diferenças dos números.Este método é chamado de codi�cação por diferenças ou codi�cação delta(∆) [1, 49]. Nafunção de codi�cação ∆ uma lista é armazenada mantendo-se o primeiro elemento originale para cada elemento seguinte de índice i (i > 0) o valor armazenado é a diferença entreo elemento i e o elemento i − 1. Esta transformação das listas é importante pois os va-lores armazenados serão menores como mostrado logo abaixo e, juntamente com uso dosmétodos que serão descritos nas próximas seções, aumenta a taxa de compressão, já que,na maioria destes métodos, quanto menor o valor do número, menos bits são necessáriospara armazená-lo.

Lista de ocorrência: (3, 7, 15, 16, 26, 34, 67, 197, 198, 199, 299).Codi�cação ∆ : (3, 4, 8, 1, 10, 8, 33, 130, 1, 1, 100).

3.3.2 Codi�cação com Quantidade Variável de Bytes

A codi�cação com quantidade variável de bytes (VBC) utiliza uma quantidade variávelde bytes para codi�car um número qualquer x. Nesta codi�cação em cada byte do códigogerado é reservado um bit (o primeiro bit) para indicar se o byte atual é o último byte ounão. Como cada byte armazena 7 bits são necessários d(log x)/7e bytes para armazenarx. A codi�cação gera os bytes do código seqüencialmente, para cada byte é atribuído o

3.3 Compressão 37

valor �0� para o primeiro bit indicando que existem mais bytes e o último byte é atribuídoo valor �1� para o primeiro bit para indicar que este é o último byte.

3.3.3 Codi�cação Elias

Os métodos de codi�cação de números Elias-γ e Elias-δ propostos por Elias [51] sãomodelos globais e não parametrizados para codi�cação de números usando uma quanti-dade variável de bits, bastante utilizados para compressão de índices invertidos [1, 49, 50].O código Elias-γ é de�nido como: para um número x qualquer, o código é dividido emduas partes, a primeira armazena o valor em unário para 1 + blog xc; na segunda partesão armazenados blog xc bits em formato binário para o valor de x − 2blog xc. A parteunária indica quantos bits são necessários para codi�car x e a segunda parte codi�ca x

em binário. O código unário utilizado para armazenar a primeira parte necessita de umnúmero variável de bits. Para armazenar um número qualquer y em unário são necessáriosexatos y bits onde para os (y − 1) primeiros bits é atribuído o valor �1� e o último bitrecebe o valor �0�. A codi�cação Elias-δ é semelhante, uma forma simples de de�nir ébaseada na de�nição de Elias-γ onde a primeira parte em vez de ser codi�cada em unárioé codi�cada usando a própria codi�cação Elias-γ. A codi�cação Elias-δ gera códigos mai-ores para números pequenos se comparado com os gerados por Elias-γ, entretanto paravalores grandes, por exemplo 1.000.000 (um milhão), os códigos Elias-δ são menores. ATabela 7 mostra os valores de 1 a 10 codi�cados usando codi�cação Elias-γ e Elias-δ comas duas partes do código gerado separadas pelo caracter �.�.

Número Unário Elias-γ Elias-δ Golomb (b=3)1 0 0 0 0.02 10 10.0 100.0 0.103 110 10.1 100.1 0.114 1110 110.00 101.00 10.05 11110 110.01 101.01 10.106 111110 110.10 101.10 10.117 1111110 110.11 101.11 110.08 11111110 1110.000 11000.000 110.109 111111110 1110.001 11000.001 110.1110 1111111110 1110.010 11000.010 1110.0

Tabela 7: Exemplo de codi�cação para números usando as codi�cações unário, Elias-γ,Elias-δ e Golomb (b=3)

3.4 Construção do Índice 38

3.3.4 Codi�cação Golomb

A codi�cação de Golomb [52, 50, 1] é um modelo de codi�cação que consegue melhortaxa de compressão e tem melhor tempo de decodi�cação que o método de Elias. Estemodelo é ótimo assumindo que o conjunto de documentos de um dado termo é aleatório.Os códigos gerados se adaptam à sua densidade de valores através de um parâmetro usadopara determinar o código emitido para um número. Este parâmetro pode ser global paratoda coleção ou local para uma lista invertida de um termo e normalmente é armazenadousando codi�cação Elias. Para codi�car um número inteiro x (x > 0) usando o métodode Golomb com um parâmetro b, primeiro é gerado o valor q + 1 em unário, onde q

é o quociente com q = bx−1bc; logo após a primeira parte é codi�cado o valor do resto

r = x−qb−1 em binário, usando ou blog bc ou dlog be bits. Para decodi�car o resto usa-seo valor t = 1 C ((log x) + 1)− b, onde (a C b) é a operação de deslocamento de b bits dea para a esquerda (left-shift). Depois de recuperar blog bc bits do resto, r é comparadocom t. Se r > t então é necessário ler mais um bit para r. A escolha do parâmetro b

pode ser feita de modo a minimizar o número de bits necessários na codi�cação de umalista. Para os casos onde a probabilidade de um valor particular z ser pequena, que é oque acontece para os valores de docid, então b é minimizado quando b = 0.69 ∗media(z)

[1]. Pode-se escolher uma aproximação global da média usando estatísticas do corpus, i.e.b = 0.69N.n

f. Neste caso o parâmetro b será global, utilizado em todas as listas, entretanto

parâmetros locais têm melhor taxa de compressão. O valor de b pode ser local em cadalista invertida de termo t, neste caso a aproximação da média é b = 0.69 N

dft.

3.4 Construção do Índice

O processo de construção visa gerar a partir de uma coleção de páginas um índiceinvertido. Este processo, que recebe o nome de inversão, é realizado em batch tendocomo entrada o conjunto com todos os documentos da coleção e gera como saída o índiceinvertido. O processo de inversão pode ser simples e e�ciente de forma ad-hoc gerando oíndice em memória usando algoritmos e estruturas de dados simples. Este processo ad-hocpode ser dividido em duas fases: primeiro é feito o parsing dos documentos extraindo ostermos e gerando o vocabulário e a lista de incidência em memória. O vocabulário podeser armazenado usando uma estrutura em árvore binária ou uma hashtable, enquanto alista de ocorrências é armazenada em memória utilizando uma estrutura de lista ligada.E, por �m, as listas em memória são compactadas e armazenadas em disco como ilustrado


em pseudo-código na Figura 15. Este tipo de inversão é útil apenas para coleções muitopequenas, pois é limitado em número de páginas pelo tamanho de memória disponível.Para coleções grandes é necessário um procedimento e�ciente para inversão de páginascomo os descritos nas próximas seções.Algoritmo 1Procedimento MemAdHocInv(C, N)Entrada: O corpus C, número de documentos no corpus NSaída: Arquivo invertido I, O Vocabulário V1. seja V ← ∅ o vocabulário vazio2. (∗ Fase 1: leitura e armazenamento das listas em memória ∗)3. para i← 1 até N4. faça seja D ← Ci o i-ézimo documento no corpus5. faça o parsing dos termos de D6. seja T o número de termos em D7. para j ← 1 até T8. faça seja t← Dj o j-ézimo termo do documento D9. seja fD,t a freqüência do termo t no documento D10. se t /∈ V11. então V ← V

⋃t

12. seja Lt a lista invertida do termo t13. adicione a entrada (D, fD,t) a lista Lt14. (∗ Fase 2: compactação e geração do arquivo em disco ∗)15. seja #V o número de termos no vocabulário V16. para i← 1 até #V17. faça seja t← Vi o i-ézimo termo no vocabulário V18. seja Lt a lista invertida do termo t19. compacte a lista Lt e armazene em I20.

Figura 15: Procedimento de inversão em memória - [1]

3.4.1 Construção Linear Baseada em Partições

Este procedimento é um processo de inversão com tempo de processamento linearbaseado no uso de memória [13]. A Figura 16 ilustra este processo que recebe como entrada(0. fase inicial) um arquivo com as listas de entradas de documentos e termos e executaem três passos. Primeiro é feita uma leitura completa do arquivo de entrada compostopela lista de tupla (docid, termid, freq) gerando em memória a tabela de controle e atabela de amostras (1. preparação). O Segundo passo divide o arquivo de entrada emvárias amostras. O objetivo é dividir o arquivo de entrada (2. divisão da entrada) em A

partes que possam ser carregadas usando o máximo de memória disponível R. O valor de


A depende de R, do número total de entradas do corpus f , e do tamanho de cada entrada.Cada entrada é composta por três valores numéricos inteiros, normalmente usando 4 bytespara representar cada inteiro, A é calculado pela fórmula A = 12f

R. O segundo passo gera

as A amostras onde cada uma armazena a parte do arquivo de entrada contendo todas aspalavras chaves de um intervalo �xo distinto. Cada intervalo é de�nido por dois códigosde termo termidi e termidf . Estes valores são escolhidos satisfazendo as condições dememória para cada amostra. O terceiro e último passo inverte cada amostra em memória(3. inversão de cada amostra) baseado na tabela de controle usando um algoritmo deordenação counting-sort descrito em pseudo-código no anexo A. A tabela de controlearmazena os índices de cada termo pré-calculados na fase inicial a partir do df de cadatermo. O resultado da ordenação de cada amostra é concatenado ao arquivo de índiceinvertido parcial. Ao �nal do processo este arquivo será o índice invertido �nal e completo.O tempo de execução de cada passo é linear em relação ao tamanho da entrada, e oprocesso �nal também é linear em vários passos.

3.4.2 Multi-way In-place Merge

Um problema da inversão linear é a necessidade de usar espaço temporário propor-cional ao corpus. Outro tipo de inversão existente que não usa espaço em disco extraé o multi-way in-place merge [1]. A idéia básica do processo é a mesma idéia de umaordenação com união (merge-sort). No caso, o arquivo de entrada é dividido em váriasamostras pequenas que ou contém apenas um elemento ou poucos elementos que podemser invertidos em memória. Estas amostras são unidas (merge) em outras maiores atéque no �nal reste apenas o índice completo e totalmente invertido. Um merge simples éaquele onde há a união por duas vias ou 2-way merge. Neste caso as amostras são unidasde duas em duas até que haja apenas uma onde são necessários log2 A leituras do arquivotemporário, onde A é o número de amostras no passo inicial. A forma mais geral é ochamado merge de múltiplas vias ou multi-way merge onde cada união é realizada com M

amostras. Deste modo, o número total de leituras seqüenciais no arquivo de entrada serálogMA. A escolha do parâmetro M depende da limitação da máquina tanto em memóriaquanto em disco, i.e., o valor de M é limitado em quantos bu�ers podem ser alocadosconsiderando o total de memória física disponível na máquina e também é limitado naquantidade de arquivos que podem ser manipulados simultaneamente.

O procedimento completo é realizado da seguinte forma, primeiro os documentos dacoleção são lidos seqüencialmente e é feito o parsing em memória gerando o arquivo de


Figura 16: Procedimento de inversão linear

amostras comprimido em blocos seqüenciais. Nesta fase inicial o arquivo de amostras con-terá as entradas de tuplas (termid, docid, freq) dos documentos da amostra. No segundopasso é feita a ordenação de cada amostra onde cada amostra é carregada em memória eordenada e o resultado será um pequeno índice invertido para os documentos presentes naamostra armazenado de volta no arquivo de amostras. O terceiro passo é fazer o mergedos blocos do arquivo temporário. Este merge é realizado com leitura seqüencial de cadaamostra. Para isto, são mantidos em memória os bu�ers de cada amostra com a parte queestá sendo atualmente processada. Inicialmente cada bu�er armazena o primeiro bloco daamostra, o bloco de rótulo bloco1 de cada amostra na Figura 17. O processamento é reali-


Figura 17: Procedimento de inversão via multi-way in-place merge

zado sobre os bu�ers que são consumidos durante o processo, a cada iteração é escolhidaa menor entrada (a próxima entrada) que irá para o bu�er de saída. Esta entrada é esco-lhida e�cientemente usando-se uma estrutura de �la de prioridade em memória descritano anexo B. Enquanto as amostras vão sendo processadas, os bu�ers são consumidos esão atualizados com os próximos blocos da amostra. Neste momento, os blocos antigosnão são mais utilizados e podem ser descartados. Então, o endereço do bloco inutilizávelé adicionado à tabela de blocos. Quando o bu�er de saída é totalmente preenchido eleé descarregado em disco em um bloco físico de uma amostra que já foi descartado databela de blocos. A Figura 17 ilustra um momento durante o processamento mostrando areutilização do espaço em disco, onde, no instante do processamento mostrado na �gura,os blocos marcados com �*� do próprio arquivo de amostras são usados para armazenar oíndice invertido. Ao �nal do processo, quando todos os blocos de amostra forem consumi-dos, o espaço �temporário� do arquivo de amostras é o espaço ocupado pelo índice. Esteprocedimento de reutilização de blocos garante a característica in-place do processo.

No �nal do passo de merge, o arquivo de amostras contém o índice invertido. Entre-tanto, os blocos que formam o índice estão dispersos no arquivo. Então, por �m, o últimopasso organiza os blocos do arquivo baseado na tabela de blocos que foi gerada em memó-ria contendo a ordem de escrita dos blocos em disco. Este passo de merge talvez preciseexecutar várias vezes, isto depende dos valores A e M , como dito antes serão necessárioslogM A merges. O valor de M já foi discutido, mas o valor de A não. Para A é preferível

3.5 Atualização 43

que cada amostra contenha o máximo de documentos possível fazendo com que A sejamenor, então, de forma análoga ao procedimento de inversão linear A é calculado usandoo máximo de memória disponível A = 12f

R.

3.4.3 Construção em Pipeline

A construção em pipeline visa utilizar de forma e�ciente os recursos de disco, CPUe rede das máquinas diminuindo o tempo em que estes recursos �cam ociosos durante aconstrução do índice. O método proposto por Melnik [53] divide o processo de construçãoem três etapas: L - carga de dados, P - processamento e E - descarga de dados. Umaconstrução sem uso de pipeline cria um índice a partir de varias seqüências de operações L,P e E. Como cada uma destas operações utiliza recursos distintos e independentes (con-siderando que os dados são carregados da rede e descarregados em disco) estas operaçõespodem ser executadas em paralelo diminuindo o tempo de processamento �nal.

3.5 Atualização

A atualidade do índice é uma medida de peso de um engenho de busca. O dinamismoda Web faz com que o índice sofra alterações constantes. Existe um problema inato naatualização dos índices para um repositório como a Web que é a quantidade de dados o quetorna o problema não trivial. Vários sistemas fazem a atualização do índice simplesmenteconstruindo um novo e o colocando no lugar do antigo. Entretanto, esta solução podeser muito custosa. Esta seção lista métodos para tratar do problema de atualização doíndice.

A Web está sujeita a alterações, entre elas, as principais são:

• Inserção: Quando um novo documento é adicionado. Um documento novo é inse-rido no corpus sendo atribuído um novo docid para este documento;• Remoção: Quando um documento é removido. Neste caso o seu docid se tornainválido. Caso o sistema sofra muitas remoções com o tempo, vários valores dedocid se tornarão inválidos gerando janelas de valores de docid que nunca serãopreenchidas nas listas de ocorrências tendo impacto direto na compressão do índice;• Atualização: Quando o conteúdo do documento é atualizado. Este tipo de ope-ração é comumente implementada com uma operação de remoção seguida de umainserção;


• Mudança: Quando a localização do documento é alterada e o documento é movidopara outro endereço. Este tipo de operação normalmente é tratado como umaremoção seguida de uma inserção usando a nova localização.

Cada operação de atualização gera várias outras alterações no índice. Cada termopresente em um documento alterado acarreta em uma das seguintes alterações no índiceinvertido:

• Adição: Esta operação insere um documento novo no �nal de uma lista invertida;• Inserção localizada: Equivale à adição de um documento a uma lista invertida.Esta operação acontece quando um documento é atualizado e no seu conteúdo apa-recem termos que já estão no índice invertido;• Atualização: Quando um termo reaparece em um documento modi�cado então aentrada do documento na lista invertida deve ser atualizada;• Remoção: Esta operação remove uma entrada de documento de uma lista inver-tida. A remoção pode fazer a lista �car vazia, no caso, o sistema pode ou removera lista ou manter a lista vazia. Este tipo de operação pode acontecer quando umdocumento é apagado ou também quando é atualizado e um dos termos foi removidodo documento.

3.5.1 Atualização Incremental sobre B-Tree

Cutting e Pedersen [54] descrevem uma estrutura otimizada para operações de in-cremento usando uma B-tree. No seu trabalho eles usam uma B-Tree para armazenar ovocabulário e os ponteiros para as listas invertidas que são armazenadas em uma estru-tura auxiliar chamada de posting �le. Eles descrevem a técnica chamada merge-updateonde citam que o uso de memória como bu�er ao invés de ser usada exclusivamente paracache diminui signi�cativamente a quantidade de operações em disco necessárias paraatualização. Outra otimização é a técnica de pulsing que visa diminuir o espaço utili-zado armazenando parte das entradas das listas invertidas na própria B-Tree, isto é feitousando os blocos da B-Tree para armazenar as entradas que estão para ser inseridas, sendoque é usado um parâmetro t para indicar a quantidade de entradas que são atualizadasdiretamente na B-Tree, quando t é alcançado, ou seja, para uma lista invertida qualquer


t entradas da lista estão armazenadas no bloco da B-Tree, então estas entradas são ar-mazenadas no posting-�le. Além disso, os autores ainda citam outras técnicas utilizadasvisando economia de espaço que são a codi�cação delta e a codi�cação VBC.

Brown [36] propõe uma técnica para gerenciamento de listas invertidas com tempode atualização proporcional ao tamanho do texto atualizado. No seu trabalho, as listasinvertidas grandes são tratadas de forma diferente das listas pequenas. Entre os motivosseguem que é veri�cada a distribuição de Zipf sobre as listas invertidas onde 10% das listasocupam 90% do espaço do índice e também que estas listas têm alta probabilidade deserem recuperadas durante o processamento de consultas. A principal modi�cação feitana estrutura de arquivo invertido é que cada lista invertida é armazenada em uma lista deblocos de tamanho �xo variando de tamanho entre 16 e 8192 bytes. Quando uma lista écriada um bloco de 16 bytes é alocado para esta lista, e quando esta lista �ca cheia entãoum novo bloco com o dobro do tamanho é alocado, o conteúdo da lista é copiado para estenovo bloco e o bloco anterior é liberado. Quando este bloco chega ao tamanho máximo(8192 bytes) então um novo bloco de tamanho máximo é alocado e é encadeado comouma lista com o bloco anterior. Além disso, há três tipos de gerenciamento de blocos. Osblocos de tamanho máximo são manipulados usando um segmento físico próprio chamadode large object pool. Os blocos de menor tamanho, blocos pequenos de 16 bytes, sãoarmazenados em blocos físicos de 4KB de tamanho com 255 blocos em cada bloco físicoonde estes blocos são armazenados em um segmento próprio chamado de small objectpool. E os demais blocos são armazenados em blocos físicos de 8KB onde cada blocofísico armazena blocos de um mesmo tamanho e contém tantos blocos quantos couberemno segmento. Estes segmentos são armazenados em um segmento de disco chamado demedium object pool. Deste modo a estrutura é otimizada para operações de incrementoonde novas páginas são adicionadas às listas pré-existentes deixando a maioria das listasanteriores sem serem tocadas durante o processo de atualização. Nos artigo Brown mostraque além manter a taxa de atualização constante por documento inserido, ele a�rma queo uso de batches grandes é mais e�ciente que atualizações de poucas páginas, pois o custode leitura dos segmentos é amortizado com a união de documentos onde as entradas deum mesmo termo são acumuladas para atualização seqüencial.

3.5.2 Atualização em Tempo de Consulta

As técnicas de atualização descritas na seção anterior estão focadas em sistemas comincremento de páginas onde existe apenas a operação de adição de novas páginas. En-

3.6 Processamento de Consultas 46

tretanto, o dinamismo da web é um desa�o maior, o estudo de Cho e Garcia-Molina [19]modela o comportamento de modi�cação das páginas baseado em experimentos onde fo-ram coletadas informações indicando que 50% das páginas sofrem alteração em um períodode uma semana. Enquanto isso várias páginas continuam sem serem modi�cadas, isso semcontar com as páginas que são removidas. Normalmente os engenhos de busca mantêmsua base atualizada de forma discreta, fazendo atualizações completas das páginas emperíodos de tempo �xos.

Chiueh [55] propõe uma estrutura de índice com atualização em tempo de consulta.A idéia principal da estrutura é manter um bu�er em memória com as entradas que estãosendo atualizadas e fazer com que as consultas sejam processadas usando informaçãodeste bu�er e do índice. O sistema deve se preocupar em controlar o acesso concorrenteao índice realizado simultaneamente pelos usuários que estão fazendo consulta ao sistemae o crawler que vive continuamente atualizando o índice.

Com o uso do bu�er as operações de atualização em disco são postergadas e realizadasde forma ordenada, amortizando o custo total. Entretanto, o uso de bu�er acaba setornando o ponto crítico da performance do sistema de modo que, dependendo da cargade atualização, o sistema não consiga lidar com altas taxas de modi�cação de páginas.

3.6 Processamento de Consultas

Até agora foram descritas apenas a estrutura e técnicas de geração e atualização deíndices invertidos deixando de lado o processo da busca. Vários tipos de consultas podemser implementados e�cientemente usando índices invertidos, entre eles consultas booleanassimples, consultas booleanas estendidas, consulta por proximidade.

3.6.1 Processamento de Consultas Booleanas

O processamento de consultas visa recuperar documentos que satisfazem uma consultae classi�cá-los em ordem de relevância para serem mostrados ao usuário. Esses são os doisaspectos por trás do processamento de consultas.

Para que uma cnnsulta seja processada usando um índice invertido, primeiramente,é feita uma busca no vocabulário para encontrar os termos presentes na consulta. Dovocabulário também são retornados o valor do df e o apontador da lista invertida de cadatermo. Com estes valores em mãos é feita uma busca nas listas invertidas para resolver


a expressão booleana formada pela consulta. Isto pode ser feito, basicamente, de duasmaneiras: (a) por ordem de termo: é quando o processamento é realizado para cada termoda consulta por vez e (b) por ordem de documento: quando a consulta é processada emordem de documento que satisfazem a expressão booleana da consulta. Processar umaconsulta por ordem de termo, pode ser até e�ciente dependendo da consulta, mas, naprática, não é viável e, as vezes, requer que a lista invertida de cada documento sejaarmazenada em memória. Mesmo fazendo otimizações no processamento, como recuperarlistas invertidas com menor df primeiro, não garantem que a memória será su�ciente[1]. O processamento por ordem de documento (b) é realizado com a união das listasinvertidas dos termos presentes na consulta que geram os documentos que satisfazem aconsulta, um por vez, e o adicionam ao conjunto de documentos do resultado da consulta.O processamento da consulta, em ambos os casos, é realizado usando a árvore sintáticada expressão booleana da consulta. O �uxo da ordem de processamento, ou por termosou por documentos, não interfere no resultado, apenas no tempo de processamento.

A segunda etapa do processamento é classi�car os documentos recuperados. Isto éfeito a partir de um valor de peso atribuído a cada documento do conjunto de respostasda consulta, que é calculado durante o processamento por uma função de ordenamento.Esta função pode ser a função de cosseno do ângulo ou outra como as mostradas na Seção2.2.

Figura 18: Processamento de consulta booleana

3.6.2 Processamento Rápido de Consultas

O tempo de processamento de consultas é uma medida fundamental em um engenhode busca. Os usuários não costumam esperar pela resposta. Grande parte das consultasrealizadas em um engenho de busca já �cam armazenadas em cache.

No trabalho de Mo�at [56] é descrito o conceito de skip-lists onde são adicionadosponteiros entre as entradas do índice que são usados para evitar decodi�cação de todas as


entradas. Durante o processamento de consulta quando é feito merge das listas inverti-das dos termos da consulta podem acontecer casamentos incorretos e estes ponteiros sãousados para identi�car quando um bloco de entradas não precisa ser decodi�cado econo-mizando tempo no processamento. A desvantagem do uso de skip-lists é o aumento doíndice causado pela adição desses ponteiros. Entretanto, este aumento é aceitável. Outratécnica é o uso de blocos de tamanho �xo [37] que possibilita a descoberta de entradas deforma mais e�ciente usando uma busca binária entre os blocos com o custo de adicionarespaço extra desperdiçado pelos espaços vazios no �nal dos blocos.

Outra técnica citada [1] é o processamento usando �la de prioridade armazenando osdocumentos de maior peso de relevância. Esta técnica altera o algoritmo de processamentoe não modi�ca nada no índice. O algoritmo de processamento é modi�cado de modo aevitar gerar um conjunto com todos os documentos que satisfazem a consulta duranteo processamento selecionando apenas os mais relevantes. Dependendo da consulta, oresultado pode produzir um conjunto de resposta bastante grande de modo que sejaimpraticável gerenciá-lo, por exemplo, no repositório do engenho Radix utilizado nostestes descritos na Seção 4.5 com 11 milhões de páginas apenas o termo �brasil� apareceem cerca de 3 milhões de documentos onde seriam necessários 22MB em memória paraarmazenar a lista descompactada para apenas este termo. A �la de prioridade armazenaos H documentos com maior relevância ordenados pelo menor de modo que, entre estes, odocumento com menor relevância é facilmente recuperado. Esta �la é atualizada duranteo processamento a partir dos documentos que são lidos e, ao �nal do processamento, a �lacontém os H documentos com maior peso de relevância que são retornados ao usuário.Este limite pode estar em torno de 100 ou 1000 itens sem afetar ao usuário, já que, amaioria dos usuários (85,2%) visitam apenas os primeiros 10 itens de resposta [57].

Outra forma de realizar processamento e�ciente é organizar as listas invertidas doíndice ordenadas em relação ao peso de relevância [37]. Desta forma, consultas simples oubooleanas simples são processadas rapidamente apenas lendo o início das listas invertidas.Entretanto, para resolver consultas mais complexas como frase e proximidade devem serrealizados operações mais complexas fazendo a checagem de listas de posições, de modoque para estes tipos de consultas o custo do processamento se torna maior.

3.7 Considerações �nais 49

3.7 Considerações �nais

Este capítulo descreve estruturas utilizadas em sistemas de recuperação de informaçãoe técnicas aplicadas a índices invertidos que servem de base para o trabalho resultado destadissertação descrito no próximo capítulo (Capítulo 4) onde são utilizados os métodos decompressão de índice, as técnicas de criação e atualização do índice e processamento deconsultas observados neste capítulo.

50

4 Especi�cação do VIF

Este capítulo descreve a estrutura de dados para índice invertido VIF - Vertical In-verted File. O VIF foi elaborado para ser utilizado no engenho de busca Radix tendocomo objetivo oferecer uma API (Application Programming Interface) de gerenciamentodo índice capaz de manipular e oferecer acesso aos dados de forma e�ciente.

Inicialmente, a Seção 4.1 descreve um resumo do problema atacado pelo projeto im-plementado nesta dissertação. Em seguida, a Seção 4.2 aborda a arquitetura do engenhode busca Radix descrevendo os principais módulos e os processos de busca de indexaçãoimplementados no sistema, e, em seguida, é descrita a estrutura de índices utilizada pre-viamente pelo sistema. Na seqüência, segue a especi�cação do trabalho proposto nestadissertação, a estrutura de índices VIF (Seção 4.3). Na Seção 4.4 são mostrados detalhesdo projeto e da implementação do índice VIF. Por �m, na Seção 4.5, são descritos osexperimentos e testes de veri�cação e os resultados obtidos.

4.1 Descrição do Problema e Objetivo

A Web é um repositório de documentos com características únicas, entre elas o di-namismo e a grande quantidade de dados (Seção 2.3). Estudos indicam que 23% daspáginas na Web são modi�cadas todos os dias (Seção 2.3.2) e existem poucos estudos naárea especí�cos para tratar deste problema. O VIF visa atacar estes dois problemas de�grandeza� e dinamismo oferecendo uma estrutura que utilize técnicas de compressão deíndices e também uma forma de atualização dinâmica baseada em uma B+-Tree.

O VIF é um índice implementado para incorporar o engenho de busca Radix comobjetivo de �resolver� estes problemas, principalmente o de espaço utilizado. No engenhoRadix, como descrito na próxima seção utiliza dois índices chamados IF e PL que temcusto muito elevado de espaço, onde para uma base de 11 milhões de páginas chegam aocupar 35.1 GB de disco (Tabela 11).

4.2 Arquitetura do Radix 51

4.2 Arquitetura do Radix

A arquitetura do Radix segue um modelo semelhante ao descrito na Seção 2.1.3.Nesta dissertação é exposto apenas a arquitetura centralizada do sistema, sem entrarem detalhes da distribuição do engenho de busca descrita nos trabalhos de Rocha [58] eFernandes [59]. Na Figura 19 estão descritos os módulos presentes na arquitetura com asligações representando a tramitação de dados entre os módulos.

Figura 19: Arquitetura Básica do Engenho de Busca Radix

A arquitetura do Radix é formada por dois módulos principais: (i) o módulo de buscaque é responsável por processar as consultas dos usuários do sistema e (ii) o módulo deindexação que gerencia a base de índices do sistema catalogando as páginas da Web eatualizando o índice de busca.

Na camada de dados existem basicamente duas bases, uma para indexação e outrapara busca onde existem quatro estruturas utilizadas pelo processo que são:

• índice: é o próprio índice invertido usado no processamento de consulta;


• página: é a estrutura que armazena os dados com informações da página. Estasinformações contêm dados mostrados para o usuário que são retirados dos documen-tos durante a indexação como o título do documento, um parágrafo descrevendo oconteúdo do documento, as datas de criação e última modi�cação do documento, otamanho do documento em bytes;• centróide: esta estrutura é um índice para acesso ao centróide do documento. Ocentróide é um vetor com todos os termos que estão presentes no documento. Esteíndice é utilizado na atualização de páginas;• função: é a estrutura que armazena os dados referentes ao componente de funçãode termos e de urls (Seção 4.2.2).

4.2.1 Módulo de Busca

O módulo de busca do Radix é dividido em componentes onde cada um é responsávelpor gerenciar vários aspectos diferentes no engenho como apresentação, distribuição, cachede resultados, agrupamento, etc. Estes componentes (desenhados na Figura 20) podemser divididos em camadas de acordo com o �uxo de dados. Inicialmente existe a camadade apresentação que interage diretamente com o usuário, nesta camada estão o Servlet,o Search, o Console e o FacadeSearch. Em uma instância do sistema existe apenas umna camada de apresentação (dentre estes citados), sendo que normalmente é utilizado oServlet que é responsável por fazer a interação com o usuário usando um navegador webvia requisições http. Este componente sempre acessa diretamente um FacadeSearch queé responsável por receber a consulta no servlet e transformá-la em uma representaçãointerna para ser processada na próxima camada, a de negócios, e também é responsávelpor recuperar informação textual da resposta gerada nesta camada.

É na camada de negócios onde estão de�nidas as regras de distribuição, de gerenci-amento de cache, de agrupamento de respostas e de coleta de dados. Os componentespresentes nesta camada e suas características estão listados na Tabela 8. Todos eles im-plementam uma interface CoreSearch que é utilizada pelo FacadeSearch para acessar acamada de apresentação. Mais detalhes da arquitetura de busca do engenho estão descri-tos em [58].

As estruturas descritas nesta dissertação estão presentes apenas na camada de dados.Existem dois componentes nesta camada que são Storage e DataCoreSearch. O primeiroé acessado no FacadeSearch para recuperar informação que é mostrada para o usuário a


Figura 20: Componentes do módulo de busca do Radix [58]Componente CaracterísticaDataCoreSearch Processamento consulta no índiceCachedCoreSearch Gerenciamento de cache de resultadosRouterCoreSearch Gerenciamento do acesso a bases replicadasGroupCoreSearch Agrupamento de respostas de bases distintasRemoteCoreSearch eRemoteCoreServer

Distribuição do processamento de consultasCoreSearch Interface de entre camada de negócios e apresentação

Tabela 8: Componentes de busca e suas características

partir de um resultado de consulta retornado por um CoreSearch. Como resultado dapesquisa de um CoreSearch são retornados apenas valores de docid para os documentos.A partir destes docids o Storage recupera dados, como por exemplo, a string do endereço,o título da página, o tamanho da página, entre outros.

O DataCoreSearch é responsável por realizar o processamento lógico da consultausando o índice da base de busca gerando o resultado da consulta ordenado por rele-vância.

4.2.2 Função de Termos e de Urls

As Funções de termos e de urls são os dois componentes do sistema que fazem omapeamento entre palavra-chave e termid (e vice-versa) e entre url e docid (e vice-versa)


respectivamente. Ambos os componentes são implementados de forma equivalente. Cadaum gerencia um repositório local com o mapeamento entre uma string e um número. Cadavez que um string é solicitado ao componente este retorna o valor associado à string (aotermo para a função de termos e à url para a função de urls). Caso essa string não existano repositório, o componente gera um novo identi�cador para a string, armazena o novomapeamento no seu repositório e retorna o novo identi�cador. Estes dois componentestrabalham independentes do sistema executando em um processo servidor, eles são usadosdurante a indexação para gerar identi�cadores de termos e de urls. Esses dois componentespodem ser compartilhados entre duas ou mais instâncias do sistema. A vantagem dessescomponentes para a busca é a possibilidade de realizar agrupamento de respostas de duasinstâncias de forma e�ciente, visto que, quando o domínio dos mapeamentos entre urlse termos em docid e termid são compartilhados entre as duas ou mais instâncias entãonão há necessidade de recuperar o endereço para descobrir se dois itens de resposta sãoequivalentes para eliminar as redundâncias durante o agrupamento processado usandoapenas o índice.

4.2.3 Módulo de Indexação

O Módulo de indexação no Radix é composto por crawlers, Servidor de Indexaçãoe servidor de links. Os crawlers são responsáveis por coletar as páginas na Web fazera análise sintática dos documentos e gerar o objeto Página que contém a representaçãointerna do documento HTML. O objeto página é composto pelos atributos: a url dodocumento, o título da página, um parágrafo descrevendo o conteúdo do documento, aspalavras-chave com o peso associado a cada palavra, a lista de posições de cada palavrado documento, e a lista de links apontados pelo documento.

Os robôs enviam os objetos Página para o servidor de indexação que é responsável porarmazenar as páginas no repositório do sistema. Os dados relativos a cada documento sãoarmazenados em arquivos de transação. Estes arquivos contêm os dados que devem seradicionados ao índice de busca para incorporar os documentos indexados. Estes arquivosde transação são usados no processo de Release para atualizar o índice de busca. Alémdisso, o servidor de indexação envia os links do documento para o servidor de links queé o componente responsável por manter as listas de endereços de páginas que devem serenviados aos robôs. O servidor de links gerencia o que está sendo indexado pelo sistemaidenti�cando urls de documentos novos e documentos para serem atualizados e tambémcontrolando o agendamento das urls fazendo o rodízio de servidores.


4.2.4 Atualização de Base

O processo de atualização de base (Release) é responsável pela atualização da base debusca a partir dos dados que foram catalogados pelo módulo de indexação. Este processoexecuta de forma esporádica gerando um novo índice para ser usado pelo módulo de busca(normalmente a atualização é feita uma vez por semana). Este processo faz uso intensivode disco e CPU para gerar o novo índice.

4.2.5 Estrutura IF

A estrutura da dados usada no Radix é um índice invertido simples chamado de IF(Inverted File) com granularidade no nível de documentos, onde as listas invertidas sãoarmazenadas seqüencialmente em dois arquivos: um arquivo if.index que armazena osponteiros dentro do arquivo de dados para as listas invertidas de cada termo; e o arquivoif.data contendo todas as listas invertidas armazenadas em formato ASCII com caracteresseparadores de números. Cada lista invertida de um termo armazena no início o própriotermid do termo em questão seguido do caracter separador de dois pontos (�:�) e do valordo dftermid. Em seguida é armazenada a lista de todos os docid e freq das páginas da listainvertida separados por um caracter de vírgula (� ,�) em ordem crescente de docid. Cadaentrada de docid e freq é separada com o caracter do símbolo igual (�=�) como mostradona Figura 21.

Figura 21: Estrutura IF

4.2.6 Estrutura PL

A estrutura PL (Position List) é um índice auxiliar utilizado durante o ordenamentopara recuperar a lista de posições de cada docid da resposta possibilitando o processamentode consultas baseado em proximidade dos termos (Seção 2.4). O PL armazena todas asentradas de duplas (termid, docid) e a lista de posições (pltermid,docid) em dois arquivos. Oarquivo que armazena os dados é chamado de pl.data onde �cam armazenados os blocos


com as entradas PL. Cada bloco armazena um número �xo de entradas contínuas. Aestrutura interna do bloco é formada por um cabeçalho mais as entradas do PL, e éilustrada na Figura 22. No cabeçalho é armazenado o número de entradas do bloco (valore) e o intervalo de cobertura. No exemplo o valor de e é �xo para todos os blocos excetopara o último que armazena menos entradas. O intervalo de cobertura do bloco são duasduplas (termid, docid) especi�cando os limites inferiores e superiores do bloco. No PLas entradas são armazenadas em formato binário usando uma codi�cação com númerovariável de bytes bastante semelhante à codi�cação VBC (Seção 3.3.1). Este arquivo deblocos é indexado por uma B-Tree, ilustrado como a estrutura pl.btree na Figura 22. EstaB-Tree é utilizada para encontrar o bloco de uma entrada qualquer. Ela armazena pares(intervalo, ponteiro) onde o intervalo é o mesmo intervalo que identi�ca um bloco e oponteiro é o valor que aponta para o início do bloco no arquivo pl.data.

Figura 22: Estrutura PL

4.2.7 Atualização dos Índices IF e PL

No Release, os processos de atualização dos índices IF e PL ocorrem de forma distinta,apesar de serem tratados de forma equivalente pelo módulo de indexação. Durante aindexação, o servidor de indexação gera os arquivos de transação chamados de if.trans epl.trans armazenando um pequeno índice IF e PL, respectivamente, cada um com umapequena quantidade de documentos. Estes arquivos são resultado da inversão em memóriados documentos indexados descarregados em disco para serem usados posteriormente comoentrada para o processo de release.

O procedimento do release funciona da seguinte maneira. Para os arquivos do IF, orelease é realizado em dois passos. Primeiro é feita a união de todos os arquivos if.transgerando um índice IF �mediano�. Este índice é resultado do que foi catalogado pelo módulode indexação no período entre o release corrente e o último release processado. O segundo

4.3 Especi�cação VIF 57

passo faz a união entre este arquivo �mediano� e o índice corrente de busca gerando o índiceIF �grande� com o resultado �nal contendo o índice para todas os documentos catalogadospelo sistema.

A construção do PL é realizada de outro modo. Os arquivos de transação do PLsão guardados todos juntos em um mesmo repositório e o processo de release gera porcompleto um novo PL a cada atualização de base. Isto é feito unindo todos os arquivospl.trans existentes.

O processo de release também lida com atualização e remoção de documentos. NoPL isto é feito simplesmente removendo as entradas anteriores do arquivo de transaçãoantigo e, no caso de atualização, armazenando as novas entradas como se fosse umainserção normal. Para o IF, a atualização é realizada adicionando entradas que devem serremovidas no IF anterior e entradas que devem sobrepor as entradas antigas.

4.2.8 Processamento de Consultas no IF e PL

O processamento de consultas usando os índices IF e PL é realizado em duas etapas.Para uma consulta qualquer, primeiro é feito o processamento lógico da consulta pararecuperar os documentos. Este processamento é realizado usando o índice IF. Nesta faseuma consulta booleana é processada gerando o conjunto com as entradas de (docid, peso)que satisfazem à consulta, onde peso é o valor de peso de ordenamento baseado no tfidf

descrito na Seção 2.2.4. Este primeiro passo resolve as consultas booleanas simples.O segundo passo acontece apenas para consultas por proximidade (Seção 3.6). Neste

passo é usado o índice PL para identi�car a lista de posições para cada termo presente naconsulta. Para cada docid no conjunto de resposta gerado no passo anterior é calculado umnovo valor de peso agora baseado na proximidade dos termos da consulta no documento.

4.3 Especi�cação VIF

O VIF (Vertical Inverted File) é uma estrutura de arquivo invertido com granularidadeno nível de termos, compactada e com estrutura dinâmica organizada sobre uma B+-Tree.Além disso, o VIF oferece uma API de processamento de consultas e de atualização egeração do índice.

O índice VIF é dividido em 3 estruturas. A primeira é o arquivo de dados vif.dataque armazena todas as entradas VIF. Este arquivo pode ser visto como uma seqüência


contínua de entradas VIF em ordem crescente. Este arquivo é indexado pela segundaestrutura a vif.btree que é uma B+-Tree responsável pelo gerenciamento da disposiçãodos blocos com as entradas no arquivo de dados. E a última estrutura é o vif.df que é oarquivo que armazena os valores de df de todos os termos.

Os dados armazenados no VIF são entradas de tuplas (termid, docid) associadas como valor de peso, pesoi,j, que é um valor atribuído em tempo de indexação pelos robôs paracada palavra-chave, e mais a lista de posições (pl) onde cada palavra ocorre no documentocomo descrito na Tabela 9.

Valor Descriçãotermid Identi�cador de palavra-chave

docid Identi�cador de documentopesotermid,docid Peso do termo no documento

size Número de vezes que o termo ocorre no documentopl Lista de posições do termo no documentoTabela 9: Atributos de uma entrada VIF

Basicamente o VIF contém a mesma informação de um índice PL. A diferença é oatributo peso que não existia no PL. Este atributo equivale ao mesmo atributo presenteno IF de peso de relevância de um documento em uma lista invertida. Este valor tem omesmo objetivo, ser usado no cálculo do peso de relevância durante o processamento deconsultas. Além disto, no VIF existe outro atributo não presente no PL. O df de cadatermo é armazenado em uma estrutura separada dos dados, o vif.df.

4.3.1 Estrutura VIF

A estrutura de armazenamento dos dados se baseia no gerenciamento de blocos con-tendo partes de listas invertidas. As listas �cam dispostas nos blocos, sendo que umalista pode usar um ou mais blocos dependendo do tamanho desta. Isto é, no caso dea lista não caber em um bloco, ela é armazenada em tantos quantos forem necessários.Em caso de listas pequenas, um bloco pode conter entradas de uma ou mais listas. Estadistribuição das listas é organizada em intervalos, cada intervalo é especi�cado pelo limitede intervalo. Um intervalo é representado por dois pares de códigos de termo e códigosde página indicando a primeira e a última entrada do intervalo, equivalente ao PL.

A Figura 23 ilustra um exemplo da estrutura VIF onde no arquivo vif.data estãodispostas quatro entradas VIF. Cada linha mostra um exemplo de uma entrada VIF ondeos dois primeiros valores separados pelo caracter �:� em negrito são os valores do termid


Figura 23: Estrutura básica índice VIF

seguido do docid da entrada, os dois valores seguintes, também separados pelo caracter�:� são o peso da entrada seguido de size, o tamanho da lista de posições. Em seguidaseguem size valores de posicão em ordem crescente.

Nesta visão lógica toda informação aparenta estar disposta de forma contínua distri-buída entre vários blocos. Entretanto, esses blocos são distribuídos no arquivo vif.datade forma não seqüencial sendo organizados pela B+-Tree. Cada bloco tem tamanho �xoe armazena uma quantidade variável de entradas, como dito antes, esta quantidade de-pende de como as entradas foram adicionadas à estrutura onde o arquivo de dados sofreo mesmo dinamismo de um arquivo de B+-Tree. A política de atualização do arquivode dados é semelhante à de uma B-Tree, por isso, as duas estruturas vif.btree e vif.datapodem ser vistas como uma única estrutura de uma B+-Tree onde os dados das folhas�cam armazenados no arquivo vif.data. A diferença para uma B+-Tree comum está nouso de codi�cação especí�co de entradas de índice invertido presente nos blocos VIF.

4.3.2 Organização blocos VIF

No VIF os blocos são organizados pela vif.btree, esta estrutura faz controle do acessoaos blocos VIF (Figura 24). Isto é feito armazenando uma chave de identi�cação deintervalo de cada bloco e o ponteiro do bloco semelhante ao PL. Entretanto, no VIF énecessário armazenar apenas uma entrada (termid,docid). Isto acontece porque o VIFmantém sempre todo o intervalo de cobertura das tuplas sobre controle. Como exemplo,no caso inicial um índice VIF vazio contém no vif.btree um entrada {(∞:∞)} apontandopara um bloco VIF vazio na estrutura vif.data. Neste caso a entrada (∞:∞) indica,de forma implícita, que existe apenas um bloco VIF de intervalo inicial (1:1) e �nal(∞,∞). Quando a estrutura ocupar dois blocos VIF então existirá duas entradas dechave no vif.btree, digamos {(t1:d1),(∞:∞)} indicando estes dois blocos identi�cados pelosintervalos de entradas [(1,1),(t1:d1)] e outro intervalo para ](t1:d1),(∞:∞)].


Figura 24: Organização dos blocos no VIF

O índice VIF é armazenado de forma compactada. A compactação está presenteinternamente nos blocos VIF na estrutura vif.data. Cada bloco é compactado indepen-dentemente dos outros onde são utilizadas as codi�cações Delta, VBC, Elias e Golombdescritas na Seção 3.3.1. Desta forma, a quantidade de espaço utilizado em cada blocovaria não apenas em função do número de entradas e do tamanho de cada entrada (que évariável) mas, varia também em função da taxa de compactação aplicada pelo método decompressão utilizado. Isto faz com que exista um espaço vazio variável no �nal de cadabloco VIF, como ilustrado na Figura 24.

4.3.3 Processamento de Consulta no VIF

O processamento de consultas no VIF segue o modelo de processamento de expressõesbooleanas como descrito na Seção 3.6.1. Para que este processamento seja possível énecessário recuperar a lista invertida de um termo qualquer do índice. No VIF as entradasde uma mesma lista podem estar distribuídas de forma dispersa em diferentes blocos VIFno arquivo de dados vif.data. Desta forma, é necessário recuperar a lista de forma ordenadado índice. No VIF isto é feito em tempo de consulta. Este algoritmo de construção emtempo de consulta da lista invertida no VIF é de�nido da seguinte forma. Dado umapalavra-chave qualquer p primeiro deve-se recuperar o termid de p, em seguida é feitauma busca na B+-Tree para encontrar o bloco que contém a primeira entrada da lista, istoé feito buscando na B+-Tree o intervalo da entrada (termid, 1). A B+-Tree irá retornarum blockid que é usado para recuperar do disco o bloco VIF com as entradas que podeou não conter a entrada buscada. O segundo passo é procurar a entrada no bloco, isto éfeito fazendo uma busca binária no bloco até encontrar a primeira entrada com o termid

que se procura. Deste ponto basta ler seqüencialmente as entradas do bloco até encontraruma entrada de outro termid. Quando as entradas do bloco terminarem, então deve-se


recuperar o próximo bloco através da B+-Tree fazendo uma busca usando a última entradado bloco corrente.

4.3.4 Processamento com Fila de Prioridade

Algumas consultas podem retornar muitos itens de resposta e muitas vezes estesitens não são relevantes. Além disso, pesquisas mostram que quase a totalidade dosusuários analisam apenas os 10 ou 20 primeiros itens [57]. O custo de gerar uma lista deresposta completa não vale o esforço. Para evitar o problema de ordenar num conjuntomuito extenso de itens de resposta. O processamento da busca faz a coleta das páginasrelevantes usando uma �la de prioridade que armazena apenas os itens de resposta commaiores pesos.

À medida que uma consulta é processada é gerada a lista de resultado com a dupla(docid, peso) onde peso é o valor de peso de relevância da página. Este peso é usado paraordenar a lista de respostas que é retornada ao usuário. Em algumas consultas podem serretornados muitos itens. Por exemplo no nosso corpus de exemplo o termo �brasil� apareceem mais de um milhão de páginas. Na prática vários desses itens podem ser descartados.A �la de prioridade serve para manter em memória os itens de resposta com os maiorespesos. Durante o processamento, esta �la de prioridade, possibilita rapidamente descobriro menor peso dentre os maiores. Quando uma tupla nova é processada o algoritmo veri�case o peso desta tupla é maior que o menor peso na �la. Se não for maior então a entradaé descartada imediatamente. Caso contrário esta entrada é adicionada à �la. Se a �laestiver cheia então o menor elemento é descartado.

4.3.5 Salto de Blocos

A estrutura do VIF oferece de forma nativa um índice B+-Tree que pode ser usadopara otimizar o processamento de consultas que geram muitos casamentos incorretos.Um exemplo deste tipo de consulta é a consulta �brasil E izoneiro� onde o termo �brasil �ocorre em milhões de páginas e o termo �izoneiro� ocorre apenas em uma dezena depáginas. O algoritmo clássico de processamento para esta consulta deveria percorrer todaa lista invertida do termo �brasil �. No VIF pode ser feita uma pequena modi�cação noprocessamento de consultas para saltar blocos que não possuem casamento, isto pode serfeito alterando o algoritmo de leitura seqüencial da lista invertida do termo para quandose estiver processando uma consulta do tipo E observar o maior valor de docid dos termos

4.4 Projeto e Implementação do VIF 62

presentes utilizando a B+-Tree para encontrar o próximo bloco VIF que contém o docid

dado evitando a leitura dos blocos intermediários.

4.3.6 Construção e Atualização do VIF

O processo de construção e atualização (release) do VIF é responsável por atualizarum índice VIF baseado em um conjunto de páginas realizando operações de inserção,atualização e remoção de entradas VIF. O processo de atualização é realizado de formaincremental e inplace. Novas páginas são adicionadas ao índice que se reorganiza mantendoa estrutura balanceada como uma B+-Tree.

O processo de atualização é realizado da seguinte forma. Inicialmente o módulo deindexação gera os arquivos de transação, vif.trans, com os dados para atualização doíndice de busca. Estes arquivos são usados como entrada para o processo de release queé executado em dois passos. O primeiro passo faz a união dos arquivos vif.trans gerandoum único arquivo de atualização ordenado. E, o segundo passo basicamente atualiza oíndice VIF de busca diretamente fazendo a leitura seqüencial do arquivo com os dados detransação identi�cando os blocos que devem ser alterados como ilustrado na Figura 25.Deste modo é realizada a atualização localizada no índice VIF onde apenas os blocos comdados que precisam ser alterados são lidos e modi�cados.

Figura 25: Atualização localizada no VIF

4.4 Projeto e Implementação do VIF

Esta seção descreve os detalhes do projeto e da implementação realizados na elabora-ção do índice VIF.


4.4.1 Ambiente de Desenvolvimento4.4.1.1 Linguagem de Implementação e de Modelagem

A linguagem de Programação utilizada é Java1 por ser uma linguagem orientadaa objetos (OO), por ser uma linguagem multiplataforma, e por oferecer uma gama deAPIs para acessos a rede, manipulação de entrada e saída, entre outros. Além disso é alinguagem utilizada no Radix e, por ser OO, facilita a integração e incorporação de novoscomponentes de acesso a dados.

São utilizados diagramas de classes, de seqüências, de colaboração e de atividadesda linguagem de modelagem UML [60] para modelar as classes, processos e algoritmosdescritos neste trabalho.

4.4.1.2 Plataforma Operacional

A implementação do VIF foi realizada utilizando as plataformas oferecidas no enge-nho de busca Radix. A principal plataforma operacional utilizada para rodar o sistemafoi uma combinação de máquinas com arquitetura Intel Pentium 3 2 e sistema operacionalLinux. A vantagem em utilizar esta combinação é o custo �nal muito menor, sem sacri-�car o desempenho, comparado com outras alternativas de hardware e outros sistemasoperacionais de prateleira.

Foram utilizadas várias versões de máquinas virtuais Java (JVM), todas compatíveiscom a API Java 2. Entre elas as JVM da Sun3, da IBM4 e blackdown5. Como todo osistema é feito em Java, teoricamente ele executa em qualquer máquina que possua suaimplementação de JVM. Por exemplo, o engenho Radix executou em outras plataformasusando máquinas de arquitetura Sun ou Sparc e sistemas operacionais SunOS ou AIX.

4.4.2 Arquitetura VIF

A arquitetura do engenho utilizando o VIF não sofreu alteração em relação à arquite-tura original (Seção 4.2) mas foram feitas alterações dos componentes de acesso a dados.A Figura 26 exibe os componentes que foram modi�cados marcados em cinza. Cada com-

1java.sun.com2www.intel.com3www.sun.com4www.ibm.com5www.blackdown.org


ponente foi alterado deixando de usar o índice anterior, baseado em índices IF e PL, epassando a utilizar a estrutura VIF.

Figura 26: Componentes modi�cados para usar o VIF

4.4.3 Modelo Acesso e Manipulação do Índice VIF

Esta seção descreve as classes básicas de acesso e manipulação do índice VIF. Asprincipais classes de acesso aos dados são VIFEntry que representa uma entrada VIF e aclasse VIFBucket que representa um bloco VIF no arquivo de dados vif.data. A Figura27 mostra o diagrama de classes UML para estas classes. Abaixo segue um resumo decada classe presente no diagrama.

• VIFEntry: É a interface que representa uma entrada VIF com métodos para recu-perar os valores de termid, docid e rank realizados nos métodos getTermId, getDocIde getRank, respectivamente, e para enumerar a lista de posições usando os métodosstartWalk para começar a listagem das posições da entrada, nextPosition para pas-sar para a próxima posição e getPosition para recuperar o valor da posição correntena listagem;


Figura 27: Diagrama de Classes dos componentes de acesso e manipulação do índice VIF

• VIFBucket: É a interface que representa um bloco VIF no arquivo de dadosvif.data. Esta interface oferece métodos para recuperar o cabeçalho do bloco atravésdos métodos getSize, getStartTermId, getStartDocId, getEndTermId e getEndDocIde recuperar uma entrada de um índice qualquer pelo método getEntry passandocomo parâmetro o índice da entrada;• VIFEntryImpl e VIFBucketImpl: São implementações das interfaces VIFEn-try e VIFBucket, respectivamente, que fazem acesso usando dados do bloco VIFcarregado em memória;• VIFReader: Interface que representa um leitor de entradas VIF. Uma classe destetipo enumera seqüencialmente objetos VIFEntry atráves dos métodos startReadingpara iniciar a leitura, next para passar para a próxima entrada e getEntry pararecuperar a entrada corrente. Possui uma assinatura do método setJumpId usadopara saltar entre as entradas que recebe como parâmetro um docid indicando que


a próxima entrada a ser listada deve ter, no mínimo, um docid maior ou igual aoespeci�cado no parâmetro;• VIFReaderByTerm: É uma classe do tipo VIFReader que representa objetos quelistam entradas de um termo especí�co. Esta classe é utilizada no processamentode consultas;• VIFReaderMerge: Representa objetos do tipo VIFReader que fazem a listagemde entradas a partir da união (merge) de vários outros leitores. Esta classe é utilizadapara fazer a união dos arquivos de transação vif.trans gerados pelo Servidor deIndexação;• VIFFileReader: É uma classe do tipo VIFReader que opera como uma enumera-ção listando entradas VIF a partir dos dados de um arquivo gerado por um objetoescritor do tipo VIFEntryWriter. Esta classe é utilizada no processo de Release paralistar os arquivos de transação gerados pelo Servidor de Indexação;• VIFDecoder: Interface que descreve o objeto que realiza a decodi�cação de umbloco VIF e gera um objeto em memória do tipo VIFBucket de acesso às entradasdeste bloco. Possui na assinatura o método decode que recebe como parâmetro uminteiro identi�cador do bloco VIF e um array de bytes representando o bu�er comos dados brutos compactados do bloco VIF e retorna um objeto do tipo VIFBucket ;• VIFCompressor: Interface que representa um objeto responsável por fazer co-di�cação de entradas VIF gerando um bu�er em memória compactado para serarmazenado em disco no arquivo de dados vif.data. Esta interface descreve um es-critor onde os métodos principais são reset, que prepara o objeto para escrita, add,que recebe como parâmetro uma entrada VIF do tipo VIFEntry e adiciona estaentrada no bu�er em memória, e �nish, que �naliza um bloco VIF em memóriagerando um bu�er que pode ser recuperado pelo método getBu�er ;• VIFDecoderImpl e VIFCompressorImpl: São as implementações de VIFDe-coder e VIFCompressor respectivamente. As duas implementações usam uma com-binação de codi�cação Elias, Golomb, VBC e Delta descritas na Seção 3.3.1. Asduas classes devem respeitar o mesmo modelo de codi�cação e decodi�cação;• VIFBucketReader: É a interface que de�ne um leitor de blocos VIF. Esta inter-face de�ne um método produce que recebe como parâmetro um inteiro identi�cadodo bloco VIF no arquivo de dados vif.data e retorna um objeto do tipo VIFBucket ;


• VIFBucketReaderImpl: É a implementação do leitor de blocos VIFBucketRea-der. Esta classe faz acesso direto ao arquivo de dados vif.data para recuperar osdados brutos do bloco e usa uma instância de decodi�cador VIFDecoder para geraro objeto VIFBucket resultado do método produce;• VIFBucketIdIndex: Esta interface de�ne os métodos de acesso e manipulaçãodo arquivo vif.btree através de uma B+-Tree. O método de acesso presente é o re-adBucketId que recebe como parâmetro dois inteiros especi�cando a chave de umaentrada pelos valores de termid e docid e retorna um inteiro indicando o iden-ti�cador bucketid do bloco VIF no arquivo de dados vif.data no qual a entradaespeci�cada deve estar, se existir. Além deste, existem dois métodos de manipu-lação que são: (1) splitRange(startTermId, startDocId, endTermId, endDocId,midTermId, midDocId, bucketIdLeft, bucketIdRight), que recebe como parâme-tro três duplas de chaves de entradas VIF (termid, docid) onde as duas primeirasindicam o intervalo de um bloco existente no arquivo de dados vif.data formado por[ (startTermId, startDocId), (endTermId, endDocId) ] e a outra é uma entradaintermediária (midTermId,midDocId) do intervalo do bloco indicando que o blocoserá dividido em dois. Um bloco com entradas menores que a entrada intermediá-ria e o outro bloco com o restante das entradas. O bloco das entradas menoresé atribuído ao identi�cador bucketIdLeft e o outro bloco é atribuído o parâme-tro bucketIdRight. E o segundo método (2) unionRanges(startTerm1, startDoc1,endTerm1, endDoc1, startTerm2, startDoc2, endTerm2, endDoc2, bucketid) de-�ne uma operação de união de dois blocos especi�cados pelos dois intervalos naassinatura do método e mais com o identi�cador do bloco bucketid que é atribuídoao intervalo com o resultado da união no arquivo vif.btree;• VIFBucketIdIndexBtree: É a implementação da interface VIFBucketIdIndexque usa uma instância de uma árvore B+-Tree para implementar as operações deacesso e manipulação do arquivo vif.btree;• BPlusTree: Classe que implementa operações de acesso e manipulação de umíndice B+-Tree. Os principais métodos utilizados são searchGE, que faz a busca pelomenor elemento maior ou igual que a chave passada como parâmetro do método eretorna o valor associado ao elemento encontrado, insert, que adiciona uma novaentrada na árvore passada como parâmetro, delete, que remove uma entrada, eupdate, que atualiza o valor associado a uma chave;• Key: Interface que representa uma chave utilizada pela classe BPlusTree. Esta


interface oferece as operações de comparação, armazenamento e leitura da chave;• TwoIntKey: Implementação de um objeto do tipo Key onde a chave são doisvalores de inteiros representando uma chave de entrada de VIF, sendo que o primeirovalor indica o termid e o segundo indica o docid de uma entrada;• VIFEntryWriter: Esta classe representa um objeto escritor de um arquivo comentradas VIF em seqüência. Esta classe utiliza um compressor do tipo VIFCom-pressor para adicionar entradas e gerar blocos VIF em memória. Estes blocos sãoarmazenados em disco em um arquivo. Esta classe é utilizada para gerar os arquivosde transação vif.trans pelo Servidor de Indexação;• VIFBlockedMerge: Esta classe de�ne o objeto responsável por atualizar um VIFde busca a partir do arquivo com os dados de atualização gerados pelo Servidor deIndexação fazendo atualizações localizadas nos blocos VIF. O Objeto possui umainstância para um leitor de entradas VIF VIFReader utilizado para listar as entradascoletadas durante a indexação. Estas entradas são atualizadas no arquivo de dadosvif.data de forma pontual utilizando o índice vif.btree através de um objeto do tipoVIFBucketIdIndex. Estes blocos atualizados são armazenados de volta no arquivode dados compactados usando o compressor.

4.4.4 Servidor de Indexação

O Servidor de Indexação é o componente responsável por fazer o armazenamentodas páginas coletadas pelos crawlers como visto na Seção 4.2.3. Este componente écomposto pela união de vários componentes que fazem o armazenamento em transaçõesde cada estrutura do sistema (listadas na Seção 4.2). A Figura 28 mostra o diagrama deseqüências ilustrando o passo-a-passo de chamadas feitas aos componentes que compõemo Servidor de Indexação. O início do processo acontece quando o Servidor de Indexaçãorecebe um objeto Página criado pelos crawlers onde é feito a análise do documento e sãoextraídas as informações que são encapsuladas no objeto Página para serem recuperadaspelo servidor de indexação. A partir deste momento o objeto é repassado para os outrossub-componentes que compõem o Servidor de Indexação. Cada um coleta a informaçãopertinente à estrutura em que o componente é responsável.

Abaixo segue a lista de cada componente descrevendo os dados pelos quais cada umé responsável:


Figura 28: Diagrama de seqüência do Servidor de Indexação do Radix

• PageStorage: Componente responsável por armazenar os dados informativos dapágina como: endereço, título, descrição, tamanho da página, etc;• CentroidStorage: Neste componente é feito o armazenamento das informações doíndice do centróide da página usado durante a atualização de páginas;• LinkStorage: Faz a coleta os links das páginas e envia para o Servidor de Linkspara que ocorra a realimentação dos crawlers com endereços para novas páginas;• VIFStorage: Componente que faz o armazenamento dos dados do índice VIF.

Cada componente armazena na base de indexação os dados das páginas que servempara atualizar o índice de busca durante o processo de release. Todos os componentesarmazenam estes dados em arquivos de transação relativo à estrutura pela qual o compo-nente é responsável. Cada arquivo contém uma quantidade máxima de documentos, comoexemplo 100, onde a cada 100 documentos enviados pelos crawlers é gerado um arquivode transação para estes documentos.

O VIFStorage armazena cada arquivo de transação como um �pequeno� índice VIFchamado de vif.trans onde são armazenadas as entradas que devem ser atualizadas noíndice de busca gravados em disco usando um objeto VIFEntryWriter. Cada entradapresente no arquivo de transação pode ter três signi�cados que são: (a) uma entrada deum documento novo; (b) uma entrada de atualização ou (c) uma entrada que deve ser


removida. As entradas (a) e (b) são consideradas entradas normais enquanto as entradasde remoção (c) são entradas especiais com uma marca indicando que a entrada deve serremovida do índice de busca durante o processo de release.

4.4.5 Processador de Consultas

O Processador de consultas equivale ao componente DataCoreSearch descrito na Seção4.2.1. Este componente é o núcleo do processamento de consultas, é neste componenteque é realizado o acesso ao índice VIF. A Figura 29 mostra as classes que participam nocomponente processador de consultas.

Figura 29: Diagrama de Classes do Processador de Consultas

A descrição de cada classe presente é listada abaixo:

• FacadeStorage e CoreSearch: São as classes que recebem a consulta do usuárioe iniciam o processo de busca. Estas classes integram o módulo de busca original eestão descritas na Seção 4.2.1;


• Query: Este tipo de classe representa um objeto com a expressão booleana espe-ci�cada pelo usuário do sistema. Este objeto faz o tratamento da consulta originalsendo usado para criar a árvore de processamento de consultas;• Request: Representa uma requisição do usuário. Contém a consulta do usuáriode�nida como um objeto do tipo Query, o índice da requisição do usuário e otamanho da página de resposta (número de endereços que deve ser mostrado noresultado);• Result: Representa o objeto de resultado de uma consulta retornado para a camadade interface. Este objeto armazena a lista de docid que foram processadas no objetoDataCoreSearch;• TupleCollection: Classe dos objetos que representam uma coleção de entradasde resultado do processamento. Além de armazenar o docid também armazenaum valor rank que é o valor de relevância de cada documento gerado durante oprocessamento da consulta;• DataCoreSearch: Classe que representa o objeto responsável por realizar o pro-cessamento de consultas gerando à lista de docid que respondem a requisição dousuário. Esta função é executada por uma chamada ao método search que temcomo parâmetro um objeto da classe Request e retorna como resultado um objetoda classe Result. A lista de docid é criada usando um objeto SearchResultRetrievecriado localmente, usado pela fábrica retrievFactory para responder à consulta;• SearchTreeFactory: Esta classe representa uma fábrica de árvores de proces-samento de consulta. Uma árvore de processamento é a estrutura utilizada paraprocessar consultas geradas a partir da expressão booleana especi�cada pelo usuá-rio. O método produce recebe uma consulta do usuário representada pelo objetoQuery e gera a árvore de processamento retornando como resultado do método onó raiz da árvore de processamento;• SearchNode: Representa um nó na árvore de processamento de consultas criadaa partir da expressão booleana da consulta do usuário de�nida no objeto Query ;• SearchResultRetrieve: Responsável por coletar a lista de docid que responde àconsulta, criando uma árvore de processamento de consulta representada por umobjeto do tipo SearchNode criado a partir da fábrica treeFactory.


Figura 30: Diagrama de Seqüência do Processador de Consultas


O diagrama de seqüências do processo realizado pelo componente DataCoreSearchestá ilustrado na Figura 30. Em resumo, o processo ocorre nos seguintes passos. Inicial-mente o componente DataCoreSearch recebe uma chamada do método search pelo objetofachada do sistema (FacadeSearchEngine) junto com um objeto Request passado comoparâmetro com a requisição do usuário. Este objeto é usado para produzir um objeto Se-archResultRetrieve chamando o método produce da fábrica. A fábrica representada pelaclasse SearchResultRetrieveFactory cria a árvore de processamento de consulta a partir doobjeto Query da requisição do usuário usando a fábrica de árvore de processamento. Ométodo run do objeto SearchResultRetrieve faz o processamento da consulta chamandoo método processIndex na raiz da árvore de processamento. Ao �nal do método run oobjeto tuples estará preenchido com a lista de docid de resposta da consulta. Por �m,esta lista é adicionada a um objeto de resultado Result sendo retornado para a fachadado sistema.

4.4.6 Árvore de Processamento de Consultas

O processador de consultas é baseado em expressões booleanas. Nele uma consulta éinicialmente processada sendo construída a árvore de processamento da consulta (comodescrito na seção anterior). Esta árvore é usada para processar as consultas, gerar alista de resposta e calcular o peso de relevância de cada documento. É na árvore deprocessamento que acontece o acesso ao índice e leitura das listas invertidas. São as folhasda árvore os elementos de acesso, este acesso é realizado pelo objeto que implementa ainterface VIFReader que faz a leitura das entradas VIF realizadas nos objetos do tipoVIFEntry. A Figura 31 mostra o diagrama de classes UML para as classes presentes nasárvores de processamento. Abaixo segue a descrição de cada classe:

• SearchNode: É a interface que representa a abstração de nó da árvore de pro-cessamento. A operação principal de um nó é realizada pelo método processIndexusado para fazer o processamento da consulta;• AbstractSearchNode: Esta classe implementa as funções básicas de um nó deprocessamento SearchNode e deixa a implementação do comportamento do nó paraser implementado por uma subclasse;• SearchNodeTerm: É a classe que representa os objetos que são folhas na árvorede processamento. Este objeto faz a leitura da lista invertida usando o leitor deentradas VIF, VIFReader ;


Figura 31: Diagrama de Classes dos Nós de Processamento da Busca

• VIFReader: Interface que representa um objeto que faz a leitura seqüencial deentradas do VIF. Basicamente são implementados os métodos para enumerar asentradas VIF e um método adicional setJumpId para saltar entradas não necessárias;• VIFEntry: Interface que representa uma entrada VIF. Possui métodos para recu-perar o termid, docid, rank e lista de posições da entrada;• VIFReaderByTerm: É a implementação da interface VIFReader utilizada paraenumerar as entradas do índice VIF de um termo especí�co;• SearchNodeOR: Esta classe representa um nó interno na árvore de processamentoque faz a união dos elementos dos nós da sub-árvore implementando no métodointernalProcessNext o comportamento de uma operação booleana OU . São listadastodas os documentos presentes em qualquer uma das sub-árvores;• SearchNodeAND: Esta classe representa um nó interno da árvore de processa-mento estendendo a classe SearchNodeOR sobrescrevendo o método internalProces-sNext para implementar o comportamento de uma operação booleana E. Onde sãoprocessados os elementos presentes em todas as sub-árvores;


• SearchNodeNOT: Esta classe representa um nó interno que implementa o com-portamento de um conectivo do tipo NÃO para consultas por expressão booleana.Esta classe estende a AbstractSearchNode implementando o método internalProces-sNext para listar os documentos presentes na expressão da sub-árvore do atributonode que não acontecem na sub-árvore do atributo notNode;• RankFunction: Interface que representa um objeto responsável por calcular o pesode relevância de um documento durante o processamento. Cada nó da árvore deprocessamento possui um atributo para a função de ordenamento do nó;• TupleCollection: Representa uma coleção de resultado do processamento. Cadaárvore de processamento possui um TupleCollection que �ca localizado na raiz daárvore fazendo a coleta dos valores de docid e rank (peso de relevância) de resultadodo processamento da árvore;• TupleFilter: Interface para objeto que indica se um documento deve ser �ltradoou não. Cada nó de processamento pode ter ou não um �ltro associado.

O �uxo de processamento segue em direção das folhas para a raiz onde são armazena-dos no objeto TupleCollection. A instância real utilizada para armazenar os documentosde resultado é a coleção LimitedTupleCollection. Este tipo de objeto implementa umacoleção de tuplas usando uma �la de prioridade com limite máximo de entradas, digamos1.000 (mil), que armazena durante o processamento os 1.000 documentos de maior pesode relevância como descrito na Seção 4.3.4.

Outra otimização, descrita na Seção 4.3.5, é implementada na árvore de processa-mento. Cada nó da árvore possui um método chamado setJumpId que serve para enviarum mensagem às sub-árvores de cada nó indicando um docid mínimo a ser processado(apenas para processamento de nós tipo E). Esta mensagem chega nos nós folhas e é re-passada para o leitor de entradas VIF, VIFReader. O Leitor se ajusta para que a próximaentrada listada tenha docid maior ou igual ao especi�cado e, caso seja necessário, faz osalto para o bloco do VIF que a entrada especi�cada esteja armazenado.

Como exemplo, a Figura 32 mostra o diagrama de colaboração UML para os objetospresentes no processamento da consulta �(arquivo OU índice) E invertido� e a interaçãoentre os objetos. O processamento ocorre da seguinte maneira. Inicialmente o sistemacria um objeto do tipo SearchRetrieve para responder à consulta (como descrito na seçãoanterior) para então chamar o método processIndex na raiz da árvore de processamento(chamada 1). No caso da �gura, o nó raiz é um objeto do tipo SearchNodeAND, a partir


Figura 32: Diagrama de Colaboração para Árvore de Processamento

deste ponto a própria raiz faz chamadas consecutivas ao método internalProcessNext dopróprio objeto (chamada 2). Neste caso, o objeto implementa um conectivo booleanode consultas do tipo E. O processamento é baseado em uso de �la de prioridade onde érecolhido o resultado do processamento das sub-árvores pelo objeto do tipo PriorityQueuecom chamadas ao método removeTop (chamada 3) que retorna o menor elemento das sub-árvores. O nó do tipo SearchNodeAND retorna apenas os valores de docid que ocorram emtodas as sub-árvores. A alimentação da �la de prioridade do nó é feita através de chamadasao método internalProcessNext das sub-árvores (chamadas 4 e 5). Uma das sub-árvoresé a consulta do tipo SearchNodeOR que processa a expressão �índice OU arquivo�. O


processamento para um conectivo OU é realizado de forma semelhante ao de um conectivodo tipo E com uso de uma �la de prioridade e chamadas ao método removeTop (chamada6). A diferença é que para o objeto do tipo SearchNodeOR sua implementação retornatodos os valores de docid que ocorrem nas sub-árvores sem restrição. No exemplo, todos osvalores retornados nas sub-árvores pelas chamadas de internalProcessNext são retornados(chamadas 7 e 8). Os nós folhas são representados por objetos do tipo SearcNodeTerm.Eles são responsáveis pela leitura da lista invertida de cada termo que é feito através dechamadas ao método next no leitor de entradas VIF VIFReaderByTerm (chamadas 9,10 e 11). Durante o processamento da árvore todos os documentos que são processadoscomo resultado da expressão são adicionados ao objeto do tipo LimitedTupleCollectionatravés do método add na raiz da árvore (chamada 12). Ao �nal do processamento oSearchResultRetrieve recupera a lista dos documentos que foram processados através dométodo getSortedTupleCollection (chamada 13) e a partir deste ponto o processamentocontinua como descrito na seção anterior.

Por �m, a interface RankFunction representa uma função de ordenamento usada paracalcular o peso de relevância dos documentos como dito antes. Cada nó de processamentotem a sua instância de função que é utilizada de acordo com o tipo de consulta do usuário(Seção 2.4). As principais implementações são: RankFunctionProximity que implementauma função para calculo de relevância de acordo com a proximidade dos termos no do-cumento, RankFunctionTFIDF, que calcula o peso de relevância a partir da fórmula detfidf , a função RankFunctionHITS, que calcula o peso de relevância baseado no algoritmode HITS implementado no Radix descrito em [22], RankFunctionAverage que calcula opeso de relevância baseado na média dos pesos dos nós das sub-árvores, e o RankFuncti-onCollection, que calcula o peso de relevância usando uma combinação de outras funçõesde ordenamento.

4.4.7 Processo de Release no VIF

O processo de release do VIF faz a atualização do índice de busca adicionando o quefoi coletado durante a indexação. Como dito antes, o release é realizado em dois passos.Primeiro é feito a união dos arquivos de indexação e em seguida a atualização do índicede busca.

O primeiro passo é realizado como demonstrado na Figura 33. Na �gura �ca ilustradaa interação entre os objetos do processo realizada nesta etapa. O objeto principal é oVIFReaderMerge, que é responsável por realizar a união de outros N leitores do tipo


Figura 33: Diagrama de Colaboração para o Passo 1 do Release do VIF

VIFReader, na �gura é feita a união de três. Esta união é realizada através de uma �lade prioridades representada por um objeto da classe PriorityQueue. O merge é entãorealizado por várias chamadas seqüenciais ao método removeTop (operação 1) da �la deprioridade. Este método retorna o menor elemento da �la removendo-o e atualizandoa lista. Esta atualização é processada baseada nos leitores de arquivos de transaçãorepresentados por objetos do tipo VIFFileReader. Cada objeto é utilizado para listar asentradas de um arquivo vif.trans, gerado pelo Servidor de Indexação, usando o métodonext() (operações 2,3,4). Por �m, todas as entradas lidas pelo VIFMergeReader sãoarmazenadas em um arquivo temporário usando o objeto escritor do tipo VIFEntryWritercom chamadas seqüenciais do método add para cada entrada listada (operação 5). Noexemplo da �gura, o processo opera sobre os três arquivos de transação sendo que naprática são gerados incontáveis arquivos de transação durante a indexação. Deste modo,este processo é executado várias vezes até que todos os arquivos de transação vif.transsejam uni�cados.

A segunda etapa do processo do Release no VIF é realizar a atualização do arquivode dados do índice VIF de busca. Esta operação é realizada pelo objeto da classe VIF-BlockedMerge. Basicamente, o objeto faz a leitura seqüencial do arquivo com os dados daunião das transações vif.trans do passo anterior, gera bu�ers das entradas de atualizaçãode cada bloco VIF e atualiza este bloco no arquivo de dados vif.data.

A Figura 34 mostra o diagrama de atividades realizadas pelo VIFBlockedMerge. Oprocedimento pode ser dividido em duas sub-etapas. A primeira visa ler o arquivo dedados e gerar o bu�er de entradas de atualização. Este bu�er é gerado baseado em umbloco VIF. Inicialmente é lida a primeira entrada de atualização do arquivo vif.trans. De


Figura 34: Diagrama de Atividades da Atualização em Blocos no Índice VIF

acordo com esta entrada o bloco VIF correspondente a entrada é lido do índice de busca.Depois, o bu�er é preenchido com as entradas que pertencem a este bloco. Esta etapa párade preencher o bu�er quando a entrada corrente está fora do intervalo de cobertura dobloco VIF, ou quando não existem mais entradas ou o bu�er de entradas está cheio. Nestestrês casos, o procedimento passa para a sub-etapa seguinte. Esta segunda etapa visa gerarem memória um novo bloco VIF atualizado. Caso este bloco esteja balanceado, i.e., obloco nem está cheio nem vazio (estado bloco OK na �gura), então o bloco é armazenadoem disco e o processo volta ao passo inicial de atualização das próximas entradas.

No caso do bloco �car cheio é necessário que sejam criados novos blocos VIF. Esteprocedimento deve gerar tantos blocos quantos forem necessários para armazenar as en-tradas do bloco que foi atualizado. O pseudo-código da Figura 35 descreve o algoritmo dedivisão recursiva de blocos que equivale à atividade �gera novo bloco e divide entradas�

4.4 Projeto e Implementação do VIF 80Algoritmo 2Procedimento DivisaoBlocosVIF (E, s, e, B)Entrada: Array de entradas E, índice da entrada inicial s, índice da entrada �nal e,

referência para bloco VIF BSaída: Blocos divididos e armazenados em disco(∗ Faz a divisão de forma recursiva ∗)1. tenteCompactar(E, s, e, B)2. se não conseguiu compactar3. então seja mid← s+e

24. seja midTerm← E[mid].getTermId() o termid da entrada E[mid]5. seja midDoc← E[mid].getDocId() o docid da entrada E[mid]6. seja C ← ∅ novo bloco VIF vazio7. (∗ Atualiza o intervalo de cobertura do bloco C ∗)8. C.setStartTermId(B.getStartTermId())9. C.setStartDocId(B.getStartDocId())10. C.setEndTermId(midTerm)11. C.setEndDocId(midDoc− 1)12. adicione entrada ((midTerm, midDoc− 1), C) na B+-Tree vif.btree13. (∗ Primeira chamada recursiva sobre B ∗)14. DivisaoBlocosVIF (E, s, mid− 1, C)15. (∗ Segunda chamada recursiva sobre B ∗)16. B.setStartTermId(midTerm)17. B.setStartDocId(midDoc)18. DivisaoBlocosVIF (E, mid, e, B)19. senão20. armazene bloco B em disco

Figura 35: Pseudo-código do algoritmo de divisão dos blocos VIF

no diagrama de atividades. O algoritmo funciona da seguinte maneira. O primeiro passoé tentar compactar as entradas no bloco. Caso não consiga então o bloco é dividido emdois. É escolhida a entrada mediana que divide o conjunto de entradas em dois comonúmeros iguais de entradas (caso o número seja ímpar um conjunto �ca com uma entradaa mais) e o procedimento é chamado de forma recursiva sendo criado um novo blocopara suportar as entradas do segundo conjunto de entradas. É necessário a atualizaçãodo arquivo vif.btree onde deve ser adicionado uma nova entrada para que seja possívelrecuperar o novo bloco VIF criado. Isto é feito adicionando uma nova entrada baseadono elemento mediano escolhido especi�cando o limite superior do intervalo de coberturado bloco.

O terceiro caso acontece quando o bloco se torna �vazio�. Na realidade o termo �vazio�é utilizado para indicar os blocos que estão com utilização abaixo de um parâmetro limiteL. Este limite L indica o percentual mínimo aceitável de uso de um bloco onde a taxa de

4.5 Testes e Resultados 81

utilização de um bloco (q) de�nida como a relação entre o espaço utilizado pelo tamanhodo bloco é considerada aceitável quando a utilização do bloco é maior ou igual ao limiteL (q ≥ L) e menor que o limite rígido do tamanho do bloco(q ≤ 1). Caso a utilizaçãode um bloco esteja abaixo deste limite então o bloco é considerado �vazio� (q < L) e sãorealizadas operações de rebalanceamento do índice VIF. Estas operações são semelhantesàs operações de remoção em uma B+-Tree [61, 62] e são realizadas do seguinte modo.Primeiro, o procedimento tenta realizar uma divisão das entradas do bloco com o seubloco vizinho. Isto é feito recuperando um bloco vizinho (o esquerdo e depois o direito)e as entradas são divididas entre os dois blocos. Caso os dois blocos �quem com taxa deutilização aceitável então o bloco é considerado �OK�, os dois blocos são armazenados emdisco e o índice vif.btree é atualizado para um novo intervalo de cobertura dos blocos. Semesmo assim o bloco continuar �vazio� então é realizada a operação de união das entradasdo bloco com o vizinho em um bloco único. Esta operação faz com que um dos blocos,entre o bloco modi�cado e o vizinho, se torne o bloco que irá armazenar as entradas dosdois blocos. O outro bloco é removido do índice vif.btree.

Quando um bloco é removido ele não é realmente apagado. O bloco removido continuafazendo parte do arquivo de dados vif.data sendo que todos os blocos vazios do arquivoformam uma lista simples de blocos livres onde em memória é utilizado apenas um ponteiropara o primeiro bloco da lista. Estes blocos são mantidos para serem reutilizados no futuro,quando ocorrerem operações de divisão, os �novos� blocos são retirados desta lista. Sãocriados blocos novos em disco apenas quando esta lista está vazia.

4.5 Testes e Resultados

Esta seção expõe os testes realizados sobre o índice VIF visando medir o desempenhoda estrutura apresentando os resultados obtidos.

4.5.1 Metodologia

Os testes realizados visaram medir o desempenho da estrutura em casos de usosnormais do índice VIF. Foram utilizados dois corpus de testes. O primeiro é um cópia dabase do Radix de janeiro de 2001 onde foram feitos os testes iniciais, esta base é chamadade BASE1. O segundo corpus corresponde aos documentos coletados da Web brasileira(domínio �.br�) no mês de junho de 2003 chamado de BASE2. Os dados das duas basesestão na Tabela 10.


BASE1 BASE2

Número de documentos(N) 11 milhões 3.2 milhõesNúmero de termos(n) 8.5 milhões 3 milhõesNúmero de entradas(E) 1.8 bilhão 246.7 milhões

Tabela 10: Detalhe dos corpus de testes

As medidas de desempenho da estrutura utilizadas são: (a) espaço utilizado, medidopelo espaço em disco total ocupado pelo índice; (b) tempo de criação, medido pelo tempogasto para criar o índice VIF (c) tempo de consulta, medido baseado no tempo gasto noprocessamento das consultas.

Os primeiros testes foram realizados visando veri�car a viabilidade de utilização doíndice comparado com a estrutura anterior utilizada no engenho Radix. Este teste tevefoco no espaço utilizado pelas duas estruturas VIF e índices IF e PL. No teste foramcomparados o espaço utilizado pelos dois índices criados sobre o mesmo corpus, no casofoi utilizado o corpus de teste BASE1. Além deste, foi realizado o teste de carga do módulode busca. Este teste é realizado da seguinte maneira. Um programa cliente simula umusuário do sistema fazendo consultas ao engenho em períodos �xos de tempo, i.e., umaconsulta a cada intervalo de tempo �xo parametrizado no programa cliente. Este clienteutiliza as próprias consultas feitas pelos usuários do engenho Radix coletadas no log dosistema. Foram realizadas duas baterias de testes. Uma sobre o índice VIF e outra sobreos índices IF e PL. Em cada bateria foram feitos quatro testes cada um utilizando umacarga diferente, os parâmetros de carga utilizados foram: uma consulta a cada 1 (um)segundo, a cada 500 milisegundos (ms), a cada 250 ms e a cada 125 ms. Como resultadode comparação foram coletados os tempos de processamento das consultas em cada teste.

O segundo teste foi realizado visando encontrar um valor do tamanho do bloco VIFpara obter melhor desempenho analisando o comportamento da estrutura de acordo coma variação do parâmetro (tamanho do bloco). Neste teste foi utilizado o corpus BASE2

onde foram executados e foi gerado o índice VIF variando o tamanho do bloco VIF nosseguintes valores: 256bytes (B), 512B, 1 Kilobyte (KB), 2KB, 4KB, 8KB, 16KB, 32KBe 64KB. Foram coletadas as medidas: de espaço total utilizado pelo índice; de espaçoutilizado pela estrutura B+-Tree do VIF(vif.btree); de tempo para criação do índice; e detempo para criação da cache estática.

O terceiro teste realizado visou medir o comportamento do índice com a otimizaçãodo algoritmo de salto em blocos implementado no processamento de consultas (Seção4.3.5), onde foi gerado o arquivo de cache estática do sistema para medir o tempo de


processamento das consultas e comparado com o tempo para processar o arquivo dacache estática com o processamento �ingênuo�, sem otimização. Este teste foi realizadomedindo o tempo de processamento da cache estática do engenho. Esta cache é umarquivo resultado do processamento das consultas mais freqüentes dos usuários do sistema.No teste, o arquivo de entrada possui dez mil (10, 000) consultas mais procuradas nosistema.

4.5.2 Ambiente do Experimento

Os testes foram realizados em duas con�gurações de máquinas. A primeira con�gura-ção foi para o teste realizado na BASE1 que foi executado em máquinas dual processadascom CPU Intel Pentium III de 600MHz com 512MB de memória RAM e com discosSCSI de 36GB marca Seagate modelo ST336704LW (com tempo médio de acesso iguala 5, 4 ms). Estas máquinas estavam com Linux kernel 2.4 e máquina virtual Java(JVM)IBM 1.3. Para os testes realizados na BASE2 foi utilizada uma máquina com processadorPentium III 550MHz, 512MB de memória e disco IDE de 40GB marca Seagate modeloST340824A (com tempo médio de acesso igual a 8, 5 ms). Nesta máquina foi utilizadoo sistema operacional Linux kernel versão 2.4 onde os testes foram executados usando aJVM da IBM versão 1.4.0.

4.5.3 Resultados

O primeiro resultado obtido foi relativo ao espaço utilizado pela estrutura. A Tabela11 descreve o espaço utilizado na estrutura VIF e nas estruturas IF e PL. Houve um ganhode aproximadamente 78% do espaço, onde se destacam duas das modi�cações realizadas:(i) a eliminação da estrutura IF a qual armazena informação duplicada (mesma informaçãopresente PL) que consumia 17GB; e (ii) o uso de métodos de compressão do índice VIF(Seção 3.3.1), onde, mesmo contendo mais dados que no PL (adição do valor do pesode cada entrada VIF), o VIF passou a ocupar 7.6GB (vif.data) contra os 18GB do PL(pl.data).

O segundo resultado sobre o mesmo corpus BASE1 foi o tempo médio de processa-mento das consultas durante o teste de carga exposto na Tabela 12. Em todos os testesusando o índice VIF o tempo médio de processamento foi inferior. Até mesmo sobre umacarga maior, uma consulta a cada 500ms, o VIF obteve melhor desempenho que o índiceIF e PL com carga de uma consulta a cada 1 segundo. Isto se deve a vários fatores, o


Espaço utilizado pelo IF e PLIF(if.index e if.data) 17GBPL(pl.data) 18GBPL(pl.btree) 95MBTotal 35.1GBEspaço utilizado no VIFVIF(vif.data) 7.6GBVIF(vif.btree) 19MBVIF(vif,df) 55MBTotal 7.7GB

Tabela 11: Espaço utilizado pelo VIF para a BASE1

primeiro fator considerado foi a diminuição de espaço, pois a quantidade de dados brutosa serem lidos durante o processamento de consultas diminuiu cerca de 78% (considerandoa espaço total usado pelos índices VIF e IF+PL), o que afetou diretamente o tempo deprocessamento, que faz uso intenso de merge das listas invertidas e leitura de disco. Outrofator considerado foi relativo às otimizações no algoritmo de processamento de consultasrealizando salto em blocos (Seção 4.3.5) e no uso e�ciente de memória limitando o ta-manho do conjunto de respostas (Seção 4.3.4). A diferença da progressão dos valoresmarcados com (*) na Tabela 12 estão relacionadas com a sobrecarga do sistema que nãoconsegue suportar o �uxo de processamento de consultas acumulando uma quantidadeexcessiva de consultas a serem processadas degradando o desempenho do sistema (AnexoD).

Uma consulta a cada1000ms 500ms 250ms 125ms

VIF 512ms 1s 304ms 1s 940ms 10s 125ms (*)IF e PL 1s 565ms 33s 476ms (*) 38s 711ms (*) 38s 244ms (*)

Tabela 12: Tempo médio de processamento de consultas no teste de carga para índiceVIF e índice IF mais PL usando o corpus BASE1

A Tabela 13 lista os valores do segundo teste realizado onde foram coletados os valoresde espaço utilizado e tempo de criação. Na tabela nota-se que a variação do tamanhodo bloco VIF tem impacto direto no tamanho da B+-Tree vif.btree. Isto acontece porqueo número de entradas está inversamente relacionado com o tamanho do bloco. Quantomaior o tamanho do bloco menos entradas VIF são necessárias. À medida que o tamanhodo bloco é duplicado o tamanho total do arquivo vif.btree diminui pela metade.

Outro ponto veri�cado é a variação do tempo de criação em relação ao tamanho dobloco. São considerados dois fatores acerca desta variação. Primeiro, com blocos pequenos


Tamanho do Bloco Espaço Total(KB) Tamanho vif.btree(KB) Tempo Criação(ms)256B 1,447,737 126,431 2,488,421512B 1,323,553 60,407 2,269,3911KB 1,264,929 29,533 2,146,2192KB 1,237,493 14,614 2,068,2834KB 1,225,777 7,281 2,076,2478KB 1,222,969 3,641 2,142,33016KB 1,227,453 1,830 2,122,46132KB 1,241,125 925 2,243,46464KB 1,277,669 476 2,535,465

Tabela 13: Desempenho do índice com a variação do tamanho do bloco

o tamanho da B+-Tree aumenta porque, com blocos menores, são necessários mais blocose com isso, aumenta o número de entradas armazenadas na B+-Tree, isto faz com que otempo para descobrir os blocos VIF aumente também, pois o tempo de acesso a B+-Tree éproporcional ao tamanho da árvore. No caso de blocos com 256 bytes a árvore chega a teruma profundidade de quatro (4) e mesmo usando uma cache para os nós da árvore queconsiga armazenar os dois primeiros níveis da árvore ainda são necessários duas leiturasde disco na B+-Tree para ler cada bloco VIF. Em compensação, à medida que o tamanhodo bloco diminui, o tempo de re-leitura do bloco é menor, pois, para cada bloco VIF, aquantidade de entradas lidas que não precisam ser atualizadas é menor comparado comblocos maiores, estes, que geram um processamento desnecessário maior.

Tamanho do bloco Ingênuo(ms) Com Salto(ms) % Melhoria256B 299.880 211.471 29,48%512B 261.459 185.665 28,99%1KB 237.905 171.240 28,02%2KB 228.651 170.151 25,58%4KB 224.728 165.052 26,55%8KB 229.219 166.933 27,17%16KB 232.133 171.373 26,17%32KB 245.711 188.098 23,45%64KB 289.692 221.756 23,45%

Melhoria média 26,54%Tabela 14: Comparação Tempo de Busca usando Otimização de salto em blocos. Tempomédio por consulta expresso em milisegundos

A Tabela 14 lista os valores de tempo para o processo de criação da cache estáticade busca. São expostos os tempos para cada índice criado variando o tamanho do blocoVIF onde são mostrados os tempos usando o processamento sem otimização (Ingênuo) e otempo para processamento usando a otimização de salto em blocos (Com Salto). Há de senotar que os mesmos fatores que in�uenciam o tempo de criação também estão presentes


no tempo para processamento de consultas. De modo que, para o teste considerado, otamanho ideal de um bloco VIF veri�cado é 4KB pois é o que oferece melhor tempo médiode processamento de consulta e um dos melhores tempos para criação do índice.

Outro ponto exposto é a melhoria do tempo de processamento com o uso da oti-mização de salto de blocos VIF onde, mesmo para o processamento das consultas mais�populares� onde 56, 47% destas 10.000 (dez mil) são consultas com apenas uma palavra-chave onde não há uso da otimização de salto em blocos. Mesmo assim o tempo médiode processamento de consulta neste caso ainda diminuiu consideravelmente chegando amelhorar o tempo de resposta médio em até 26, 5% no caso de blocos com 4KB. Se fos-sem consideradas apenas as consultas onde se aplica a otimização, 43, 53% das consultasrestantes, a melhoria no tempo médio de processamento seria de 33, 2% observado nostempos mostrados no Anexo C.

4.6 Considerações Finais

Este capítulo apresenta a estrutura de índices VIF descrevendo a arquitetura e im-plementação da estrutura e a incorporação dela ao engenho de busca Radix descrevendo,também, a arquitetura deste engenho. São mostradas as estruturas utilizadas previa-mente no Radix, os índices IF e PL. São descritos os detalhes da implementação do índiceVIF expondo as APIs de acesso e de processamento de consultas implementadas. Sãodescritos os algoritmos de geração e atualização do índice mostrando o todo o processo deorganização dinâmica do índice VIF e o algoritmo de processamento de consultas baseadona construção de árvore a partir da estrutura sintática da expressão booleana da consultado usuário.

Ao �nal são apresentados os testes feitos sobre a estrutura. Os primeiros testes com-param o desempenho da estrutura VIF com as estrutura IF e PL onde são constatadoso ganho de 78% do espaço utilizado e a melhoria média de 26,5% no tempo de processa-mento. Estes resultados estão relacionamos, basicamente, com o ganho de espaço que temimpacto direto na melhoria do tempo de processamento de consultas, visto que a maiorparte do tempo gasto no processamento é utilizado em operações de leitura de disco, o quediminui consideravelmente com uso de compressão. Indo além, a melhoria no tempo deprocessamento também é resultado da otimização do procedimento de processamento deconsultas onde é utilizada a otimização de salto em blocos como visto na seção anterior.

Outro ponto observado está relacionado ao tamanho dos blocos. Há de se notar que


a escolha do tamanho do bloco VIF tem impacto tanto no tempo de criação quanto notempo de processamento de consultas. Para o corpus utilizado nos testes descritos na seçãoanterior, o uso de diferentes tamanhos de blocos acarreta em mudanças no desempenhogeral da estrutura VIF, sendo que, para o corpus testado, o tamanho ideal de um blocoé de 4KB. Porém, este tamanho está baseado no corpus e no ambiente especí�cos usadono teste, de modo que este valor pode não ser ideal em outro ambiente ou, até mesmo nomesmo ambiente para outro corpus. Este ponto não é explorado de forma aprofundadae pode ser um caso de estudo futuro prever o tamanho do bloco ideal que maximize odesempenho geral da estrutura.

Além disso, o estudo quantitativo da e�ciência da estrutura variando o tamanho dobloco realizado na seção anterior pode ser analisado por outros prismas. Por exemplo,na área de arquitetura de computadores conceitos usados para medir o tamanho ideal deblocos usados em caches podem ser usados como comparativo [63]. Caches com blocosmaiores oferecem menores taxas de faltas (miss rate) e, por conseqüência, produzemmenos faltas em cache. Esta redução ocorre porque do principio da localidade possuiduas componentes: localidade temporal e localidade espacial. O uso de blocos maiorestraz a vantagem da localidade espacial, mesma vantagem que se aplica aos blocos do VIF.Entretanto, o uso de blocos maiores aumenta a penalidade de uma falta em cache, poismais dados devem ser lidos em uma falta e, também, blocos maiores reduzem o númerode blocos disponíveis na cache. Ou seja, uso de blocos maiores melhoram e degradam odesempenho por diferentes razões. Encontrar o ponto de equilíbrio que ofereça o melhordesempenho pode ser feito com experimentos práticos como os realizados para calculartamanho de blocos em caches visando melhorar a taxa de faltas [63] ou como o que foiutilizado para encontrar o tamanho do bloco usado na estrutura VIF descrito na Seção4.5.3.

88

5 Conclusões

Este capítulo �naliza o trabalho proposto neste documento. São abordadas as prin-cipais contribuições do trabalho citando também as di�culdades encontradas durante oprocesso do desenvolvimento do trabalho e, por �m, são descritas propostas de possíveistrabalhos futuros acerca do conteúdo tratado nesta dissertação.

5.1 Principais Contribuições

A principal contribuição apresentada foi a implementação da estrutura de índice in-vertido VIF onde foram alcançados os objetivos de gerar uma estrutura usando métodosde compressão de índice, obtendo ganhos signi�cativos de espaço utilizado pelo índice demodo a gerar outras vantagens como o ganho de performance associado à necessidade deprocessamento sobre listas invertidas em virtude da diminuição da necessidade de opera-ções de entrada e saída (E/S). Abaixo segue a lista de contribuições relacionadas com oprojeto VIF:

• Ganho signi�cativo no espaço utilizado pelo índice adquirido pelo uso de métodos decompressão de índice baseado nos métodos de codi�cação Elias, Golomb citados naSeção 3.3.1, onde também foi notado a melhoria no desempenho no processamentode consultas con�rmando o fato de que uso de compressão em índices se tornoufundamental;• Otimização do método de processamento de consultas baseada na técnica de salto deblocos que faz uso da estrutura em árvore da B+-Tree para evitar processamentosdesnecessários durante a leitura das listas invertidas no índice VIF obtendo umamelhoria signi�cativa no tempo de realização de uma consulta. Nos testes realizados(Seção 4.5), o tempo de processamento usando esta otimização melhorou em médiao tempo de processamento das consultas em 26.5%;• Construção de uma API de processamento de consultas baseada na árvore sintática

5.2 Di�culdades Encontradas 89

de expressões booleanas elaborada para ser acoplada ao engenho de busca Radixde forma simples e o mais transparente possível para o resto do sistema oferecendo,também, interfaces para integração de novas funções de ordenamento;• criação de uma estrutura de dados dinâmica baseada no uso de uma B+-Tree oferen-cendo atualização localizada de forma e�ciente quando comparada com estruturas�clássicas� de índices invertidos;• Atualização do processamento de consultas para fazer uso e�ciente de memória limi-tando a lista de documentos processados com o uso de �la de prioridades evitandosobrecarga de uso de memória descartando itens de resposta pouco relevantes.

5.2 Di�culdades Encontradas

Uma das di�culdades encontradas foi a existência de pouco material com informaçõessobre a operação de remoção em B+-Tree. Mesmo sendo uma estrutura bastante difun-dida, utilizada e descrita em praticamente todos os livros sobre banco de dados [64, 65] ouestrutura de dados para memória secundária [66, 67], a operação para remoção de itensé pouco detalhada. Foram encontrados apenas dois artigos [61, 62] que serviram de basepara implementação da estrutura usada no índice VIF.

5.3 Limitações e Trabalhos Futuros

• O tamanho do problema gerou limitações em relação a quantidade de dados queforam manipulados o que di�cultou a realização de testes mais elaborados que con-sumiriam bastante tempo;• Fazer a análise da estrutura baseada no comportamento dinâmico da Web otimi-zando e veri�cando a viabilidade do índice para suportar atualizações em freqüênciade tempo reduzidas, i.e., atualizações a cada minuto, de 15 em 15 minutos, de horaem hora, etc.;• Veri�car a viabilidade de utilizar o índice VIF em um site de alto dinamismo, porexemplo, em um site de notícias, veri�cando a viabilidade de atualizações em temporeal (tempo de consulta) comparando com a proposta descrita na Seção 3.5.2;• Fazer um estudo para veri�car se é possivel predizer o tamanho de bloco VIF idealque maximize o desempenho total da estrutura;

5.3 Limitações e Trabalhos Futuros 90

• Fazer uso da API Java nio 1 para acesso a arquivos via operações de entrada e saída(E/S) que foi remodelada oferecendo melhoria de performance em relação a uso debu�ers e outras facilidades de acesso a operações de E/S que poderiam ser úteispara incrementar o desempenho no acesso e gerenciamento do índice VIF.

1java.sun.com/j2se/1.4.1/docs/guide/nio/

91

Referências Bibliográ�cas

[1] I. H. Witten, A. Mo�at, and T. C. Bell. Managing Gigabytes. Morgan Kaufman,second edition, 1999.

[2] S. Lawrence and C. L. Giles. Accessibility of information on the web. Nature,400:107�109, December 1999.

[3] B. H. Murray and A. Moore. Sizing the internet. White Paper, July 2000.[4] M. Levene, T. I. Fenner, G. Loizou, and R. Wheeldon. A stochastic model for the

evolution of the web. Computer Networks, 39(3):277�287, 2002.[5] Google, Aug 2003. http://www.google.com.[6] J. Cho and H. Garcia-Molina. The evolution of the web and implications for an

incremental crawler. In Proc. of the 26th Inter. Conf. on Very Large Databases,2000.

[7] Radix.com :: Acha mais e melhor!, Aug 2003. http://www.radix.com.br.[8] BRIGHT - BRazilian Internet Guide in Hyper-Text. Projeto do engenho de busca

para a Web brasileira vinculado ao CNPq desenvolvido no Cin-UFPE e no Centrode Estudos Avançados do Recife (CESAR).

[9] R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison Wesley,1999.

[10] C. J. van Rijsbergen. Information Retrieval. ALondon: Butterworths, 2ª edition,1979.

[11] V. V. Raghavan. What do you say after you say, 'i work in ir' ? cite-seer.nj.nec.com/144923.html, 1991.

[12] H. S. Heaps. Information retrieval, computational and theoretical aspects. AcademicPress, 1978.

[13] E. Fox, D. Harman, R. Baeza-Yates, and W. Lee. Inverted �les. In W. B. Frakesand R. Baeza-Yates, editors, Information Retrieval: Data Structure and Algorithms,chapter 3, pages 28�43. Prentice Hall, 1992.

[14] G. Zipf. Human Behaviour and the Principle of the Least E�ort. Addison-Wesley,1949.

[15] G. Salton and M. J. McGill. Introduction to Modern Information Retrieval. McGraw-Hill, 1983.


[16] K. Yang. Literature review, January 2001. Doctoral Dissertation Committee: R.M. Losee, G. Marchionini, G. B. Newby, P. Solomon and E. Voorhees. School ofInformation and Library Science University of North.

[17] M. Levene and A. Poulovassilis. Web dynamics. International Workshop on Webdynamics, 1(4):881�885, January 2001.

[18] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomp-kins, and J. Wiener. Graph structure in the web. Proc. of the 9th WWW Conference,2000.

[19] J. Cho and H. Garcia-Molina. Estimating frequency of change. ACM Transactionson Internet Technology, 3(3):256�290, August 2003.

[20] S. Brin, R. Motwani, L. Page, and T. Winograd. What can you do with the web inyour pocket?, 1998. Data Engineering Bulletin.

[21] J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACMSTAM Symposium on Discrete Algorithms, 1998.

[22] R. S. Coelho. SAAL - um sistema para armazenamento e análise da estrutura delinks da web. Master's thesis, Universidade Federal de Pernambuco, 2002.

[23] L. A. Barbosa. Uma proposta para a atualização da base de dados em engenhos debusca utilizando classi�cadores. Master's thesis, Universidade Federal de Pernam-buco, 2003.

[24] R. Baeza-Yates. Searching the web: Challenges and partial solutions. IBERAMIA'98,1998.

[25] A. Broder, S. Galssman, M. Manasse, and G. Zweig. Systactic clustering of the web.WWW Conference, 6:391�404, 1997.

[26] N. Shivakumar and H. Garcia-Molina. Finding near-replicas of documents on theweb. Workshop of Web Databases, 1998.

[27] C. Faloustsos and S.Christodoulakis. Signature �les: An access method for documentsand its analytical performance evaluation. ACM Transactions on O�ce InformationSystems, 1984.

[28] D. R. Morrison. Patricia � practical algorithm to retrieve information coded inalphanumeric. Journal of the ACM, 15(4):514�534, October 1968.

[29] P. Weiner. Linear pattern matching algorithms. 14th Annual IEEE Symposium onSwitching and Automata Theory, pages 1�11, 1973.

[30] E. McCreight. A space-economical su�x tree construction algorithm. Journal of theACM, 23(2):262�272, April 1976.

[31] E. Ukkonen. On-line construction of su�x trees. Algorithmica, 14(3):249�260, 1995.[32] G. Gonnet and R. Baeza-Yates. New indices for text: Pat trees. In W. B. Frakes

and R. Baeza-Yates, editors, Information Retrieval: Data Structure and Algorithms,pages 66�82. Prentice Hall, 1992.


[33] U. Manber and G. Myers. Su�x arrays: a new method for on-line string searches.SIAM Journal on Computing, 22(5):935�948, October 1993.

[34] C. Faloustsos. Access methods for text. ACM Computing Surveys, 17(1):49�74,March 1985.

[35] A. Tomasic, H. Garcia-Molina, and K. Shoens. Incremental updates of inverted listsfor text document retrieval. ACM SIGMOD Record, pages 289�300, May 1994.

[36] E. W. Brown, J. P. Callan, and W. B. Croft. Fast incremental indexing for full-textinformation retrieval. Proceedings of the 20th International Conference on Very LargeDatabases (VLDB), pages 192�202, September 1994.

[37] J. Zobel, A. Mo�at, and K. Ramamohanarao. Inverted �les versus signature �les fortext indexing. ACM Transactions on Database Systems, 23(4):453�490, 1998.

[38] R. Haskin. Special purpose processors for text retrieval. Database Engineering,4(1):16�29, 1981.

[39] T. Bell, A. Mo�at, C. Nevill-Manning, I. Witten, and J. Zobel. Data compression infull-text retrieval systems. Journal of the American Society for Information Science,44(9):508�531, October 1993.

[40] A. J. Kent, R. Sacks-Davis, and K. Ramamohanarao. A signature �le scheme basedon multiple organisations for indexing very large text databases. Journal of theAmerican Society for Information Science, 41(7):508�534, 1990.

[41] R. Sacks-Davis, A. J. Kent, and K. Ramamohanarao. Multikey access methodsbased on superimposed coding thechniques. ACM Transactions on Database Systems,12(4):655�696, December 1987.

[42] D. E. Knuth. The Art of Computer Programming: Sorting and Searching - Vol. 3.Addison Wesley, 1973.

[43] R. Bayer and E. McCreight. Organization and maintenance of large ordered indices.Acta Informatica, 1:173�189, 1972.

[44] D. Comer. The ubiquitous B-tree. Computing Surveys, 11(2):121�137, June 1979.[45] D.A. Hu�man. A method for the construction of minimum redundancy codes. IRE,

40(9):1098�1101, September 1952.[46] J. Ziv and A. Lempel. Compression of individual sequences via variable length coding.

IEEE Trans. On Information Theory, 24(11):530�536, 1978.[47] J. Rissanen and G. G. Langdon. Arithmetic coding. IBM Journal of Research and

Development, 23(2):149�162, March 1979.[48] N. Ziviani, E.Moura, G. Navarro, and R. Baeza-Yates. Compression: A key for next

generation text retrieval systems. IEEE Computer, 33(11):37�44, November 2000.[49] E. S. Moura and N. Ziviani. Construção e�ciente de índices para bases de dados

textuais. Simpósio Brasileiro de Banco de Dados, XV:247�258, Outubro 2000.


[50] F. Scholer, H. E. Williams, J. Yiannis, and J. Zobel. Compression of inverted indexesfor fast query evaluation. SIGIR, pages 215�221, 2002.

[51] P. Elias. Universal codeword sets and representations of the integers. IEEE Tran-sactions on Information Theory, 21(2):194�203, March 1975.

[52] S.W. Golomb. Run-length encoding. IEEE Transactions on Information Theory,12(3):399�401, July 1966.

[53] S. Melnik, S. Raghavan, B. Yang, and H. Garcia-Molina. Building a distributedfull-text index for the web. World Wide Web (WWW10), pages 396�406, 2001.

[54] D. Cutting and J. Pedersen. Optimizations for dynamic inverted index maintenance.Proceedings of the 13th International ACM SIGIR Conference on Research and De-velopment in Information Retrieval, pages 405�411, 1990.

[55] T. Chiueh and L. Huang. E�cient real-time index updates in text retrieval systems.Technical report, State University of New York at Stony Brook, April 1999.

[56] A. Mo�at and J. Zobel. Self indexing inverted �les for fast text retrieval. ACMTransactions on Information Systems, 14(4):349�379, 1996.

[57] C. Silverstein, M. Henzinger, H. Marais, and M. Moricz. Analysis of a very large websearch engine query log. SIGIR Forum, 33(1):6�12, 1999.

[58] J. B. Rocha J. Uma arquitetura distribuída de busca para sistemas de recuperaçãode informação. Master's thesis, Universidade Federal de Pernambuco, 2002.

[59] M. R. Fernandes. Engenhos de busca distribuídos: uma abordagem visando escabi-lidade para crawling e indexação. Master's thesis, Universidade Federal de Pernam-buco, 2002.

[60] G. Booch, J. Rumbaugh, and I. Jacobson. Uni�ed Modeling Language - User Guide.Addison Wesley, 1999.

[61] J. Jannink. Implementing deletion in B+-trees. SIGMOD Record, 24(1):33�38, March1995.

[62] R. Maelbrancke and H. Olivié. Optimizing Jan Jannink's implementation of B+-treedeletion. SIGMOD Record, 24(3):5�7, 1995.

[63] J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Appro-ach. Morgan Kau�man Publishers, 2nd edition edition, 1996.

[64] H. Garcia-Molina, J. D. Ullman, and J. Widom. Database System Implementation.Prentice Hall, 2000.

[65] R. Elmasri and S. Navathe. Fundamentals of Database Systems. Addison-Wesley,2000.

[66] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. M.I.T.Press, 1990.

[67] R. Sedgewick. Algorithms in C++: Parts 1-4. Addison Wesley, 1998.


[68] A. Arasu, J. Cho, H. Garcia-Molina, A. Paepcke, and S. Raghavan. Searching theweb. Technical report, Computer Science Department, Stanford University, 2001.

[69] A. N. Vo and A. Mo�at. Compressed inverted �les with reduced decoding overhe-ads. Proc. ACM-SIGIR Intern. Conf. on Research and Development in InformationRetrieval, pages 290�297, 1998.

[70] J. W. J. Williams. Algorithm 232(heapsort). Communications of the ACM, 7:347�348, 1964.

96

ANEXO A -- Algoritmo de Counting-Sort

Pseudo-código para o algoritmo de ordenação em tempo linear descrito em [66]. Paraque o algoritmo execute em tempo linear é necessário um array auxiliar de tamanhoM para o controle da freqüência dos valores de entrada onde o tempo de execução doalgoritmo é O(n + M).Algoritmo 3Procedimento CountingSort(A, n, B, C,M)Entrada: Array de entrada A de tamanho n, Array de controle C de tamanho MSaída: B array de saída com valores de A ordenados(∗ ordena os valores de A usando array de controle C ∗)(∗ onde os valores de A devem estar no intervalo A[i] ∈ [0, M) ∗)1. para i← 0 até M − 12. faça C[i]← 03. para i← 0 até n− 14. faça C[A[i]]← C[A[i]] + 15. para i← 1 até M − 16. faça C[i]← C[i] + C[i− 1]7. para i← n− 1 decrescente até 08. faça C[A[i]]← C[A[i]]− 19. B[C[A[i]]]← A[i]

Figura 36: Pseudo-código do algoritmo de counting sort

97

ANEXO B -- Fila de Prioridades

Uma Fila de Prioridades [70, 66, 67] é uma estrutura usada para manter um conjuntode elementos suportando três operações neste conjunto: (i) insert(x): que insere o ele-mento x na �la; (ii) max(): que retorna o maior elemento da �la e (iii) removeMax():que retira o maior elemento da �la. Na Figura 37 é mostrado o código-fonte da classe emLinguagem Java para a Fila de Prioridades baseado na implementação de Sedgewick [67].

Anexo B -- Fila de Prioridades 98

public class PriorityQueue {

private Comparable[] elements;

private int size;

public PriorityQueue(int capacity) {

this.elements = new Comparable[capacity + 1];

this.size = 0;

}

public int size() {

return size;

}

public Object max() {

return elements[1];

}

public void insert(Comparable item) {

elements[++size] = item;

fixUp(elements, size);

}

private void exch(Comparable[] a, int i, int j) {

Comparable aux = a[i];

a[i] = a[j];

a[j] = aux;

}

public Object removeMax() {

exch(elements, 1, size);

fixDown(elements, 1, size - 1);

return elements[size--];

}

private void fixUp(Comparable[] a, int k) {

while (k > 1 && a[k / 2].compareTo(a[k]) < 0) {

exch(a, k, k / 2);

k = k / 2;

}

}

private void fixDown(Comparable[] a, int k, int N) {

while (2 * k <= N) {

int j = 2 * k;

if (j < N && a[j].compareTo(a[j + 1]) < 0)

j++;

if (!(a[k].compareTo(a[j]) < 0))

break;

exch(a, k, j);

k = j;

}

}

}

Figura 37: Código-fonte em Linguagem Java para a Fila de Prioridades

99

ANEXO C -- Tabelas do Teste deProcessamento de Consultas

Este anexo descreve as tabelas com os tempos do teste de processamento de consultascom mais detalhes do que o mostrado na Seção 4.5.3. As Tabelas 16 e 17 expõem ostempos do processo gerador da cache estática em milisegundos sobre o arquivo contendotodas as 10.000 (dez mil) consultas mais realizadas ao Radix usando o processamento comotimização de salto em blocos (Tabela 16) e sem otimização (Tabela 17). As Tabelas 18 e19 são do mesmo procedimento de geração da cache estática mas considerando apenas asconsultas com mais de um termo. Abaixo(Tabela 15) segue a distribuição da quantidadede consultas por número de termos por consulta.

Número deTermos naconsultaPercentualde consultas

1 56.47%2 38.86%3 4.12%4 0.43%5 0.12%Total maisde 1 termo 43.53%

Tabela 15: Percentual de consultas por quantidade de termos das 10.000 consultas maisrealizadas no engenho

Tamanho do bloco Média(ms) Máximo(ms) Mínimo(ms) Mediana(ms) Desvio256B 211,471 7070 0 62 434,471512B 185,665 5860 0 57 371,5381KB 171,240 5620 0 52 337,8272KB 170,151 5224 0 54 329,8104KB 165,052 5260 1 51 318,6038KB 166,933 5087 2 52 321,74816KB 171,373 5042 4 57 321,25632KB 188,098 5035 10 70 334,49564KB 221,756 5368 16 103 343,271

Tabela 16: Tempo de Processamento da cache estática com otimização de salto em blocos

Anexo C -- Tabelas do Teste de Processamento de Consultas 100


Tabela 17: Tempo de Processamento da cache estática sem otimização


Tabela 18: Tempo de processamento da cache estática com salto de blocos para consultascom mais de um termo


Tabela 19: Tempo de processamento da cache estática sem otimização para consultas commais de um termo

101

ANEXO D -- Grá�cos do Teste de Carga

Figura 38: Comparativo do tempo de resposta de cada consulta ao longo do tempo parao teste sobre o índice VIF e sobre o indice IF+PL com carga de 1 consulta a cada 1000ms


Figura 39: Comparativo do tempo de resposta de cada consulta ao longo do tempo parao teste sobre o índice VIF e sobre o indice IF+PL com carga de 1 consulta a cada 500 ms




Figura 42: Comparativo do �uxo de consultas ao longo do tempo durante o teste de cargaaplicado aos índices VIF e IF+PL sobre uma carga de 1 consulta a cada 1000 ms




Documents

VIF - Uma estrutura de índice invertido em blocos baseada ... · Dissertação de Mestrado sob o título VIF - Uma Estrutura de Índice Invertido em Bloosc Baseada em uma B +-Tree