( PDF ) Algoritmos de espaço quase ótimo para hashing perfeito

Download PDF

ads:

Fabiano Cupertino Botelho

Orientador - Nivio Ziviani

Algoritmos de Espa¸co Quase

Otimo

Para Hashing Perfeito

Tese de doutorado apresentada ao Pro-

grama de P´os-Gradua¸c˜ao em Ciˆencia da

Computa¸c˜ao da Universidade Federal de

Minas Gerais, como requisito parcial para

a obten¸c˜ao do grau de Doutor em Ciˆencia

da Computa¸c˜ao.

Belo Horizonte

29 de Setembro de 2008

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

ads:

A minha querida esposa Jana´ına.

Aos meus queridos pais Maria L´ucia e Jos´e V´ıtor.

As minhas queridas irm˜as Gleiciane e Cristiane.

Agradecimentos

A Deus por ter concedido a mim vida e sabedoria para realizar um sonho de infˆancia e

pela grande ajuda nos momentos dif´ıceis.

A minha querida esposa Jana´ına Marcon Machado Botelho pelo amor, compreens˜ao pelos

v´arios momentos em que n˜ao pude lhe dar a aten¸c˜ao merecida, companheirismo e

incentivo durante momentos nos quais tive vontade de desistir de tudo. Obrigado

Jana por compartilhar comigo sua vida e as vit´orias conquistadas durante todo o

doutorado. Com a gra¸ca de Deus em nossas vidas continuaremos a ser muito felizes.

Aos meus queridos pais Maria L´ucia de Lima Botelho e Jos´e Vitor Botelho pelos sacrif´ıcios

realizados no passado que deram suporte para esta conquista.

As minhas queridas irm˜as Cristiane Cupertino Botelho e Gleiciane Cupertino Botelho,

pelo carinho e amor das duas melhores irm˜as do mundo.

Aos meus queridos tios M´arcia Novaes Alves e Sud´ario Alves, os quais sempre me acol-

heram com todo carinho, dando muito apoio durante todo o doutorado.

Ao Prof. Nivio Ziviani pelo excelente trabalho de orienta¸c˜ao e pelo exemplo de proﬁs-

sionalismo e dedica¸c˜ao ao trabalho. Sua grande experiˆencia em pesquisa acadˆemica

e, em especial, nas ´areas de recupera¸c˜ao de informa¸c˜ao e de algoritmos foram fun-

damentais para a realiza¸c˜ao desta tese. Al´em disto, seu excelente apoio, aten¸c˜ao

e incentivo foram de suma importˆancia n˜ao somente para realiza¸c˜ao do doutorado,

como tamb´em, para minha forma¸c˜ao acadˆemica e proﬁssional.

Ao Prof. Rasmus Pagh com quem tanto aprendi sobre t´ecnicas de projeto e an´alise

de algoritmos de hashing, sendo crucial sua participa¸c˜ao durante a realiza¸c˜ao deste

trabalho de tese.

Ao Prof. Yoshiharu Kohayakawa pela aten¸c˜ao dedicada nas discuss˜oes que contribuiram

para melhorar a qualidade deste trabalho. Agrade¸co tamb´em por receber-me no

Instituto de Matem´atica e Estat´ıstica da Universidade de S˜ao Paulo e por todo apoio

dado ao meu trabalho no per´ıodo em que estive em S˜ao Paulo.

Ao Prof. Edleno Silva de Moura pela conﬁan¸ca depositada em mim e pelo incentivo

de sempre. Agrade¸co tamb´em por receber-me no Departamento de Ciˆencia da Com-

puta¸c˜ao da Universidade Federal do Amazonas no per´ıodo em que estive em Manaus.

Aos demais membros da banca, professores Gaston Gonnet, Antˆonio Alfredo Loureiro,

Wagner Meira Jr. e Jayme Luiz Szwarcﬁter por terem aceitado participar da avalia¸c˜ao

desta tese e pelas cr´ıticas e sugest˜oes pertinentes.

A Djamal Belazzougui pelas sugest˜oes e contribui¸c˜oes inteligentes feitas a este trabalho

de tese e `a biblioteca CMPH.

A Davi Reis por ter concebido a id´eida da biblioteca CMPH, a qual foi fundamental para

divulgar os resultados obtidos nesta tese.

Ao colega e amigo Marco Antˆonio Pinheiro de Cristo pelos divertidos momentos que

passamos juntos durante nossas aulas de inglˆes e pelo incentivo de sempre.

Ao colega e amigo Thierson Couto pela amizade, e por estar sempre pronto a colaborar.

Ao colega e amigo David Menoti pelas discuss˜oes, sugest˜oes e cr´ıticas que muito con-

tribuiram no in´ıcio deste trabalho de tese.

Ao colega e amigo David Fernandes por ter me recebido em sua casa durante o per´ıodo

que passei em Manaus e pela amizade de sempre.

Aos colegas e amigos do nosso grande e inesquec´ıvel time de futebol Curucu e as suas

respectivas esposas pela amizade conquistada durante o per´ıodo em que passamos

juntos. Obrigado Pedro Neto, Maur´ıcio Figueiredo, Eduardo Freire Nakamura,

Ruiter Caldas, Andr´e Lins, Jos´e Pinheiro, Guillermo Camara Chavez, Martin Gomez

Ravetti, David Patricio Viscarra del Pozo e David Menotti pelos momentos super

divertidos que serviram para aliviar o estresse desse dif´ıcil per´ıodo de doutorado.

Aos colegas e amigos do per´ıodo de gradua¸c˜ao que, por meio da lista de discuss˜ao intri-

gas99, sempre me apoiaram estando perto ou distantes. Agrade¸co a todos tamb´em

pelas boas risadas que dei ao ler os emails da lista, o que com certeza ajudou e muito

a aliviar a tens˜ao em momentos dif´ıceis.

Aos colegas e amigos do Laborat´orio para Tratamento da Informa¸c˜ao (LATIN) An´ısio

Mendes Lacerda,

Alvaro Pereira Jr., Charles Ornelas Almeida, Claudine Santos

Badue, Daniel Galinkin, Denilson Pereira, Guilherme Vale Menezes, Hendrickson R.

Langbehn, Humberto Mossri, Marco Antˆonio Pinheiro de Cristo, Marco Aur´elio Bar-

reto Modesto, P´avel Calado e Wladmir Cardoso Brand˜ao pelas cr´ıticas e sugest˜oes

dadas durante a prepara¸c˜ao da defesa e pelo clima de amizade que estabelecemos

dentro do LATIN.

Aos professores e funcion´arios do Departamento de Ciˆencia da Computa¸c˜ao da Univer-

sidade Federal de Minas Gerais que de v´arias formas contribu´ıram para a conclus˜ao

deste trabalho.

Aos professores e funcion´arios do Departamento de Computa¸c˜ao do Centro Federal de

Educa¸c˜ao Tecnol´ogica de Minas Gerais por terem me recebido t˜ao bem e com tanto

respeito para integrar a equipe do Departamento.

As bolsas concedidas pelos ´org˜aos de fomento CAPES (Coordena¸c˜ao de Aperfei¸coamento

de Pessoal de N´ıvel Superior) e CNPq (Conselho Nacional de Desenvolvimento

Cient´ıﬁco e Tecnol´ogico), as quais serviram como subs´ıdio durante o tempo dedi-

cado a este trabalho de tese.

Abstract

A perfect hash function (PHF) h : S → [0, m − 1] for a key set S ⊆ U of size n, where

m ≥ n and U is a key universe, is an injective function that maps the keys of S to unique

values. A minimal perfect hash function (MPHF) is a PHF with m = n, the smallest possi-

ble range. Minimal perfect hash functions are widely used for memory eﬃcient storage and

fast retrieval of items from static sets, such as words in natural languages, reserved words

in programming languages or interactive systems, universal resource locations (URLs) in

web search engines, or item sets in data mining techniques.

In this thesis we present a simple, highly scalable and near-space optimal perfect hashing

algorithm. Evaluation of a PHF on a given element of S requires constant time, and the

dominating phase in the construction algorithm consists of sorting n ﬁngerprints of O(log n)

bits in O(n) time. The space usage depends on the relation between m and n. For m = n

the space usage is in the range 2.62n to 3.3n bits, depending on the constants involved

in the construction and in the evaluation phases. For m = 1.23n the space usage is in

the range 1.95n to 2.7n bits. In all cases, this is within a small constant factor from the

information theoretical minimum of approximately 1.44n bits for MPHFs and 0.89n bits for

PHFs, something that has not been achieved by previous algorithms, except asymptotically

for very large n. This small space usage opens up the use of MPHFs to applications for

which they were not useful in the past.

We demonstrate the scalability of our algorithm by constructing an MPHF for a set of

1.024 billion URLs from the World Wide Web of average length 64 characters in approx-

imately 50 minutes, using a commodity PC. We also present a distributed and parallel

implementation of the algorithm, which generates an MPHF for the same URL set, using

a 14 computer cluster, in approximately 4 minutes, achieving an almost linear speedup.

Also, for 14.336 billion 16-byte random integers distributed among the 14 participating ma-

chines, the algorithm outputs an MPHF in approximately 50 minutes, with a performance

degradation of 20%.

Resumo

Uma fun¸c˜ao hash perfeita (FHP) h : U → [0, m −1] para um conjunto de chaves S ⊆ U

de tamanho n, onde m ≥ n e U ´e um universo de chaves, ´e uma fun¸c˜ao injetora que

mapeia as chaves de S para valores ´unicos. Uma fun¸c˜ao hash perfeita m´ınima (FHPM)

´e uma FHP com m = n, o menor intervalo poss´ıvel. Fun¸c˜oes hash perfeitas m´ınimas s˜ao

amplamente utilizadas para armazenamento eﬁciente e recupera¸c˜ao r´apida de itens de con-

juntos est´aticos, como palavras em linguagem natural, palavras reservadas em linguagens

de programa¸c˜ao ou sistemas interativos, URLs (universal resource locations) em m´aquinas

de busca, ou conjuntos de itens em t´ecnicas de minera¸c˜ao de dados.

Nesta tese n´os apresentamos um algoritmo de hashing perfeito altamente escal´avel e

de espa¸co quase ´otimo. A avalia¸c˜ao de uma FHP sobre um dado elemento de S requer

tempo constante, e a fase dominante no algoritmo de constru¸c˜ao consiste da ordena¸c˜ao

de n ﬁngerprints de O(log n) bits em tempo O(n). A utiliza¸c˜ao de espa¸co depende da

rela¸c˜ao entre m e n. Para m = n a utiliza¸c˜ao de espa¸co est´a dentro do intervalo 2, 62n

`a 3, 3n bi ts, dependendo das constantes envolvidas nas fases de constru¸c˜ao e avalia¸c˜ao.

Para m = 1, 23n a utiliza¸c˜ao de espa¸co est´a dentro do intervalo 1, 95n `a 2, 7n bits. Em

todos os casos, isto est´a distante por um pequeno fator constante do m´ınimo te´orico de

aproximadamente 1, 44n bits para FHPMs e 0, 89n bits para FHPs, uma coisa que n˜ao

foi alcan¸cada por algoritmos anteriores, exceto assint´oticamente para valores de n muito

grandes. Esta pequena utiliza¸c˜ao de espa¸co permitiu o uso de FHPMs em aplica¸c˜oes para

as quais elas n˜ao eram ´uteis no passado.

N´os demonstramos a escalabilidade do nosso algoritmo ao construir uma FHPM para

um conjunto de 1, 024 bilh˜oes de URLs da World Wide Web de tamanho m´edio igual a

64 caracteres em aproximadamente 50 minutos, usando um PC comodite. N´os tamb´em

apresentamos uma implementa¸c˜ao distribu´ıda e 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¸cando um speedup quase linear. Al´em disso, para 14, 336

bilh˜oes de n´umeros inteiros de 16 bytes gerados aleatoriamente e distribu´ıdos entre as 14

m´aquinas participantes, o algoritmo gera uma FHPM em aproximadamente 50 minutos,

com uma degrada¸c˜ao de desempenho de 20%.

Artigos Publicados

1. F.C. Botelho, Y. Kohayakawa, and N. Ziviani. A practical minimal perfect hashing

method. In Proceedings of the 4th International Workshop on Eﬃcient and Experi-

mental Algorithms (WEA’05), pages 488–500. Springer LNCS vol. 3503, 2005.

2. F.C. Botelho, R. Pagh, and N. Ziviani. Simple and Space-Eﬃcient Minimal Perfect

Hash Functions. In Proceedings of the 10th Workshop on Algorithms and Data

Structures (WADS’07), pages 139–150. Springer LNCS vol. 4619, 2007.

3. F.C. Botelho, and N. Ziviani. External Perfect Hashing for Very Large Key Sets.

In Proceedings of the 16th Conference on Information and Knowledge Management

(CIKM’07), pages 653–662, ACM Press, 2007.

4. F.C. Botelho, D. Galinkin, W. Meira Jr., and N. Ziviani. Distributed Perfect Hashing

for Very Large Key Sets. In Proceedings of the 3rd International ICST Conference

on Scalable Information Systems (InfoScale’08), Naples, Italy, June 2008.

5. F.C. Botelho, H.R. Langbehn, G.V. Menezes, and N. Ziviani. Indexing Internal

Memory with Minimal Perfect Hash Functions. In Proceedings of the 23rd Brazilian

Symposium on Database (SBBD’08), Campinas, Brazil, October 2008.

Resumo Estendido

Introdu¸c˜ao

A necessidade de acesso `a itens com base no valor de uma chave ´e omnipresente em ´areas

como inteligˆencia artiﬁcial, estruturas de dados, banco de dados, minera¸c˜ao de dados e recu-

pera¸c˜ao de informa¸c˜ao. Alguns tipos de bases de dados s˜ao atualizados apenas raramente,

geralmente por atualiza¸c˜oes peri´odicas feitas em lote. Isso ´e verdade, por exemplo, para a

maioria das aplica¸c˜oes em data warehousing (veja [71] para mais exemplos e discuss˜oes).

Em tais cen´arios, ´e poss´ıvel melhorar o desempenho do processamento de consultas por

meio da utiliza¸c˜ao de fun¸c˜oes hash perfeitas m´ınimas para criar representa¸c˜oes compactas

das chaves.

Em aplica¸c˜oes onde o conjunto de chaves ´e ﬁxo por um longo per´ıodo de tempo, a

constru¸c˜ao de uma fun¸c˜ao hash perfeita m´ınima pode ser feita como parte da fase de

pr´e-processamento. Por exemplo, aplica¸c˜oes OLAP (On-Line Analytical Processing) fazem

uso extensivo de pr´e-processamento de dados para otimizar ao m´aximo o processamento

de certos tipos de consultas. Mais formalmente, dado um conjunto est´atico de chaves

S ⊆ U de tamanho n, sendo suas chaves provenientes de um universo de chaves U de

tamanho u, onde cada chave est´a associada com dados sat´elites, a quest˜ao que n´os estamos

interessados ´e: quais s˜ao as estruturas de dados que proporcionam o melhor compromisso

entre utiliza¸c˜ao de espa¸co e tempo de consulta?

A utiliza¸c˜ao de uma tabela indexada por uma fun¸c˜ao hash consiste em uma estrutura

de dados que permite a realiza¸c˜ao de consultas eﬁcientemente (custo constante no caso

m´edio). Considerando S ⊆ U e dada uma chave x ∈ S, uma fun¸c˜ao hash h computa um

inteiro no intervalo [0, m − 1] para o armazenamento ou recupera¸c˜ao de x em uma tabela

hash. M´etodos de hashing para conjuntos de chaves n˜ao est´aticos podem ser usados para

construir estruturas de dados que armazenam S e suportam consultas do tipo “x ∈ S?”

com custo esperado de tempo O(1). No entanto, esses m´etodos envolvem perda de espa¸co

devido a localiza¸c˜oes n˜ao utilizadas na tabela e perda de tempo para resolver colis˜oes

quando duas chaves s˜ao mapeadas para a mesma entrada da tabela.

Hashing perfeito ´e uma forma eﬁciente em espa¸co para criar representa¸c˜oes compactas

de um conjunto est´atico S contendo n chaves. Para aplica¸c˜oes com somente pesquisas com

sucesso, a representa¸c˜ao de uma chave x ∈ S ´e simplesmente o valor de h(x), onde h ´e

uma fun¸c˜ao hash perfeita (FHP) para o conjunto S de valores considerados. A palavra

“perfeita” refere ao fato de que a fun¸c˜ao mapear´a os elementos de S para valores ´unicos.

Fun¸c˜oes hash perfeitas m´ınimas (FHPM) produzem valores que s˜ao inteiros no intervalo

[0, n −1], que ´e o menor intervalo poss´ıvel. A Figura 1(a) ilustra uma fun¸c˜ao hash perfeita

e a Figura 1(b) ilustra uma fun¸c˜ao hash perfeita m´ınima.

0 n−1...21

210

...

m−1

Conjunto de Chaves

Tabela Hash

(a)

Tabela Hash

Conjunto de Chaves

0 n−121

...

(b)

Figura 1: (a) Fun¸c˜ao hash perfeita (b) Fun¸c˜ao hash perfeita m´ınima.

Uma vez que colis˜oes n˜ao ocorrem nas FHPs e FHPMs, cada chave pode ser recuperada

da tabela com um ´unico acesso. FHPMs evitam completamente o problema de desperd´ıcio

de espa¸co e tempo. Melhor ainda, foi observado em [56] que FHPMs tamb´em evitam cache

misses que acontecem devido aos esquemas de resolu¸c˜ao de colis˜oes, como endere¸camento

aberto e encadeamento [51]. Isso ocorre porque tais fun¸c˜oes fazem, no pior caso, um ´unico

acesso `a tabela hash.

Fun¸c˜oes hash perfeitas m´ınimas s˜ao usadas para armazenamento eﬁciente e recupera¸c˜ao

r´apida de itens provenientes de conjuntos est´aticos, tais como palavras em linguagem na-

tural, palavras reservadas em linguagens de programa¸c˜ao ou sistemas interativos, conjun-

tos de itens em t´ecnicas de minera¸c˜ao de dados [21, 22], tabelas de roteamento e outras

aplica¸c˜oes na ´area de redes [66], dados espaciais esparsos [54], compress˜ao de grafos [7] e,

para representar grandes mapas da web [27].

Uma FHP depende completamente do conjunto S de chaves.

E sabido que manter

uma FHP em aplica¸c˜oes dinˆamicas, nas quais ocorrem inser¸c˜oes no conjunto S, ´e somente

poss´ıvel usando espa¸co que ´e super-linear em n [28]. No entanto, neste trabalho n´os

consideramos o caso onde S ´e ﬁxo, e a constru¸c˜ao de uma FHP pode ser feita como parte

do pr´e-processamento dos dados (por exemplo, em aplica¸c˜oes de data warehouse).

Os m´etodos de hashing perfeito conhecidos na literatura n˜ao s˜ao capazes de gerar

fun¸c˜oes que podem ser armazenadas utilizando um n´umero constante de bits por elemento

para conjuntos de dados de tamanhos real´ısticos. Todos os m´etodos anteriores ou sofrem

de um compreendimento te´orico incompleto e, portanto, n˜ao existem garantias de que

eles funcionem bem para qualquer conjunto de chaves, ou n˜ao s˜ao pr´aticos devido a um

procedimento complicado de avalia¸c˜ao da fun¸c˜ao, que na maioria das vezes ´e tamb´em

ineﬁciente.

At´e este trabalho de tese, por causa das limita¸c˜oes dos algoritmos existentes, o uso de

FHPMs era restrito `a cen´arios onde o conjunto de chaves era relativamente pequeno. No

entanto, em muitos casos, a demanda para se tratar conjuntos de chaves muito grandes de

forma eﬁciente est´a crescendo. Por exemplo, m´aquinas de busca est˜ao indexando dezenas

de bilh˜oes de p´aginas e algoritmos como PageRank [16], o qual utiliza o grafo da web

para derivar uma medida de popularidade para p´aginas web, poderia se beneﬁciar de uma

FHPM para mapear URLs que ocupam muitos bytes para n´umeros inteiros que ocupam

poucos bytes e s˜ao utilizados como identiﬁcadores para as p´aginas. Os n´umeros inteiros

obtidos no mapeamento correspondem ao conjunto de v´ertices do grafo da web.

Embora uma quantidade consider´avel de trabalho sobre como construir boas FHPs

tenha sido realizado nos ´ultimos vinte anos na literatura de hashing perfeito, existe uma

lacuna entre teoria e pr´atica em todos os m´etodos de hashing perfeito anteriores. Por um

lado, existem bons resultados te´oricos sem comprova¸c˜ao experimental da sua aplicabili-

dade para grandes conjuntos de chaves. Por outro lado, existem os algoritmos que fazem

suposi¸c˜oes n˜ao real´ısticas para analisarem teoricamente tanto o tempo de execu¸c˜ao quanto

o espa¸co necess´ario para descrever as fun¸c˜oes.

Nesta tese s˜ao apresentados novos algoritmos para construir FHPs e FHPMs que,

al´em de serem melhores do que os principais algoritmos pr´aticos dispon´ıveis na literatura,

tamb´em s˜ao bem compreendidos teoricamente. Consequentemente, um importante passo

foi dado para preencher a lacuna existente entre teoria e pr´atica nos m´etodos de hashing

perfeito. N´os tamb´em mostramos que os novos algoritmos viabilizaram a utiliza¸c˜ao de

FHPMs em aplica¸c˜oes nas quais tais fun¸c˜oes n˜ao eram consideradas uma boa op¸c˜ao no

passado. Por ﬁm, os resultados desta tese permitem a constru¸c˜ao de FHPMs que escalam

facilmente para conjuntos contendo bilh˜oes de elementos.

iii

Deﬁni¸c˜oes e Nota¸c˜ao

Nesta se¸c˜ao apresentamos algumas deﬁni¸c˜oes e a nota¸c˜ao usada ao longo deste trabalho.

O objetivo ´e estabelecer um vocabul´ario comum que ser´a usado por toda a tese.

Deﬁni¸c˜ao 1 Uma chave ´e constru´ıda a partir de s´ımbolos de um alfabeto Σ, o qual ´e

ﬁnito, ordenado e de tamanho |Σ|.

Deﬁni¸c˜ao 2 Seja Φ o comprimento m´aximo de uma chave. Ent˜ao, L = Φ log |Σ| ´e o

comprimento m´aximo em bits

. Assim, deﬁnimos um universo de chaves U de tamanho

u = 2

Por toda esta tese consideramos que L = O(1) e que log u cabe em um n´umero cons-

tante de palavras de um computador. Consequentemente, todos os algoritmos que iremos

considerar s˜ao analisados para o modelo computacional Word RAM [41]. Neste modelo,

um elemento do universo U cabe dentro de uma palavra do computador, e as opera¸c˜oes

aritm´eticas e os acessos `a mem´oria tˆem custo unit´ario.

Deﬁni¸c˜ao 3 Seja S um subconjunto de U contendo n chaves, onde n ≪ u.

Deﬁni¸c˜ao 4 Seja h : U → M uma fun¸c˜ao hash que mapeia as chaves de U para um dado

intervalo de inteiros M = [0, m − 1] = {0, 1, . . . , m − 1} (isto ´e, dada uma chave x ∈ U, a

fun¸c˜ao hash computa um inteiro em [0, m − 1]).

Deﬁni¸c˜ao 5 Dado duas chaves x, y ∈ U, onde x = y, e uma fun¸c˜ao hash h : U → M, uma

colis˜ao ocorre quando h(x) = h(y).

Deﬁni¸c˜ao 6 Uma fun¸c˜ao hash perfeita phf : S → M ´e uma fun¸c˜ao injetora, onde S ⊆ U

(isto ´e, para todos os pares s

, s

∈ S nos quais s

= s

, temos que phf (s

) = phf (s

onde m ≥ n). Por ser uma fun¸c˜ao injetora, phf mapeia cada chave de S em um inteiro

´unico no intervalo M. Como n˜ao ocorrem colis˜oes, se phf for utilizada para indexar uma

tabela hash de tamanho m, com n registros identiﬁcados pelas n chaves de S, ent˜ao, cada

registro pode ser recuperado com um ´unico acesso `a tabela.

Deﬁni¸c˜ao 7 Uma fun¸c˜ao hash perfeita m´ınima mphf : S → M ´e uma fun¸c˜ao bijetora,

onde S ⊆ U (isto ´e, cada chave de S ´e mapeada para um ´unico inteiro em M e m = n).

Por todo este trabalho iremos denotar log

x como log x.

Deﬁni¸c˜ao 8 Uma fun¸c˜ao hash perfeita ´e de ordem preservada se, para qualquer par de

chaves s

e s

∈ S, temos phf (s

) < phf (s

) sempre que i < j.

Limite Inferior de Espa¸co para se Representar FHPs e

FHPMs

A m´etrica mais importante relacionada com FHPs e FHPMs ´e a quantidade de espa¸co

necess´ario para descrever tais fun¸c˜oes. O limite inferior ter´orico para descrever uma FHP

foi primeiramente estudado em [57]. Fredman e Koml´os [40] provaram um limite inferior

para FHPMs. Uma prova mais simples deste limite foi mais tarde obtido em [68]. Os

dois teoremas seguintes apresentam o limite inferior te´orico para descrever uma FHP e

uma FHPM, respectivamente. Aqui n´os utilizamos a aproxima¸c˜ao de Stirling e, portanto,

obtivemos um resultado mais preciso, que est´a distante do valor exato por uma constante

aditiva, uma vez que a aproxima¸c˜ao de Stirling est´a distante do valor exato por um fator

constante. Por simplicidade de exposi¸c˜ao, consideramos nesta tese o caso em que log u ≪ n,

o qual nos permite ignorar nos dois teoremas abaixo termos que dependam de u.

Teorema 1 Toda fun¸c˜ao hash perfeita phf : S → M, onde |S| = n e |M| = m, requer

pelo menos (1 + (m/n − 1 + 1/2n) ln(1 − n/m)) n log e bits para ser armazenada.

Prova. A probabilidade de mapear aleatoriamente n elementos dentro de um intervalo

de tamanho m sem colis˜oes (isto ´e, a probabilidade de se obter uma FHP) ´e:

(n, m) =

(m − 1)(m − 2) . . . (m − n + 1)

(m − n)!

Pela seguinte aproxima¸c˜ao de Stirling n! ≈ n

−n

√

2πn obtemos:

(n, m) ≈ m

(m−n)

· (m −n)

−(m−n)

· e

−n



m − n

Portanto, pelo menos 1/ Pr

(n, m) fun¸c˜oes hash s˜ao necess´arias para se obter uma FHP.

Assim, pelo menos log(1/P r

(n, m)) = (1 + (m/n −1 + 1/2n) ln(1 −n/m)) n log e bits s˜ao

necess´arios para codiﬁcar esse conjunto de fun¸c˜oes.

Teorema 2 Toda fun¸c˜ao hash perfeita m´ınima mphf : S → M, onde |S| = n e |M| =

m = n, requer pelo menos n log e − O(log n) bits para ser armazenada.

Prova. A probabilidade de encontrar uma FHPM (onde n = m) ´e:

mph

(n, n) =

√

2πn

= e

−n

√

2πn.

Na equa¸c˜ao acima tamb´em utilizamos a aproxima¸c˜ao de Stirling mencionada anteriormente.

Consequentemente, o n´umero esperado de bits necess´ario para descrever essas raras FHPMs

´e no m´ınimo log(1/ Pr

mph

(n, n)) = n log e − O(log n).

Hashing Uniforme versus Hashing Universal

Todos os algoritmos de hashing perfeito precisam usar fun¸c˜oes hash selecionadas aleato-

riamente com probabilidade uniforme de uma familia H de fun¸c˜oes hash, as quais s˜ao

utilizadas durante a constru¸c˜ao de FHPs e FHPMs. Existem dois tipos de familias de

fun¸c˜oes hash que s˜ao utilizadas nas an´alises cl´assicas de esquemas de hashing: (i) fun¸c˜oes

hash uniformes e (ii) fun¸c˜oes hash universais. Nesta se¸c˜ao deﬁnimos essas duas familias de

fun¸c˜oes hash.

Familia de Fun¸c˜oes Hash Uniformes

A an´alise cl´assica de esquemas de hashing ´e frequentemente calcada na suposi¸c˜ao de que

as fun¸c˜oes hash utilizadas s˜ao escolhidas aleatoriamente e com probabilidade uniforme de

uma familia de fun¸c˜oes hash uniformes, a qual ´e deﬁnida como segue.

Deﬁni¸c˜ao 9 Seja H a familia de todas as m

fun¸c˜oes hash que mapeiam chaves do universo

U para o intervalo [0, m−1]. Uma fun¸c˜ao hash uniforme ´e uma fun¸c˜ao que ´e escolhida com

probabilidade uniforme da familia H e que produz valores independentes e uniformemente

distribu´ıdos dentro do intervalo considerado.

O problema com as fun¸c˜oes hash uniformes ´e o espa¸co necess´ario para descrever uma

´unica fun¸c˜ao, o qual ´e Ω(u log m) bits. Esse requisito de espa¸co normalmente excede a

capacidade de armazenamento dispon´ıvel e ´e frequentemente desconsiderado durante a

an´alise dos algoritmos pr´aticos de hashing perfeito existentes na literatura.

Lema 1 [20] Seja H uma familia de fun¸c˜oes hash e seja h : U → M uma fun¸c˜ao hash

selecionada de H com probabilidade

|H|

. Seja C

(x, y) = 1 se x ∈ U e y ∈ U colidem na

utiliza¸c˜ao da fun¸c˜ao hash h, e 0 caso contr´ario, onde x = y . A probabilidade de colis˜ao

entre duas chaves diferentes x, y ∈ U corresponde ao valor esperado de C

(x, y) e ´e dada

por:

E[C

(x, y)] ≥

−

Prova. Seja C

(x, U) o n´umero total de chaves de U que colidem com uma dada chave

x ∈ U na utiliza¸c˜ao da fun¸c˜ao hash h. Logo, C

(x, U) =



y∈U,y=x

(x, y). Seja C

(U, U)

o n´umero total de colis˜oes para toda chave x ∈ U na utiliza¸c˜ao da fun¸c˜ao hash h. Logo,

(U, U) =



x∈U

(x, U). Seja H uma familia ou cole¸c˜ao de fun¸c˜oes hash uniformes.

Assim, C

(U, U) =



h∈H

(U, U) denota o n´umero total de colis˜oes para toda chave

x ∈ U e para todas as fun¸c˜oes hash de H. Vamos imaginar que M = [0, m−1] ´e um intervalo

de ´ındices de uma tabela hash com m entradas e que os valores de M s˜ao computados por

uma fun¸c˜ao hash h : U → M selecionada com probabilidade

|H|

da familia H de fun¸c˜oes

hash uniformes. Depois de mapear todas as chaves para o intervalo M, se uma entrada

i ∈ M tem trˆes chaves {k

, k

}, ent˜ao k

colide com cada uma das chaves de {k

, k

colide com cada uma das chaves de {k

, k

}, e k

colide com cada uma das chaves de

, k

}, e, portanto, 6 colis˜oes ocorrem na entrada i. Considerando uma fun¸c˜ao hash

h ∈ H, no pior caso, quando todas as chaves de U s˜ao mapeadas na mesma entrada i, o

n´umero de colis˜oes corresponde ao n´umero de pares ordenados que podem ser formados

a partir das chaves do universo U de tamanho u, o qual ´e dado por C

(U, U) = u

− u.

Consequentemente, C

(U, U) = |H|(u

− u). Como existem m entradas, ent˜ao, o n´umero

esperado de colis˜oes para todas as fun¸c˜oes hash de H ´e:

E[C

(U, U)] = u

|H|



−



Assim, pelo princ´ıpio da casa dos pombos

, existem x, y ∈ U e h ∈ H tal que

E[C

(x, y)] =

−

≥

−

Familia de Fun¸c˜oes Hash Universais

Como mencionado na se¸c˜ao anterior, a quantidade de espa¸co necess´ario para se representar

uma fun¸c˜ao hash uniforme ´e proibitiva na pr´atica. Felizmente, na maioria das situa¸c˜oes,

O princ´ıpio da casa dos pombos diz que, dado dois n´umeros naturais n e m com n > m, se n pombos

s˜ao colocados dentro de m casas de pombos, ent˜ao, pelo menos uma casa de pombo conter´a mais do que

um pombo.

vii

fun¸c˜oes hash heur´ısticas se comportam de forma similar ao comportamento esperado de

fun¸c˜oes hash uniformes, mas existem casos para os quais garantias probabil´ısticas rigorosas

s˜ao necess´arias [18]. Por exemplo, v´arios esquemas de hashing adaptativos presumem

que uma fun¸c˜ao hash com certas propriedades pr´e-estabelecidas pode ser encontrada com

custo esperado de tempo O(1). Isso acontece se a fun¸c˜ao ´e selecionada aleatoriamente

com probabilidade uniforme de uma familia de fun¸c˜oes hash uniformes at´e que uma fun¸c˜ao

adequada seja encontrada, mas n˜ao necessariamente se a sele¸c˜ao for limitada a um conjunto

menor de fun¸c˜oes. Essa situa¸c˜ao conduziu Carter e Wegman [20] ao conceito de hashing

universal.

Deﬁni¸c˜ao 10 Uma familia H de fun¸c˜oes hash ´e deﬁnida como fracamente universal ou

apenas universal se, para qualquer par de elementos distintos x

, x

∈ U e uma fun¸c˜ao h

escolhida com probabilidade uniforme de H, temos que

Pr(h(x

) = h(x

)) ≤

Deﬁni¸c˜ao 11 Uma familia H de fun¸c˜oes hash ´e deﬁnida como fortemente universal ou

independente aos pares se, para qualquer par de elementos distintos x

, x

∈ U e dois

valores arbitr´arios y

, y

∈ M, temos que

Pr(h(x

) = y

e h(x

) = y

) =

Em muitas situa¸c˜oes, a an´alise de v´arios esquemas de hashing pode ser completada sob

a suposi¸c˜ao mais fraca de que h ´e escolhida com probabilidade uniforme de uma familia

de fun¸c˜oes hash universais, ao inv´es da suposi¸c˜ao de que h ´e escolhida com probabilidade

uniforme de uma familia de fun¸c˜oes hash uniformes. Em outras palavras, aleatoriedade

limitada ´e suﬁciente na pr´atica [70]. Por exemplo, quando estamos trabalhando com um

universo de chaves muito maior do que o intervalo M = [0, m − 1] da fun¸c˜ao hash, que

´e o caso para a maioria das aplica¸c˜oes de m´etodos de hashing, fun¸c˜oes hash universais se

comportam t˜ao bem quanto as fun¸c˜oes hash uniformes. Isso pode ser visto ao compararmos

o resultado do Lema 1 com a probabilidade de colis˜oes para fun¸c˜oes hash universais, que

´e dada na Deﬁni¸c˜ao 10.

E importante observar que existem casos para os quais garantias

probabil´ısticas rigorosas s˜ao necess´arias [18, 2]. Para ilustrar esse fato, iremos utilizar os

trˆes cen´arios seguintes, os quais foram bem reportados em [2]:

1. Considere que um conjunto de chaves S ⊆ U de tamanho n seja mapeado em uma

tabela hash com m entradas. A quest˜ao ´e: quantas entradas m s˜ao necess´arias para

viii

que nenhuma colis˜ao ocorra? Ao utilizarmos uma fun¸c˜ao hash universal com uma

tabela de tamanho m = O(n

), a probabilidade de que nenhuma colis˜ao ocorra ´e

maior que 1/2. Por outro lado, ao utilizarmos uma fun¸c˜ao hash uniforme, ´e bem

sabido que uma tabela de tamanho m = o(n

) n˜ao ´e suﬁciente para evitar colis˜oes,

como exempliﬁcado pelo paradoxo do anivers´ario

. Consequentemente, nada ´e per-

dido quando se utiliza uma fun¸c˜ao hash universal nesse cen´ario.

2. Considere que um conjunto de chaves S ⊆ U seja mapeado em uma tabela hash com

m = n entradas. A quest˜ao ´e: qual deveria ser o tamanho de S para cobrir todas as

entradas da tabela (isto ´e, nenhuma entrada ﬁca vazia)? Ao utilizarmos uma fun¸c˜ao

hash universal, se o tamanho de S for 2n

, ent˜ao, todas as entradas s˜ao cobertas

com probabilidade maior do que 1/2. Por outro lado, ao utilizarmos uma fun¸c˜ao

hash uniforme, ´e bem sabido que seria necess´ario um conjunto de chaves de tamanho

θ(n log n) para cobrir todas as entradas, com alta probabilidade

. Consequentemente,

ao utilizarmos uma fun¸c˜ao hash uniforme nesse cen´ario, um ganho polinomial ´e obtido

ao sairmos de O(n

) para θ(n log n) entradas.

3. Considere que o conjunto de chaves S de tamanho n seja mapeado em uma tabela

hash com m = n entradas. A quest˜ao ´e: qual seria a entrada com o maior n´umero de

chaves? Ao utilizarmos uma fun¸c˜ao hash universal, a entrada com o maior n´umero

de chaves conter´a O(n

1/2

) chaves. Ao utilizarmos uma fun¸c˜ao hash uniforme, ´e bem

sabido que a entrada com o maior n´umero de chaves conter´a θ(log n/ log log n) chaves.

Consequentemente, ao utilizarmos uma fun¸c˜ao hash uniforme nesse cen´ario, um ganho

exponencial ´e obtido ao sairmos de O(n

1/2

) para θ(log n/ log log n).

Grafos Randˆomicos

Nesta se¸c˜ao discutimos alguns fatos sobre grafos randˆomicos que s˜ao importantes para a

an´alise dos nossos algoritmos. Um grafo randˆomico ´e um grafo gerado por algum procedi-

mento aleat´orio. Existem muitas formas n˜ao equivalentes de se deﬁnir grafos randˆomicos

e agora iremos apresentar dois modelos fortemente relacionados. O estudo dos grafos

O paradoxo do anivers´ario diz que, se 23 ou mais pessoas forem aleatoriamente reunidas, a probabi-

lidade que pelo menos duas pessoas fa¸cam anivers´ario no mesmo dia ´e maior do que 50%, como pode ser

visto em Feller [36, P´agina 33].

Por toda esta tese o termo “com alta probabilidade” ´e utilizado para signiﬁcar com probabilidade

1 − n

−δ

para δ > 0.

randˆomicos se iniciou com o trabalho cl´assico de Erd˝os e R´enyi [33, 34, 35] (veja [8, 49]

para um tratamento moderno do assunto).

Deﬁni¸c˜ao 12 Seja G = (V, E) um grafo randˆomico obtido atrav´es do modelo uniforme

G(m, n), que ´e o modelo em que todos os



(

)



grafos com m v´ertices e n arestas s˜ao

equiprov´aveis. Nesse modelo, o grafo G inicia com um n´umero ﬁxo de v´ertices, denotado

por |V | = m, e |E| = n arestas s˜ao escolhidas aleatoriamente do conjunto de todas as





arestas poss´ıveis sem permitir repeti¸c˜ao. Um modelo similar, denotado por G(m, p), onde

0 ≤ p ≤ 1, ´e obtido quando consideramos o mesmo conjunto de v´ertices e selecionamos

cada aresta com probabilidade p, mas independentemente das outras. Portanto, neste caso,

repeti¸c˜oes s˜ao permitidas.

Como apresentado em [48], frequentemente ´e ´util considerar que o grafo randˆomico

evolui no tempo por meio de um processo estoc´astico, iniciando com um conjunto de

v´ertices e sem nenhuma aresta. Em seguida, arestas s˜ao inseridas at´e que o grafo completo

seja obtido. O processo de se adicionar cada aresta independentemente das outras em algum

instante de tempo aleat´orio, o qual pode, por exemplo, estar uniformemente distribu´ıdo

no intervalo (0, 1), resultar´a em um grafo randˆomico do tipo G(m, p) em um certo instante

de tempo p ∈ (0, 1) e um grafo randˆomico do tipo G(m, n) no instante de tempo em que a

n-´esima aresta aparece.

Nosso melhor resultado constr´oi uma familia F de FHPs e FHPMs baseado em hiper-

grafos r-partidos sem ciclos, deﬁnidos como segue.

Deﬁni¸c˜ao 13 Um hipergrafo ´e a generaliza¸c˜ao de um grafo n˜ao direcionado onde cada

aresta conecta r ≥ 2 v´ertices.

Deﬁni¸c˜ao 14 Seja G

= (V, E) um hipergrafo randˆomico, r-partido e r-uniforme para

r ≥ 2, onde V ´e a uni˜ao das r partes disjuntas V

, V

, . . . , V

r−1

, |V

| = ρ, |V | = m = rρ,

e |E| = n. As arestas s˜ao inseridas em G

, uma de cada vez, sendo cada uma selecionada

aleatoriamente dentre todas as ρ

arestas poss´ıveis, permitindo repeti¸c˜ao.

Deﬁni¸c˜ao 15 Um hipergrafo ´e ac´ıclico se e somente se alguma sequˆencia de remo¸c˜oes

repetidas de arestas que incidem sobre v´ertices de grau 1 tem como resultado um hipergrafo

sem nenhuma aresta [26, P´agina 103].

Trabalhos Relacionados

Nesta se¸c˜ao revisamos alguns dos resultados te´oricos, pr´aticos e heur´ısticos mais impor-

tantes da literatura de hashing perfeito. Czech, Havas e Majewski [26] ﬁzeram um levan-

tamento mais completo at´e o ano de 1997.

Como mencionado anteriormente, existe uma lacuna entre teoria e pr´atica nos m´etodos

de hashing perfeito. Por um lado, existem bons resultados te´oricos sem comprova¸c˜ao

experimental da sua aplicabilidade para grandes conjuntos de chaves. N´os argumentaremos

abaixo que esses m´etodos n˜ao podem ser utilizados na pr´atica. Por outro lado, existem duas

categorias de algoritmos pr´aticos: (i) os algoritmos que tˆem as complexidades de tempo e

espa¸co analisadas sob a suposi¸c˜ao de que fun¸c˜oes hash uniformes podem ser utilizadas sem

nenhum custo adicional de espa¸co, a qual ´e uma suposi¸c˜ao n˜ao real´ıstica porque cada uma

dessas fun¸c˜oes requer pelo menos u log m bits para ser armazenada, e (ii) os algoritmos

heur´ısticos que apresentam apenas evidˆencias emp´ıricas sobre os seus comportamentos.

O objetivo desta se¸c˜ao ´e discutir a lacuna existente entre estes trˆes tipos de algoritmos

dispon´ıveis na literatura.

Resultados Te´oricos

Nesta se¸c˜ao revisamos alguns dos resultados te´oricos mais importantes da literatura

de hashing perfeito m´ınimo, os quais n˜ao assumem que fun¸c˜oes hash uniformes est˜ao

dispon´ıveis para serem utilizadas sem nenhum custo adicional de espa¸co. Fredman e

Koml´os [40] provaram que pelo menos n log e + log log u − O(log n) bits s˜ao necess´arios

para representar uma FHPM (considerando o pior caso e todos os conjuntos de chaves de

tamanho n), dado que u ≥ n

para algum α > 2. Mehlhorn [57] mostrou que o limite

obtido por Fredman e Koml´os era quase justo, exibindo para isso um algoritmo que constr´oi

uma FHPM que pode ser representada em no m´aximo n log e + log log u + O(log n) bits.

No entanto, seu algoritmo est´a muito distante da pr´atica, uma vez que tanto a gera¸c˜ao

quanto a avalia¸c˜ao das fun¸c˜oes resultantes s˜ao exponenciais em n (isto ´e, n

θ(ne

u log u)

Schmidt e Siegel [70] propuseram o primeiro algoritmo para construir uma FHPM com

tempo de avalia¸c˜ao constante e tamanho da descri¸c˜ao igual a O(n+log log u) bits. Do ponto

de vista pr´atico, o algoritmo de Schmidt e Siegel n˜ao ´e atrativo. O esquema ´e complicado

para se implementar e a constante escondida na ordem de complexidade assint´otica de

espa¸co ´e grande: para um conjunto de n chaves, pelo menos 29n bits s˜ao utilizados, o que

signiﬁca uma utiliza¸c˜ao de espa¸co na pr´atica similar aos melhores esquemas que geram

fun¸c˜oes que s˜ao armazenadas em O(n log n) bits. Embora pare¸ca que os autores em [70]

queriam descrever o algoritmo deles da forma mais clara poss´ııvel, sem tentar otimizar a

constante, seria dif´ıcil melhorar a utiliza¸c˜ao de espa¸co signiﬁcativamente.

Mais recentemente, Hagerup e Tholey [43] apresentaram o melhor resultado te´orico

que conhecemos. A FHPM obtida pode ser avaliada em tempo O(1) e armazenada

em n log e + log log u + O(n(log log n)

/ log n + log log log u) bits. O tempo de gera¸c˜ao

´e O(n+ log log u) utilizando O(n) palavras de um computador. Apesar da sua importˆancia

te´orica, o algoritmo de Hagerup e Tholey tamb´em n˜ao ´e pr´atico, uma vez que ele enfatiza

somente complexidade assint´otica de espa¸co. (Ele tamb´em ´e muito complicado de se im-

plementar, mas n˜ao iremos discutir isso.) Para n < 2

150

o esquema n˜ao ´e bem deﬁnido,

pois conta com o particionamento do conjunto de chaves em subconjuntos de tamanho

ˆn ≤ log n/(21 log log n). Se corrigirmos isto permitindo subconjuntos de tamanho m´ınimo

1, ent˜ao, subconjuntos de tamanho um ser˜ao utilizados para n < 2

300

, o que conduziria a

uma utiliza¸c˜ao de espa¸co de pelo menos (3 log log n+log 7) n bits. Para um conjunto de um

bilh˜ao de chaves, isso seria mais do que 17 bits por elemento. J´a que 2

300

excede o n´umero

de ´atomos conhecidos no universo, ´e seguro conluir que a FHPM de Hagerup e Tholey n˜ao

´e eﬁciente em espa¸co em situa¸c˜oes pr´aticas. Embora acreditamos que o algoritmo deles

foi otimizado levando em cosidera¸c˜ao a simplicidade de exposi¸c˜ao, ao inv´es das constantes

envolvidas na ordem de complexidade de espa¸co, parece ser dif´ıcil reduzir a utiliza¸c˜ao de

espa¸co signiﬁcativamente na abordagem deles.

Resultados Pr´aticos

Nesta se¸c˜ao descrevemos alguns dos principais resultados “pr´aticos” que serviram de fonte

de inspira¸c˜ao para este trabalho. Eles s˜ao caracterizados pela simplicidade e por possuirem

fatores constantes, aparentemente baixos, na complexidade de espa¸co para se descrever as

fun¸c˜oes resultantes. Em geral, eles s˜ao analisados sob a suposi¸c˜ao n˜ao real´ıstica de que

fun¸c˜oes hash uniformes est˜ao dispon´ıveis para serem utilizadas sem nenhum custo adicional

de espa¸co.

O algoritmo proposto por Czech, Havas e Majewski [25] fazem a suposi¸c˜ao mencionada

anteriormente para construir FHPMs de ordem preservada (mas, na pr´atica, fun¸c˜oes hash

universais s˜ao utilizadas). O m´etodo usa duas fun¸c˜oes hash uniformes h

: S → [0, cn − 1]

e h

: S → [0, cn − 1] para gerar FHPMs na seguinte forma: mphf (x) = (g[h

(x)] +

g[h

(x)] mod n, onde c > 2. As FHPMs resultantes podem ser avaliadas em tempo O(1) e

armazenadas em O(n log n) bits (que ´e ´otimo para uma FHPM de ordem preservada). A

FHPM resultante ´e gerada com complexidade esperada de tempo O(n).

xii

Botelho, Kohayakawa e Ziviani [12] melhoraram as requisi¸c˜oes de espa¸co para se ar-

mazenar as FHPMs resultantes sob a pena de gerar fun¸c˜oes da mesma forma, mas que

n˜ao s˜ao de ordem preservada. O algoritmo deles tamb´em ´e linear em n, mas executa mais

r´apido do que os algoritmos de Czech et al. [25] e as FHPMs resultantes necessitam da

metade do espa¸co para serem armazenadas, pois c ∈ [0.93, 1.15]. No entanto, as FHPMs

resultantes ainda requerem O(n log n) bits de espa¸co de armazenamento. Foi mostrado

experimentalmente em [12] que o algoritmo funciona bem em situa¸c˜oes pr´aticas.

Majewski et al. [55] propuseram um algoritmo para gerar uma familia de FHPMs

baseado em hipergrafos r-uniformes (isto ´e, com arestas de tamanho r). O algoritmo ´e

uma generaliza¸c˜ao do apresentado em [25]. As fun¸c˜oes resultantes podem ser avaliadas em

tempo O(1) e armazenadas em O(n log n) bits. Embora as fun¸c˜oes resultantes s˜ao quase

t˜ao compactas quanto as geradas no trabalho apresentado em [12], elas ainda requerem

O(n log n) bits de espa¸co de armazenamento. Botelho, Pagh e Ziviani [14] projetaram uma

familia de algoritmos que melhora o requisito de espa¸co, saindo de O(n log n) para O(n)

bits, sob a pena de gerar fun¸c˜oes que n˜ao s˜ao de ordem preservada.

J´a que a requisi¸c˜ao de espa¸co de armazenamento para fun¸c˜oes hash uniformes as tornam

inadequadas para implementa¸c˜ao, ´e preciso estabelecer uma conﬁgura¸c˜ao mais real´ıstica. O

primeiro passo nessa dire¸c˜ao foi dado por Pagh [61]. Ele propˆos uma familia de algoritmos

randˆomicos para construir FHPMs da forma mphf (x ) = (f(x) + d[g(x)]) mod n, onde f

e g s˜ao selecionadas de uma familia de fun¸c˜oes hash universais (veja Deﬁni¸c˜ao 10) e d

´e um conjunto de valores de deslocamentos utilizados para resolver as colis˜oes causadas

pela fun¸c˜ao f. Pagh identiﬁcou um conjunto de condi¸c˜oes relacionadas com f e g, e

mostrou que se estas condi¸c˜oes forem satisfeitas, ent˜ao, uma FHPM pode ser computada

com complexidade de tempo esperada igual a O(n) e pode ser armazenada em (2+ǫ)n log n

bits, que ´e sub-´otimo.

Dietzfelbinger e Hagerup [29] melhoraram o resultado apresentado em [61], reduzindo

a utiliza¸c˜ao de espa¸co para (1 + ǫ)n log n bits, mas, na abordagem deles, f e g precisam ser

escolhidas de uma classe de fun¸c˜oes hash que atenda a alguns outros requisitos. Woelfel [75]

mostrou como diminuir a utiliza¸c˜ao de espa¸co um pouco mais, indo para O(n log log n) bits

assint´oticamente, ainda com um algoritmo muito simples. No entanto, n˜ao existe nenhuma

evidˆencia emp´ırica sobre o valor pr´atico desse esquema.

Galli, Seybold e Simon [42] propuseram um algoritmo para gerar FHPMs similar aos

apresentados nos trabalhos [61, 29]. No entanto, nas FHPMs deles, as duas fun¸c˜oes f e g s˜ao

deﬁnidas como f(x) = h

(x) mod n e g(x) = ⌊h

(x)/n⌋, onde h

(k) = (ck mod p) mod n

xiii

1 ≤ c ≤ p − 1 e p ´e um n´umero primo maior que u. As FHPMs s˜ao geradas em tempo

liner e armazenadas em O(n log n) bits. A principal vantagem dessa abordagem ´e que ela

pode ser facilmente adaptada para conjuntos dinˆamicos, mas somente para FHPs.

Prabhakar e Bonomi [66] projetaram FHPs que foram utilizadas para armazenar tabelas

de roteamento em roteadores. Eles mostraram que o requisito de espa¸co de armazenamento

para as fun¸c˜oes resultantes tende a 2en bits a medida que n tende ao inﬁnito. Nas suas

simula¸c˜oes, as fun¸c˜oes resultantes necessitavam de 8.6n bits para serem armazenadas. A

principal vantagem desse esquema ´e que ele ´e simples o suﬁciente para ser implementado

em hardware.

Algoritmos randˆomicos do tipo Las Vegas

foram projetados em todos os trabalhos

anteriores e tamb´em neste trabalho de tese. Contrariamente, os trabalhos [4, 73] apresen-

tam algoritmos determin´ısticos para construir FHPs e FHPMs. As fun¸c˜oes resultantes re-

querem O(n log(n)+log(log(u))) bits de espa¸co de armazenamento e s˜ao avaliadas em tempo

O(log(n) + log(log(u))). Assim, as fun¸c˜oes resultantes n˜ao s˜ao avaliadas em tempo O(1) e

est˜ao distantes por um fator de O(log n) bits dos limites inferiores de espa¸co de armazena-

mento de FHPs e FHPMs, os quais s˜ao apresentados nos Teoremas 1 e 2, respectivamente.

As complexidades de caso m´edio e de pior caso dos algoritmos s˜ao O(n log(n) log(log(u)))

e O(n

log(n) log(log(u))), respectivamente.

Heur´ısticas

Nesta se¸c˜ao consideramos trabalhos projetados para aplica¸c˜oes espec´ıﬁcas e, em geral,

apenas evidˆencias experimentais sobre o comportamento dos algoritmos s˜ao apresentadas.

Fox et al. [39] criaram o primeiro esquema com boa performance de caso m´edio para

grandes conjuntos de chaves, isto ´e, n ≈ 10

. Eles projetaram dois algoritmos. O primeiro

gera uma FHPM que pode ser avaliada em tempo O(1) e armazenada em O(n log n) bits. O

segundo usa hashing quadr´atico e adiciona desvios realizados com base em uma tabela de

valores bin´arios para obter uma FHPM que pode ser avaliada em tempo O(1) e armazenada

em c(n+1/ log n) bits. Eles argumentaram que o valor de c seria tipicamente menor do que

5, no entanto, a partir da experimenta¸c˜ao apresentada, ﬁca claro que o valor de c cresce

com n e eles n˜ao discutem isso. Eles alegaram que os seus algoritmos tinham complexidade

linear de tempo de execu¸c˜ao, mas, foi mostrado em [26, Section 6.7] que os algoritmos s˜ao

exponenciais no pior caso, embora o pior caso tenha uma pequena probabilidade de ocorrer.

Um algoritmo randˆomico ´e chamado de Las Vegas se ele sempre produz respostas corretas, mas com

uma pequena probabilidade de demorar muito para executar.

xiv

Fox, Chen e Heath [38] melhoraram o resultado acima para obter uma fun¸c˜ao que

pode ser armazenada em cn bits. O m´etodo usa quatro fun¸c˜oes hash uniformes h

: S →

[0, n−1], h

: [0, p

−1] → [0, p

−1], h

: [p

, n−1] → [p

, b−1] e h

: S×{0, 1} → [0, n−1]

para construir uma FHPM que tem a seguinte forma:

mphf (x) = (h

(x, d) + g(i(x))) mod n

i(x) =







◦ h

(x) se h

(x) < p

◦ h

(x) caso contr´ario.

onde p

= 0.6n e p

= 0.3n foram determinados experimentalmente, e b = ⌈cn/(log n+1)⌉.

Novamente o valor de c foi estabelecido somente para valores pequenos de n. Tamb´em neste

caso, o valor de c poderia muito bem crescer com o valor de n. Ent˜ao, a limita¸c˜ao dos

trˆes algoritmos ´e que n˜ao existe nenhuma garantia de que o n´umero de bits por chave para

armazenar a fun¸c˜ao resultante permane¸ca constante a medida que o valor de n aumente.

O trabalho de Lefebvre e Hoppe [54] tem o mesmo problema de n˜ao garantir que o

n´umero de bits por chave para se armazenar as fun¸c˜oes resultantes permane¸ca constante.

Eles projetaram um m´etodo para construir FHPs utilizadas especiﬁcamente para represen-

tar dados espaciais esparsos. As fun¸c˜oes resultantes requerem mais de 3 bits por chave para

serem armazenadas. Seguindo a mesma tendˆencia, Chang, Lin e Chou [21, 22] projetaram

FHPMs feitas sob medida para minerar regras de associa¸c˜ao e padr˜oes transversais em

t´ecnicas de minera¸c˜ao de dados.

Panorama T´ecnico deste Trabalho

Nosso objetivo prim´ario foi o de projetar algoritmos de hashing perfeito que fossem bem

fundamentados teoricamente e que pudessem ser eﬁcientemente utilizados na pr´atica. Para

isso, investigamos maneiras de preencher a lacuna existente entre teoria e pr´atica nos

algoritmos de hashing perfeito dispon´ıveis na literatura.

Neste trabalho utilizamos uma abordagem de dois passos para atingir nosso objetivo

prim´ario. No primeiro passo, particionamos o conjunto de chaves de entrada em pequenos

subconjuntos de chaves, chamados de buckets de agora em diante. Esse passo ´e equivalente

ao processo de gerar runs em um mergesort externo de m´ultiplos caminhos, o qual foi

cuidadosamente projetado para funcionar com complexidade de tempo linear. No segundo

passo, geramos uma FHP ou uma FHPM para cada bucket.

A Figura 2 ilustra os dois passos do algoritmo: o passo de particionamento e o passo

de pesquisa. O passo de particionamento toma como entrada um conjunto de chaves S de

tamanho n e usa uma fun¸c˜ao hash h

para particionar S em N

buckets. O passo de pesquisa

gera uma FHPM (ou, equivalentemente, uma FHP) para cada bucket i, 0 ≤ i ≤ N

− 1, e

computa o arranjo oﬀset. A avalia¸c˜ao da FHPM resultante para uma dada chave x ´e:

MPHF (x) = MPHF

(x) + oﬀset[i]

onde i = h

(x) indica o bucket onde a chave x reside, MPHF

(x) ´e a posi¸c˜ao de x dentro

do bucket i, e oﬀset[i] fornece o n´umero total de entradas antes do bucket i na tabela hash.

...

Conjunto de Chaves S

0 1

Particionamento

0 1 2

Pesquisa

Buckets

MPHF

−1

− 1

MPHF

Tabela Hash

m−1

n−1

Figura 2: Os dois passos do algoritmo.

Se o tamanho do conjunto de chaves, que ´e denotado por n, couber na mem´oria interna

dispon´ıvel, ent˜ao, o primeiro passo do algoritmo n˜ao ´e necess´ario. Nessa situa¸c˜ao, fazemos

com que o tamanho do bucket seja igual ao tamanho da entrada, isto ´e, n, e geramos uma

FHP ou uma FHPM para esse ´unico bucket. Consequentemente, o algoritmo se torna um

algoritmo de mem´oria interna que acessa `a mem´oria de forma randˆomica e, por isso, foi

denominado RAM que ´e uma abrevia¸c˜ao para iternal random access memory algorithm.

Se o tamanho do conjunto de chaves for maior do que o tamanho da mem´oria interna

dispon´ıvel, ent˜ao, o primeiro passo ´e realizado para particionar o conjunto de entrada em

pequenos buckets e, portanto, o algoritmo se torna uma algoritmo de mem´oria externa

ciente de cache. O algoritmo foi chamado de EM, que ´e uma abrevia¸c˜ao para external

memory algorithm e ´e ciente de cache porque os buckets s˜ao pequenos o suﬁciente para

caberem na cache do processador. Dessa forma, o algoritmo EM acessa `a mem´oria de uma

forma menos randˆomica quando comparado ao algoritmo RAM.

N´os reﬁnamos e combinamos in´umeras t´ecnicas existentes para projetar e implementar

o algoritmo, como discutido a seguir.

xvi

1. Para gerar FHPs ou FHPMs para os buckets poder´ıamos escolher in´umeras alter-

nativas, enfatizando ou utiliza¸c˜ao de espa¸co, ou tempo de constru¸c˜ao, ou tempo de

avalia¸c˜ao. Podemos fazer funcionar qualquer um dos m´etodos que assumem que

fun¸c˜oes hash uniformes est˜ao dispon´ıveis para serem utilizadas sem custo adicional

de espa¸co. Para isso, basta utilizarmos a t´ecnica split-and-share apresentada em

[30], na qual quebramos o problema em pequenos buckets e simulamos fun¸c˜oes hash

uniformes para cada um dos buckets. No Cap´ıtulo 3, apresentamos um reﬁnamento

dessa id´eia que nos permite obter uma familia de fun¸c˜oes hash uniformes para cada

bucket com um custo adicional de espa¸co que ´e constante.

2. Utilizamos o algoritmo RAM para computar FHPs ou FHPMs para os pequenos

buckets por duas raz˜oes: (i) ele gera fun¸c˜oes de espa¸co quase ´otimo; e (ii) ´e mais

eﬁciente do que os principais algoritmos pr´aticos dispon´ıveis na literatura de hashing

perfeito, incluindo nosso resultado anterior apresentado em [12]. N´os pegamos como

ponto de partida um algoritmo para gerar FHPs implicitamente deﬁnido em [23], o

qual foi tamb´em sugerido de forma independente por Belazzougui [5]. A partir da´ı,

melhoramos a an´alise, reﬁnamos o algoritmo de gera¸c˜ao para que obtivesse sucesso

com alta probabilidade, o estendemos para tamb´em gerar FHPMs, e mostramos como

implementar tudo de uma maneira quase ´otima em termos de espa¸co. Caso o conjunto

de chaves cujo tamanho ´e n caiba em mem´oria interna, temos apenas um bucket de

tamanho n, caso contr´ario, v´arios buckets pequenos s˜ao manipulados pelo algoritmo.

O algoritmo RAM ´e apresentado no Cap´ıtulo 2.

3. Ordena¸c˜ao externa (veja, por exemplo, [74, 53]) foi usada para agrupar as chaves em

buckets quando o conjunto de chaves n˜ao cabe em mem´oria interna. Em seguida,

cada bucket ´e tratado separadamente. A perspectiva importante aqui foi o parti-

cionamento do problema em buckets pequenos, e isso tem tanto implica¸c˜oes te´oricas

quanto pr´aticas. Do ponto de vista te´orico, mostramos que, ao reﬁnarmos a t´ecnica

de split-and-share para simular fun¸c˜oes hash uniformes para os buckets pequenos, fo-

mos capazes de provar que o algoritmo EM funcionar´a com alta probabilidade para

qualquer conjunto de chaves, mesmo aqueles escolhidos por advers´arios. J´a do ponto

de vista pr´atico, uma caracter´ıstica importante disso ´e que podemos construir buck-

ets pequenos o suﬁciente para caberem no cache do processador, resultando em uma

acelera¸c˜ao signiﬁcativa no tempo de processamento por elemento em compara¸c˜ao

com outros m´etodos. Para gerar os runs da ordena¸c˜ao externa, usamos o algoritmo

xvii

radixsort [24], o qual realiza essa tarefa com complexidade linear de tempo.

Tabelas de deslocamentos (oﬀset) s˜ao utilizadas para colocar tudo junto em uma

´unica FHP ou FHPM. Isso tem sido feito em v´arios trabalhos te´oricos (veja, por

exemplo, [70, 43]). No Cap´ıtulo 4, mostramos como implementar isso com um baixo

custo de utiliza¸c˜ao de espa¸co na pr´atica e apresentamos o algoritmo EM.

4. O algoritmo EM tem um alto grau de paralelismo por ser baseado em um mergesort

externo de m´ultiplos caminhos. No Cap´ıtulo 5, exploramos esse fato para projetar

uma vers˜ao paralela do algoritmo EM.

5. As t´ecnicas projetadas em nosso trabalho anterior apresentado em [12], as quais

permitem a gera¸c˜ao de FHPMs com base em grafos randˆomicos contendo ciclos, foram

utilizadas para otimizar uma vers˜ao do algoritmo RAM apresentado no Cap´ıtulo 2.

Isso ´e apresentado no Cap´ıtulo 6.

Contribui¸c˜oes

A atratividade de se usar FHPs e FHPMs depende dos seguintes requisitos [43]:

1. A quantidade de tempo de CPU necess´ario para gerar as fun¸c˜oes.

2. Os requisitos de espa¸co para gerar as fun¸c˜oes.

3. A quantidade de tempo de CPU necess´ario pelas fun¸c˜oes durante a avalia¸c˜ao.

4. Os requisitos de espa¸co para se descrever as fun¸c˜oes resultantes.

Nenhum algoritmo conhecido at´e ent˜ao tem bom desempenho em todos os quatro re-

quisitos acima. Normalmente, a requisi¸c˜ao de espa¸co para gerar as fun¸c˜oes ´e ignorada.

Devido a isso, os algoritmos na literatura n˜ao s˜ao capazes de escalar para conjuntos de

chaves contendo bilh˜oes de elementos. Al´em disso, como mencionado anteriormente, existe

uma lacuna entre os algoritmos pr´aticos e te´oricos. Por um lado, os algoritmos pr´aticos

possuem a complexidade de espa¸co para descrever as fun¸c˜oes analisada sob a suposi¸c˜ao n˜ao

real´ıstica de que fun¸c˜oes hash uniformes est˜ao dispon´ıveis para serem utilizadas sem custo

adicional de espa¸co. Por outro lado, os algoritmos te´oricos s˜ao analisados sem nenhuma

suposi¸c˜ao n˜ao real´ıstica, mas eles enfatizam apenas complexidade assint´otica de espa¸co e

s˜ao muito complicados para implementar.

xviii

As principais contribui¸c˜oes desta tese s˜ao:

1. N´os apresentamos um algoritmo de hashing perfeito simples, pr´atico e altamente es-

cal´avel que leva em considera¸c˜ao os quatro requisitos mencionados no in´ıcio desta

se¸c˜ao. Caso o conjunto de chaves de entrada caiba na mem´oria principal, o algo-

ritmo se torna um algoritmo de mem´oria interna, o qual acessa `a mem´oria de forma

randˆomica e, como mencionado anteriormente, foi chamado de RAM (internal ran-

dom access memory algorithm); caso contr´ario, ele se torna um algoritmo de mem´oria

externa ciente de cache e, por isso, foi denominado EM (external memory algorithm).

Vers˜oes preliminares dos algoritmos RAM e EM foram apresentadas em [14] e [15],

respectivamente. Em seguida apresentamos mais detalhes sobre os dois algoritmos.

(a) O algoritmo RAM trabalha sobre hipergrafos randˆomicos, r-partidos e ac´ıclicos

obtidos com o aux´ılio de r fun¸c˜oes hash uniformes. A id´eia de basear a gera¸c˜ao

de FHPs ou FHPMs em hipergrafos radˆomicos e ac´ıclicos n˜ao ´e nova, veja, por

exemplo, [55], mas n´os procedemos diferentemente para alcan¸car fun¸c˜oes que

podem ser descritas com uma complexidade de espa¸co igual a O(1) bits por

chave, ao inv´es de O(log n) bits por chave, reduzindo a ordem de complexidade

de espa¸co para armazenar as fun¸c˜oes de O(n log n) para O(n) bits. O algoritmo

RAM ´e apresentado no Cap´ıtulo 2.

Agora comentamos sobre os quatro requisitos mencionados anteriormente:

i. O algoritmo RAM gera FHPs ou FHPMs com complexidade linear de

tempo. As FHPs s˜ao equivalentes `as sugeridas por Belazzougui [5], as quais

foram anteriormente sugeridas por Chazelle et al. em [23], mas de uma

forma mais geral.

ii. O algoritmo RAM requer O(n) palavras de computador para gerar FHPs

ou FHPMs. Esta ´e a raz˜ao que o torna mais apropriado para conjuntos de

chaves que podem ser tratados em mem´oria interna.

iii. O algoritmo RAM gera FHPs ou FHPMs que s˜ao avaliadas com custo O(1)

de tempo.

iv. O algoritmo RAM gera FHPs e FHPMs de espa¸co quase ´otimo. Os req-

uisitos de espa¸co para descrever as fun¸c˜oes resultantes depende da rela¸c˜ao

entre m e n. Para m = n, a utiliza¸c˜ao de espa¸co ´e aproximadamente 2.62n

bits. Para m = 1.23n, a utiliza¸c˜ao de espa¸co ´e aproximadamente 1.95n bits.

Em todos os casos, os valores est˜ao distantes, por um fator constante, dos

xix

limites inferiores te´oricos, os quais s˜ao 1.44n e 0.89n bits para FHPs e FH-

PMs, respectivamente. Esse ´e um resultado que n˜ao tinha sido alcan¸cado

pelos algoritmos pr´aticos existentes at´e ent˜ao, mas que tem sido procurado

a mais de vinte anos pela comunidade de hashing perfeito.

(b) O algoritmo EM usa in´umeras t´ecnicas da literatura para permitir a gera¸c˜ao de

FHPs ou FHPMs para conjuntos de chaves contendo bilh˜oes de elementos. Ele

aumentou uma ordem de magnitude no tamanho do maior conjunto de chaves

para o qual uma FHPM tinha sido gerada na literatura [12]. Esse resultado ´e

proveniente de uma combina¸c˜ao de um novo esquema de hashing perfeito que ´e

bem fundamentado teoricamente e simpliﬁca consideravelmente os m´etodos an-

teriores, e o fato que ele ´e projetado para fazer uma boa utiliza¸c˜ao da hierarquia

de mem´oria, j´a que ´e fundamentalmente uma t´ecnica de dividir para conquistar.

O algoritmo EM pode ser considerado como o primeiro passo visando preencher

a lacuna existente entre teoria e pr´atica nos m´etodos de hashing perfeito. Con-

sequentemente, o algoritmo EM ´e o primeiro algoritmo que pode ser usado na

pr´atica, tem complexidades de tempo e espa¸co cuidadosamente analisados sem

suposi¸c˜oes n˜ao real´ısticas, e escala para conjuntos com bilh˜oes de chaves.

A escalabilidade do algoritmo EM foi demonstrada por meio da gera¸c˜ao de uma

FHPM para um conjunto com 1, 024 bilh˜oes de URLs, as quais foram obtidas da

World Wi de Web e possuem comprimento m´edio igual a 64 bytes. A fun¸c˜ao foi

gerada em approximadamente 50 minutos, utilizando um computador pessoal

rodando o sistema operacional Linux na vers˜ao 2.6, com um processador de 1.86

GHz (core 2 duo) da Intel, 4 MB de cache L2 e 1 GB de mem´oria principal. O

algoritmo EM ´e apresentado no Cap´ıtulo 4.

Agora comentamos sobre os quatro requisitos mencionados anteriormente:

i. O algoritmo EM gera FHPs ou FHPMs com complexidade linear de tempo.

O passo que domina o tempo de execu¸c˜ao do algoritmo de gera¸c˜ao ´e a

ordena¸c˜ao de n ﬁngerprints de O(log n) bits.

ii. O algoritmo EM requer O(n

) palavras de computador para ter complexi-

dade linear de tempo, onde 0 < ǫ < 1. Isso acontece porque ele necessita

somente de um heap em mem´oria principal para realizar uma intercala¸c˜ao

de m´ultiplos caminhos dos arquivos armazenados no disco, e o tamanho do

heap ´e a rela¸c˜ao entre o tamanho do conjunto de chaves e a quantidade de

mem´oria interna dispon´ıvel, ambos em bytes. No nosso caso, como queremos

desempenhar a opera¸c˜ao de intercala¸c˜ao em uma ´unica passada sobre os

arquivos, necessitamos que ǫ = 0.5 (veja, por exemplo, [1, Teorema 3.1]).

Isso ´e uma das raz˜oes que capacita o algoritmo EM escalar para conjuntos

contendo bilh˜oes de elementos.

iii. O algoritmo EM gera FHPs ou FHPMs que s˜ao avaliadas com custo O(1)

de tempo.

iv. O algoritmo EM tamb´em gera FHPs e FHPMs de espa¸co quase ´otimo,

mas agora n´os n˜ao assumimos que fun¸c˜oes hash uniformes est˜ao dispon´ıveis

para serem utilizadas sem nenhum custo adicional de espa¸co. Para isso,

projetamos, no Cap´ıtulo 3, uma forma de simular fun¸c˜oes hash uniformes

que operam sobre os buckets pequenos com somente um fator constante de

espa¸co adicional. Isso nos permitiu usar o algoritmo RAM para construir as

FHPMs de cada bucket sem suposi¸c˜oes n˜ao real´ısticas. Da mesma forma que

para o algoritmo RAM, os requisitos de espa¸co para se descrever as fun¸c˜oes

resultantes tamb´em dependem da rela¸c˜ao entre m e n. Para m = n, a

utiliza¸c˜ao de espa¸co ´e de aproximadamente 3.3n bits. Para m = 1.23n,

a utiliza¸c˜ao de espa¸co ´e de aproximadamente 2.7n bits. Novamente, esses

valores est˜ao distantes por um fator constante dos limites inferiores te´oricos

relacionados com o espa¸co necess´ario para representar FHPs e FHPMs. Esse

tamb´em ´e um resultado que n˜ao foi alcan¸cado pelos algoritmos pr´aticos e

te´oricos dispon´ıveis at´e ent˜ao na literatura de hashing perfeito, exceto para

valores de n assintoticamente grandes.

2. N´os fornecemos uma implementa¸c˜ao paralela e altamente escal´avel do algoritmo EM,

a qual foi chamada de PEM – parallel external me mory algorithm. O algoritmo PEM

permite distribuir a constru¸c˜ao, descri¸c˜ao e avalia¸c˜ao das fun¸c˜oes resultantes. Por

exemplo, usando um cluster de 14 computadores o algoritmo PEM gera uma FHPM

para 1, 024 bilh˜oes de URLs em aproximadamente 4 minutos, atingindo um speedup

quase linear. Al´em disso, para 14, 336 bilh˜oes de inteiros de 16 bytes gerados aleato-

riamente e igualmente distribu´ıdos entre as 14 m´aquinas participantes, o algoritmo

PEM produz como sa´ıda uma FHPM em approximadamente 50 minutos, resultando

em uma degrada¸c˜ao de desempenho de 20%. Pelo melhor do nosso conhecimento,

nenhum outro resultado da literatura de hashing perfeito pode ser implementado

de uma forma paralela para obter resultados melhores no que diz respeito ao de-

sempenho e a escalabilidade do que os obtidos com o algoritmo PEM. O algoritmo

xxi

PEM ´e apresentado no Cap´ıtulo 5. Uma vers˜ao preliminar do algoritmo PEM foi

apresentado em [11].

3. N´os apresentamos t´ecnicas que permitem a gera¸c˜ao de FHPs e FHPMs baseadas em

grafos randˆomicos contendo ciclos. Um resultado preliminar foi apresentado em [12],

onde melhoramos a utiliza¸c˜ao de espa¸co do algoritmo de Czech, Havas e Majewski [25]

sob a pena de gerar fun¸c˜oes na mesma forma que n˜ao s˜ao de ordem preservada. Os

dois algoritmos possuem complexidade de tempo linear em n, mas nosso algoritmo

executa, em m´edia, 59% mais r´apido do que o apresentado em [25], e as FHPMs

resultantes s˜ao armazenadas na metade do espa¸co.

No entanto, as FHPMs resultantes ainda necessitam de O(n log n) bits para serem

armazenadas. Como em [25], assumimos hashing uniforme e usamos O(n) palavras

de computadores do modelo de computa¸c˜ao Word RAM para construir as fun¸c˜oes.

Recentemente, usando id´eias similares as apresentadas em [12], fomos capazes de

otimizar a vers˜ao do algoritmo RAM que trabalha sobre grafos bipartidos para gerar

as fun¸c˜oes 40% mais r´apido do que quando ciclos n˜ao s˜ao permitidos. Estes resultados

s˜ao apresentados no Cap´ıtulo 6.

4. N´os mostramos que as FHPs e as FHPMs projetadas nesta tese podem agora serem

utilizadas em aplica¸c˜oes para as quais elas n˜ao eram consideradas uma boa op¸c˜ao no

passado. Isso ´e uma consequˆencia do fato de que as fun¸c˜oes resultantes necessitam

de um n´umero constante de bits por chave para serem armazenadas. No Cap´ıtulo 7,

mostramos que FHPMs fornecem o melhor compromisso entre utiliza¸c˜ao de espa¸co e

tempo de pesquisa quando comparadas a outros esquemas de hashing. Uma vers˜ao

preliminar deste resultado foi apresentada em [13].

5. Finalmente, criamos a biblioteca CMPH – C Minimal Perfect Hashing Library, a qual

est´a dispon´ıvel no link http://cmph.sf.net sob a licen¸ca LGPL (the GNU Lesser

General Public License). A biblioteca foi concebida por duas raz˜oes. Primeiro,

gostar´ıamos de tornar nossos algoritmos dispon´ıveis para testar sua aplicabilidade

em situa¸c˜oes pr´aticas. Segundo, percebemos que havia uma falta de uma biblioteca

similar na comunidade de software de c´odigo aberto. Recebemos muitos feedbacks

interessantes com respeito a praticidade da biblioteca. Por exemplo, mais de 2, 500

downloads foram realizados at´e Setembro de 2008 e a biblioteca foi incorporada por

xxii

duas distribui¸c˜oes do Linux: Debian

e Ubuntu

Conclus˜oes

Encontrar fun¸c˜oes hash perfeitas que s˜ao armazenadas utilizando espa¸co constante para

cada elemento do conjunto de chaves tem sido objeto de estudo h´a mais de vinte anos

pela comunidade cient´ıﬁca. Nesta tese apresentamos uma solu¸c˜ao para esse problema que

´e bem fundamentada teoricamente e pode ser utilizada na pr´atica para conjuntos est´aticos

contendo bilh˜oes de elementos. Nenhum outro resultado da literatura gera fun¸c˜oes t˜ao

compactas e que podem ser geradas por algoritmos lineares extremamente eﬁcientes e

escal´aveis como as fun¸c˜oes apresentadas neste trabalho.

Esse resultado possui in´umeras implica¸c˜oes pr´aticas. Por exemplo, mostramos que

as FHPMs projetadas neste trabalho fornecem o melhor compromisso entre utiliza¸c˜ao de

espa¸co e tempo de pesquisa para aplica¸c˜oes que precisam indexar conjuntos est´aticos de

chaves em mem´oria prim´aria. Al´em disso, devido a disponibiliza¸c˜ao dos resultados na

biblioteca CMPH, recebemos coment´arios sobre a utilidade dos resultados para escalar

modelos de tradu¸c˜ao autom´atica em t´ecnicas de aprendizado de m´aquina, para melhorar a

qualidade de ﬁltros de spam, onde grandes vocabul´arios s˜ao mantidos, dentre outras. Por

ﬁm, os resultados desta tese podem ser explorados em uma s´erie de ´areas e aplica¸c˜oes,

como indicado no Cap´ıtulo 8.

Debian ´e um projeto volunt´ario para desenvolver uma distribui¸c˜ao GNU/Linux, a qual est´a dispon´ııvel

em http://www.debian.org. O Debian iniciou a mais de uma d´ecada e, desde ent˜ao, cresceu e hoje envolve

mais de 1.000 membros com status oﬁcial de desenvolvedor, possuindo ainda muito mais volunt´arios e

contribuidores. O Debian expandiu ao ponto de englobar atualmente mais de 20.000 “pacotes” de aplica¸c˜oes

de c´odigo aberto e livre.

O projeto Ubuntu, dispon´ıvel em http://www.ubuntu.com, tenta trabalhar com o Debian para tratar

de assuntos que fazem com que alguns usu´arios evitem de usar o Debian. Ubuntu fornece um sistema

baseado no Debian com atualiza¸c˜oes e releases frequentes, utilit´arios corporativos, e uma interface de

desktop mais agrad´avel. Ubuntu permite a seus usu´arios uma forma de implantar o Debian com corre¸c˜oes

de erros cr´ıticos de seguran¸ca, uma interface consistente de desktop, e nunca est´a mais do que seis meses

distante da ´ultima vers˜ao de qualquer software na comunidade de software de c´odigo aberto e livre.

xxiii

xxiv

Fabiano Cupertino Botelho

Supervisor - Nivio Ziviani

Near-Optimal Space

Perfect Hashing Algorithms

PhD. dissertation presented to the Grad-

uate Program in Computer Science of the

Federal University of Minas Gerais as a par-

tial requirement to obtain the PhD. degree

in Computer Science.

Belo Horizonte

September 29, 2008

To my dear wife Jana´ına.

To my dear parents Maria L´ucia and Jos´e V´ıtor.

To my dear sisters Gleiciane and Cristiane.

Acknowledgements

To God for having granted me life and wisdom to realize a dream of childhood and for

the great help in diﬃcult moments.

To my dear wife Jana´ına Marcon Machado Botelho for the love, understanding by several

times when I could not give her the attention she deserves, companionship and en-

couragement during moments in which I desired to give up everything. Jana thank

you for sharing your life with me and the victories won during the entire doctorate.

With the grace of God in our lives we will continue to be very happy.

To my dear parents Maria L´ucia de Lima Botelho and Jos´e Vitor Botelho for sacriﬁces

made in the past that have given support for this achievement.

To my dear sisters Cristiane Cupertino Botelho and Gleiciane Cupertino Botelho for the

love of the best two sisters in the world.

To my dear aunt M´arcia Novaes Alves and my dear uncle Sud´ario Alves for always welcome

me with aﬀection, giving me much support throughout my doctorate.

To Prof. Nivio Ziviani for the excellent work of supervision and for being an example

of professionalism and dedication to work. His extensive experience in academic

research, and particularly in the areas of information retrieval and algorithms have

been of extreme importance to realize this work. In addition, his excellent support,

attention and encouragement were of great importance not only for completing the

doctorate, but also for my academic and professional life.

To Prof. Rasmus Pagh with whom I’ve learned a lot about techniques for designing and

analyzing hashing algorithms, being crucial his participation in this thesis.

To Prof. Yoshiharu Kohayakawa for the attention dedicated to the discussions that con-

tributed to improve the quality of this work. Thanks also to receive me at the

Institute of Mathematics and Statistics at the University of S˜ao Paulo and for all the

support given to my work during the time I spent in S˜ao Paulo.

To Prof. Edleno Silva de Moura for trusting on me and for always encouraging me.

Thanks also to receive me at the Department of Computer Science at the Federal

University of Amazonas during the time I spent in Manaus.

To the other Professors that evaluated this thesis, namely, Gaston Gonnet, Antˆonio Al-

fredo Loureiro, Wagner Meira Jr. and Jayme Luiz Szwarcﬁter for having accepted

to participate of the PhD. defense and for the relevant criticisms and suggestions.

To Djamal Belazzougui for the intelligent suggestions and contributions made to this

thesis and to the CMPH library.

To Davi Reis for having conceived the idea of the CMPH library, which was fundamental

to disseminate the results obtained in this thesis.

To my colleague and friend Marco Antˆonio Pinheiro de Cristo for the fun moments we

spent together during our English classes and for always encoraging me.

To my colleague and friend Thierson Couto for his friendship, and to be always ready to

cooperate.

To my colleague and friend David Menotti for the discussions, suggestions and criticisms

that contributed much in the beginning of this work.

To my colleague and friend David Fernandes for having received me in your home during

the time I spent in Manaus and for his endless friendship.

To my colleagues and friends of our great and unforgettable soccer team Curucu and their

wives for the friendship conquered during the period we spent together. Thanks Pedro

Neto, Maur´ıcio Figueiredo, Eduardo Freire Nakamura, Ruiter Caldas, Andr´e Lins,

Jos´e Pinheiro, Guillermo Camara Chavez, Martin Gomez Ravetti, David Patricio

Viscarra del Pozo and David Menotti for the amazing and fun moments that served

to relieve the stress of this diﬃcult period of doctorate.

To colleagues and friends from that period of our undergraduate course that, through

the mailing list intrigas99, always supported me being close or distant. I thank also

for all the good laughs that I gave when I was reading some posts of the list, which

certainly helped a lot to ease the tension in diﬃcult times.

To my colleagues and friends of the Laboratory for Treating Information (LATIN) An´ısio

Mendes Lacerda,

Alvaro Pereira Jr., Charles Ornelas Almeida, Claudine Santos

Badue, Daniel Galinkin, Denilson Pereira, Guilherme Vale Menezes, Hendrickson

R. Langbehn, Humberto Mossri, Marco Antˆonio Pinheiro de Cristo, Marco Aur´elio

Barreto Modesto, P´avel Calado and Wladmir Cardoso Brand˜ao for the criticism and

suggestions provided during the defense preparation and for the climate of friendship

we have established within LATIN.

To Professors and employees of the Department of Computer Science at the Federal

University of Minas Gerais that in various ways contributed to the completion of this

work.

To Professors and employees of the Department of Computer Engineering at the Federal

Center for Technological Education of Minas Gerais for having received me so well

and in a so respectful manner to integrate the department team.

To the scholarships granted by CAPES (Coordination of Improvement of Higher Edu-

cation) and CNPq (National Council for Scientiﬁc and Technological Development),

which served as subsidy for the time dedicated to this thesis.

Published Papers