Algoritmos de espaço quase ótimo para hashing perfeito

AUTOR(ES)
DATA DE PUBLICAÇÃO

2008

RESUMO

Uma função hash perfeita (FHP) h : S ? [0, m - 1] para um conjunto de chaves S ? U de tamanho n, onde m = n e U é um universo de chaves, é uma função injetora que mapeia as chaves de S para valores únicos. Uma função hash perfeita mínima (FHPM) é uma FHP com m = n, o menor intervalo possível. Funções hash perfeitas mínimas são amplamente utilizadas para armazenamento eficiente e recuperação rápida de itens de conjuntos estáticos, como palavras em linguagem natural, palavras reservadas em linguagens de programação ou sistemas interativos, URLs (universal resource locations) em máquinas de busca, ou conjuntos de itens em técnicas de mineração de dados. Nesta tese nós apresentamos um algoritmo de hashing perfeito altamente escalável e de espço quase ótimo. A avaliação de uma FHP sobre um dado elemento de S requer tempo constante, e a fase dominante no algoritmo de construção consiste da ordenação de n fingerprints de O(log n) bits em tempo O(n). A utilização de espaço depende da relação entre m e n. Para m = n a utilização de espaço está dentro do intervalo 2,62n à 3,3n bits, dependendo das constantes envolvidas nas fases de construção e avaliação. Para m = 1,23n a utilização de espaço está dentro do intervalo 1,95n à 2,7n bits. Em todos os casos, isto está distante por um pequeno fator constante do mínimo teórico de aproximadamente 1,44n bits para FHPMs e 0,89n bits para FHPs, uma coisa que não foi alcançada por algoritmos anteriores, exceto assintóticamente para valores de n muito grandes. Esta pequena utilização de espaço permitiu o uso de FHPMs em aplicações para as quais elas não eram úteis no passado. Nós demonstramos a escalabilidade do nosso algoritmo ao construir uma FHPM para um conjunto de 1,024 bilhões de URLs da World Wide Web de tamanho médio igual a 64 caracteres em aproximadamente 50 minutos, usando um PC comodite. Nós também apresentamos uma implementação paralela do algoritmo, a qual gera uma FHPM para o mesmo conjunto de URLs, usando um cluster de 14 computadores, em aproximadamente 4 minutos, alcançando um speedup quase linear. Além disso, para 14,336 bilhões de números inteiros de 16 bytes gerados aleatoriamente e distribuídos entre as 14 máquinas participantes, o algoritmo gera uma FHPM em aproximadamente 50 minutos, com uma degradação de desempenho de 20%.

ASSUNTO(S)

computação teses. estrutura de dados (computação) teses. algoritmos de computador teses. organização de arquivos (computação) teses. hashing (computação) teses.

ACESSO AO ARTIGO

Documentos Relacionados