Faculty of Information Technology, BUT

Publication Details

Evolutionary design of hash functions for IP address hashing using genetic programming

KIDOŇ Marek and DOBAI Roland. Evolutionary design of hash functions for IP address hashing using genetic programming. In: 2017 IEEE Congress on Evolutionary Computation (CEC). San Sebastian: Institute of Electrical and Electronics Engineers, 2017, pp. 1720-1727. ISBN 978-1-5090-4601-0.
Czech title
Evoluční návrh hašovacích funkcí pro hašování IP adres s použitím genetického programování
Type
conference paper
Language
english
Authors
Kidoň Marek, Ing. (DCSY FIT BUT)
Dobai Roland, Ing., Ph.D. (DCSY FIT BUT)
Keywords
Hash function, Hash table, Cuckoo hashing, Evolutionary design, Genetic programming
Abstract
Hash tables are common lookup data structures. A key element of such data structure is a hash function because it greatly affects its latency. A badly designed hash function may slow down the hash table by producing hash collisions which is a negative state that has to be resolved using additional computation time. There is no deterministic method for designing a well performing hash function. The designer solely relies on his/her experience, knowledge or intuition. This paper focuses on the evolutionary design of hash functions for Cuckoo hashing which is a modern approach to collision resolution. Its main benefit is constant time complexity of lookup which is achieved by using two or more hash functions per hash table. Hash functions are automatically designed using common elementary hashing operations such as multiplication or binary shift by means of genetic programming. The evolved hash functions are about 2.7 to 7 times faster, can utilize about 1 to 1.6% more keys and use fewer elementary operations than human-created counterparts on the IP address hashing problem.
Published
2017
Pages
1720-1727
Proceedings
2017 IEEE Congress on Evolutionary Computation (CEC)
Conference
IEEE Congress on Evolutionary Computation 2017, Donostia - San Sebastián, ES
ISBN
978-1-5090-4601-0
Publisher
Institute of Electrical and Electronics Engineers
Place
San Sebastian, ES
DOI
BibTeX
@INPROCEEDINGS{FITPUB11322,
   author = "Marek Kido\v{n} and Roland Dobai",
   title = "Evolutionary design of hash functions for IP address hashing using genetic programming",
   pages = "1720--1727",
   booktitle = "2017 IEEE Congress on Evolutionary Computation (CEC)",
   year = 2017,
   location = "San Sebastian, ES",
   publisher = "Institute of Electrical and Electronics Engineers",
   ISBN = "978-1-5090-4601-0",
   doi = "10.1109/CEC.2017.7969509",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11322"
}
Back to top