Detail publikace

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

KIDOŇ Marek a 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, s. 1720-1727. ISBN 978-1-5090-4601-0.
Název česky
Evoluční návrh hašovacích funkcí pro hašování IP adres s použitím genetického programování
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Kidoň Marek, Ing. (UPSY FIT VUT)
Dobai Roland, Ing., Ph.D. (UPSY FIT VUT)
Abstrakt

Hašovací tabulky jsou základní vyhledávací datové struktury. Klíčovým prvkem těchto tabulek jsou hašovací funkce, protože mají velký vliv na jejich latence. Špatně navržená hašovací funkce může zpomalit hašovaní tvorbou kolizí, což je nepříznivý stav a musí byt řešený na úkor výpočtového času. Neexistuje deterministická metoda pro návrh dobře fungující hašovací funkce. Návrhář spoléhá pouze na jeho/její zkoušenosti, vědomosti a intuice. Tento článek je orientovaný na evoluční návrh hašovacích funkcí pro Kukaččí hašování, který je moderním způsobem řešení kolizí. Jeho hlavní výhodou je konstantní čas vyhledávaní, kterého je dosaženo použitím dvou či více hašovacích funkcí pro hašovací tabulku. Hašovací funkce jsou navrženy automatickým použitím genetického programování z obecných operací jako například násobení nebo bitový posuv. Evolučně navážené funkce jsou 2.7-7 krát rychlejší, umožňují uložení o 1-1,6% více klíčů a jsou konstruovány z méně jednoduchých operací v porovnaní s řešením vytvořeným člověkem v problematice hašování IP adres.

Rok
2017
Strany
1720-1727
Sborník
2017 IEEE Congress on Evolutionary Computation (CEC)
Konference
IEEE Congress on Evolutionary Computation 2017, Donostia - San Sebastián, ES
ISBN
978-1-5090-4601-0
Vydavatel
Institute of Electrical and Electronics Engineers
Místo
San Sebastian, ES
DOI
10.1109/CEC.2017.7969509
UT WoS
000426929700222
EID Scopus
2-s2.0-85028503249
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"
}
Nahoru