Original title: Implementace Bloomových filtrů v FPGA
Translated title: Implementation of Bloom Filters in FPGA
Authors: Matoušek, Denis ; Kaštil, Jan (referee) ; Žádník, Martin (advisor)
Document type: Bachelor's theses
Year: 2011
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Práce se zabývá pravděpodobnostní datovou strukturou Bloomův filtr a jeho variantami - počítaným Bloomovým filtrem a multistage filtrem. Je vysvětlen princip těchto datových struktur a jsou uvedeny matematické vztahy popisující jejich vlastnosti včetně vztahu pro minimalizaci falešných pozitivních výsledků. Je proveden výběr vhodné hašovací funkce z hlediska implementace v FPGA čipu. Návrhy architektur hašovací funkce a datových struktur jsou implementovány v jazyce VHDL a je provedena jejich syntéza. Její výsledky jsou zhodnoceny z hlediska zabraných zdrojů na FPGA čipu, kritické cesty a maximální frekvence. The thesis deals with probabilistic data structure Bloom filter and its modifications - counting Bloom filter and multistage filter. The fundamentals of these data structures are explained and the mathematical equations describing their properties including the equation to minimize the false positive rate are shown. Appropriate hash function is chosen considering an implementation on a FPGA chip. Designs of architectures of the hash function and data structures are implemented in VHDL language and their synthesis is done. Its results are discussed considering occupied resources of a FPGA chip, a critical path and maximum frequency.
Keywords: Bloom filter; counting Bloom filter; false positive; FPGA; hashing; multistage filter; VHDL.; Bloomův filtr; falešný pozitivní výsledek; FPGA; hašování; multistage filtr; počítaný Bloomův filtr; VHDL.

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/55726

Permalink: http://www.nusl.cz/ntk/nusl-238776


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses