Deterministic and efficient minimal perfect hashing schemes

Authors

  • Leandro Miranda Zatesko Universidade Federal do Paraná
  • Jair Donadelli Jr. Universidade Federal do ABC

DOI:

https://doi.org/10.22456/2175-2745.26905

Abstract

Neste trabalho apresentamos versões determinísticas para os esquemas
de hashing de Botelho, Kohayakawa e Ziviani (2005) e por Botelho, Pagh e Ziviani
(2007). Também respondemos a um problema deixado em aberto no primeiro dos
trabalhos, relacionado à prova da corretude e à análise de complexidade do esquema
por eles proposto. As versões determinísticas desenvolvidas foram implementadas
e testadas sobre conjuntos de dados com até 25.000.000 de chaves, e os resultados
verificados se mostraram equivalentes aos dos algoritmos aleatorizados originais.

Downloads

Download data is not yet available.

Published

2013-04-13

How to Cite

Zatesko, L. M., & Donadelli Jr., J. (2013). Deterministic and efficient minimal perfect hashing schemes. Revista De Informática Teórica E Aplicada, 20(2), 56–72. https://doi.org/10.22456/2175-2745.26905

Issue

Section

Regular Papers