Matheus Barbosa Silva - NUSP: 11221741

Supervisor: Prof. Dr. Guilherme Oliveira Mota

Cossupervisor: Prof. Dr. Yoshiharu Kohayakawa


Resumo

Responder se um dado elemento faz parte de um conjunto é um problema recorrente em diversas aplicações computacionais. Para conjuntos com muitos elementos, o emprego de soluções determinísticas convencionais pode ser inviável. Portanto, nesses casos a aplicação de estruturas de dados probabilísticas pode ser vantajosa de modo a prover respostas a testes de membresia com mais agilidade, ao custo de resultados falsos positivos -- como ocorre nos Bloom filters. A técnica de cuckoo hashing é utilizada pelo cuckoo filter, estrutura de dados probabilística capaz de responder a testes de membresia. Essa é uma estrutura alternativa aos Bloom filters que usualmente apresenta melhor desempenho de consultas e menor consumo de espaço em várias aplicações práticas. Analisa-se comparativamente o desempenho de cada um dos filtros aplicados em um algoritmo hifenizador de palavras.

Proposta

Acessar

Monografia

Acessar

Slides

Acessar

Repositório

Acessar