technical-note

Evolving universal hash functions using genetic algorithms

Author:

GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

Pages 2729 - 2732

https://doi.org/10.1145/1570256.1570396

Published: 08 July 2009 Publication History

Get Access

Abstract

In this paper we explore the use of metaheuristic functions, namely Genetic Algorithms to construct Universal Hash Functions to efficiently hash a given set of keys. The Hash Functions generated in this way should give lesser number of collisions as compared to selecting them randomly from a family of Universal Hash Functions. Simulations and tests performed using this technique provide promising results. The algorithm can be used in scenarios where the input distribution of keys is changing frequently and the hash function needs to be modified often to rehash the values to reduce collisions.

References

[1]

Goodrich, M.T., Tamassia, R. Algorithm Design -- Foundations, Analysis and Internet Examples. Wiley Student Edition, 2005

Digital Library

Google Scholar

[2]

Est'ebanez, C., Hern'andez-Castro, J.C., Ribagorda, A. Evolving hash functions by means of genetic programming. In the proceedings of GECCO'06, (Seattle, Washington, USA, July 8-12, 2006) ACM Press, New York, NY, 2006, 1861--1862.

Digital Library

Google Scholar

[3]

Atkin, A.O.L., Bernstein, D.J. Prime sieves using binary quadratic forms. Mathematics of Computation 73, 2004, 1023--1030,

Crossref

Google Scholar

[4]

Mitchell, M. An Introduction to Genetic Algorithms. MIT Press, 2005

Google Scholar

Cited By

View all

Dobai RKorenek JSekanina L(2017)Evolutionary design of hash function pairs for network filtersApplied Soft Computing10.1016/j.asoc.2017.03.00956:C(173-181)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.asoc.2017.03.009
Dobai RKorenek J(2015)Evolution of Non-Cryptographic Hash Function Pairs for FPGA-Based Network Applications2015 IEEE Symposium Series on Computational Intelligence10.1109/SSCI.2015.174(1214-1219)Online publication date: Dec-2015
https://doi.org/10.1109/SSCI.2015.174
Estébanez CSaez YRecio GIsasi P(2014)AUTOMATIC DESIGN OF NONCRYPTOGRAPHIC HASH FUNCTIONS USING GENETIC PROGRAMMINGComputational Intelligence10.1111/coin.1203330:4(798-831)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1111/coin.12033
Show More Cited By

Index Terms

Evolving universal hash functions using genetic algorithms
1. Information systems
  1. Information storage systems
    1. Record storage systems
      1. Record storage alternatives
        Hashed file organization

Recommendations

Evolving hash functions by means of genetic programming
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

The design of hash functions by means of evolutionary computation is a relatively new and unexplored problem. In this work, we use Genetic Programming (GP) to evolve robust and fast hash functions. We use a fitness function based on a non-linearity ...
Evolving Universal Hash Functions Using Genetic Algorithms
ICFCC '09: Proceedings of the 2009 International Conference on Future Computer and Communication

In this paper we explore using Genetic Algorithms to construct Universal Hash Functions to efficiently hash a given set of keys. The Hash Function generated in this way should give minimum number of collisions. The algorithm has less computational ...
Universal hash functions for an infinite universe and hash trees

In this note we describe the adaptation of the universal hashing idea to an infinite universe, and to prefix hash trees. These are a structure underlying all extendible hash methods, which have up to now only been studied under the uniform hashing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '09: Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers

July 2009

1760 pages

ISBN:9781605585055

DOI:10.1145/1570256

General Chair:
Franz Rothlauf
University of Mainz, Germany

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Technical-note

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
262
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dobai RKorenek JSekanina L(2017)Evolutionary design of hash function pairs for network filtersApplied Soft Computing10.1016/j.asoc.2017.03.00956:C(173-181)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.asoc.2017.03.009
Dobai RKorenek J(2015)Evolution of Non-Cryptographic Hash Function Pairs for FPGA-Based Network Applications2015 IEEE Symposium Series on Computational Intelligence10.1109/SSCI.2015.174(1214-1219)Online publication date: Dec-2015
https://doi.org/10.1109/SSCI.2015.174
Estébanez CSaez YRecio GIsasi P(2014)AUTOMATIC DESIGN OF NONCRYPTOGRAPHIC HASH FUNCTIONS USING GENETIC PROGRAMMINGComputational Intelligence10.1111/coin.1203330:4(798-831)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1111/coin.12033
Varrette SMuszyński JBouvry P(2012)Hash function generation by means of Gene Expression ProgrammingAnnales UMCS, Informatica10.2478/v10065-012-0027-x12:3(37-53)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.2478/v10065-012-0027-x

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Evolving hash functions by means of genetic programming

Evolving Universal Hash Functions Using Genetic Algorithms

Universal hash functions for an infinite universe and hash trees