Pesquisas apoiadas pelo UOL

Conheça alguns trabalhos de pesquisa feitos com o apoio do UOL:

Adding Compression to Block Addressing Inverted Indexes

Gonzalo Navarro, Edleno Silva de Moura, Marden S. Neubert, Nivio Ziviani, Ricardo A. Baeza-Yates

Algoritmos Distribuídos para a Construção de Arquivos Invertidos

Marden S. Neubert; Orientador: Nivio Ziviani

Analyzing Client Interactivity in Streaming Media

Cristiano Costa, Italo Cunha, Alex Borges, Claudiney Ramos, Marcus Rocha, Jussara Almeida e Berthier Ribeiro-Neto

Detecção de Comunidades Baseados em Interesse para Serviços Web

Rodrigo Barra de Almeida, orientador: Virgílio Augusto Fernandes Almeida

Efficient Distributed Algorithms to Build Inverted Files

Berthier A. Ribeiro-Neto, Edleno Silva de Moura, Marden S. Neubert, Nivio Ziviani

Realimentação de Exemplos na Extração de Dados Semi-Estruturados (Example Feedback in Re Extraction of Semi-Structured Data)

Karine Gomes Chaves; Orientadores: Alberto H. F. Laender, Berthier Ribeiro-Neto

Adding Compression to Block Addressing Inverted Indexes

Gonzalo Navarro, Edleno Silva de Moura, Marden S. Neubert, Nivio Ziviani, Ricardo A. Baeza-Yates

Inverted index compression, block addressing and sequential search on compressed text are three techniques that have been separately developed for efficient, low-overhead text retrieval. Modern text compression techniques can reduce the text to less than 30% of its size and allow searching it directly and faster than the uncompressed text. Inverted index compression obtains significant reduction of their original size at the same processing speed. Block addressing makes the inverted lists point to text blocks instead of exact positions and pay the reduction in space with some sequential text scanning.

In this work we combine the three ideas in a single scheme. We present a compressed inverted file that indexes compressed text and uses block addressing. We consider different techniques to compress the index and study their performance with respect to the block size. We compare the index against three separate techniques for varying block sizes, showing that our index is superior to each isolated approach. For instance, with just 4% of extra space overhead the index has to scan less than 12% of the text for exact searches and about 20% allowing one error in the matches.

Algoritmos Distribuídos para a Construção de Arquivos Invertidos

Marden S. Neubert; Orientador: Nivio Ziviani

Este trabalho apresenta uma família de algoritmos distribuídos visando a construção de arquivos invertidos globais para grandes volumes de texto. Dada uma coleção de documentos textuais distribuída entre várias estações de trabalho, um arquivo invertido global é um índice que permite a busca eficiente de informações no texto distribuído como um todo. Esse índice é composto por duas partes: o vocabulário global, isto é, o conjunto de palavras distintas presentes no texto distribuído, e as listas de ocorrências globais, que apontam para os documentos da coleção nos quais cada palavra do vocabulário ocorre.

O ambiente de operação considerado é uma rede de alta velocidade, pela qual as estações de trabalho possam se comunicar com pouca ou nenhuma contenção. As análises supõem que o texto encontra-se distribuído igualmente entre as estações e que o índice invertido a ser gerado é consideravelmente maior que a quantidade de memória principal disponível no ambiente.

As listas de ocorrências são ordenadas pela freqüência dos termos nos documentos e comprimidas de forma a reduzir as demandas de espaço e o volume de dados transferidos pelos discos e pela rede.

Três algoritmos distribuídos são discutidos e seus resultados analíticos e experimentais são comparados. Os experimentos mostram que, utilizando-se quatro estações de trabalho, o mais eficiente desses algoritmos é capaz de indexar 3 gigabytes de texto em menos de 14 minutos. As análises indicam que, no mesmo ambiente de experimentação, é possível indexar uma coleção de 100 gigabytes em menos de 6 horas.

Analyzing Client Interactivity in Streaming Media

Cristiano Costa, Italo Cunha, Alex Borges, Claudiney Ramos, Marcus Rocha, Jussara Almeida e Berthier Ribeiro-Neto

This paper provides an extensive analysis of pre-stored streaming media workloads, focusing on the client interactive behavior.

We analyze four workloads that fall into three different domains, namely, education, entertainment video and entertainment audio.

Our main goals are: (a) to identify qualitative similarities and differences in the typical client behavior for the three workload classes and (b) to provide data for generating realistic synthetic workloads.

Detecção de Comunidades Baseados em Interesse para Serviços Web

Rodrigo Barra de Almeida, orientador: Virgílio Augusto Fernandes Almeida

A experiência comum sugere que usuários de serviços Web podem ser agrupados em comunidades tendo como base seus interesses. A recente pesquisa sobre algoritmos para a identificação de comunidades na Web tem foco em técnicas que utilizam a estrutura de ligação entre páginas (e.g, hyperlinks). Neste trabalho, apresentamos uma técnica para identificação de comunidades de interesse em serviços Web. Ao invés de utilizarmos estruturas da ligação conectando páginas, propomos um algoritmo baseado no comportamento apresentado pelos acessos dos usuários do serviço. Um grafo é criado tendo como base os padrões de acesso dos usuários e é mostrada sua capacidade de reter propriedades úteis para identificação de comunidades. Aplicamos o algoritmo proposto a uma série de dados sintéticos, construídos de forma a apresentar comunidades de interesse, e utilizamos os resultados como forma de comparação entre nosso algoritmo e outras metodologias similares. Além disso, aplicamos o algoritmo a dois serviços reais disponíveis na Web: uma livraria virtual e uma rádio online. Os estudos de caso são relevantes porque enfatizam a contribuição do algoritmo quando se deseja encontrar comunidades em um ambiente sem estruturas explícitas que representem relacionamentos entre usuários. Também apresentamos uma máquina de busca baseada em comunidades como forma de demonstrar a utilidade da técnica proposta.

Efficient Distributed Algorithms to Build Inverted Files

Berthier A. Ribeiro-Neto, Edleno Silva de Moura, Marden S. Neubert, Nivio Ziviani

We present three distributed algorithms to build global inverted files for very large text collections. The distributed environment we use is a high bandwidth network of workstations with a shared-nothing memory organization. The text collection is assumed to be evenly distributed among the disks of the various workstations. Our algorithms consider that the total distributed main memory is considerably smaller than the inverted file to be generated. The inverted file is compressed to save memory and disk space and to save time for moving data in/out disk and across the network.

We analyze our algorithms and discuss the tradeoffs among them. We show that, with 8 processors and 16 megabytes of RAM available in each processor, the advanced variants of our algorithms are able to invert a 100 gigabytes collection (the size of the very large TREC-7 collection) in roughly 8 hours. Using 16 processors this time drops to roughly 4 hours.

Realimentação de Exemplos na Extração de Dados Semi-Estruturados (Example Feedback in Re Extraction of Semi-Structured Data)

Karine Gomes Chaves; Orientadores: Alberto H. F. Laender, Berthier Ribeiro-Neto

Este trabalho tem por objetivo estender a ferramenta DEByE-Data Extraction by Example- que é uma ferramenta para extração de dados semi-estruturados baseada em exemplos, de modo a dotá-la de características reativas possibilitando a realimentação de exemplos. Esta ferramenta consiste de dois módulos, uma interface gráfica que auxilia o usuário na especificação de exemplos de objetos existentes em página de uma fonte Web e um extrator. Os exemplos fornecidos pelo usuário são posteriormente usados para gerar padrões de extração de objetos. Através do uso desses padrões, o extrator recupera outras páginas da Web, com o mesmo contexto do exemplo fornecido, que sejam relevantes para o usuário. Experimentos realizados com a ferramenta indicaram que se o usuário pudesse retornar ao exemplo fornecido e modificá-lo, o resultado da extração poderia ser melhorado. Baseado nisso, serão incorporadas à ferramenta facilidades para realimentação dos exemplos especificados.