Czasopismo | PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE | Rocznik 2019 - zeszyt 3

Realizacja sprzętowego generatora indeksów z wykorzystaniem filtru Blooma

Hardware implementation of index generation unit using a Bloom Filter

10.15199/59.2019.3.2

Tomasz MAZURKIEWICZ

nr katalogowy: 119358
10.15199/59.2019.3.2

Streszczenie

Funkcje generowania indeksów są wykorzystywane przede wszystkim do wyszukiwania wzorców w dużych zbiorach danych. Spowodowało to znaczny wzrost zainteresowania efektywną realizacją tych funkcji w czasach dynamicznego rozwoju technologii, takich jak np. Big Data. W literaturze przedstawiono wiele algorytmów skutecznie minimalizujących tego typu funkcje. Równocześnie zaproponowano metody ich sprzętowej realizacji. W ramach niniejszej pracy przedstawiono możliwość implementacji funkcji generowania indeksów z wykorzystaniem struktury probabilistycznej - filtru Blooma. Pokazano, że kosztem wprowadzenia niewielkiego prawdopodobieństwa otrzymania wyniku fałszywie pozytywnego, możliwa jest efektywna implementacja proponowanego rozwiązania. W tym celu przedstawiono ideę filtru Blooma z pojedynczą funkcją skrótu. Uzyskane wyniki dowodzą, że opisana struktura zapewnia mniejsze wykorzystanie pamięci od rozwiązania opisywanego w literaturze. Mimo że konieczne jest zrealizowanie dodatkowych obliczeń, w pracy pokazano, że mogą być one efektywnie zrealizowane w układach FPG A.

Abstract

Index generation functions are primarily used for pattern matching in large data sets. Efficient implementation of these functions is attracting significant interest due to the dynamic development of technologies such as Big Data. In the literature many algorithms were presented that efficiently minimize these functions. At the same time, methods of efficient hardware implementation have been proposed. In this paper, the possibility of implementing index generation functions using the probabilistic structure, i.e. a B loom filter, was analyzed. We show that at the cost of a small probability of a false positive result, it is possible to efficiently implement the proposed method. Furthermore, the idea of an One-Hashing Bloom filter is presented. The obtained results prove that the described structure provides lower memory usage than the structure described in the literature. Even though it requires additional computations, we prove that these operations can be efficiently implemented using FPG A devices.

Słowa kluczowe

Keywords

Bibliografia

[1] Astola J. T. (et al.): An algebraic approach to reducing the number of variables of incompletely defined discrete functions, IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL), pp. 107-112, 2016.
[2] Augustynowicz P.: "Dobór funkcji skrótu spełniających wymagania sprzętowej implementacji filtru Blooma", Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 8-9, s. 605-608, 2018.
[3] Bertoni G. (et al.): The Keccak reference, SHA-3 competition (round 3), 2011, http://keccak.neokeon.org/
[4] Bertoni G. (et al.): Keccak implementation overview, ver. 3.1., 2011, http://keccak.neokeon.org/
[5] Bloom B. H.: "Space/Time Trade-offs in Hash Coding with Allowable Errors", Commun. ACM, vol. 13, no. 7, pp. 422-426, Jul. 1970.
[6] Bogdanov A. (et al.): "SPONGENT: The Design Space of Lightweight Cryptographic Hasing", Cryptology ePrint Archive Report 697/2011, https://eprint.iacr.org/
[7] Borowik G.: "Optimization on the complementation procedure towards efficient implementation of the index generation function", International Journal of Applied Mathematics and Computer Science, pp. 803-815, 2018.
[8] Broder A., M. Mitzenmacher: "Network Applications of Bloom Filters: A Survey", in Internet Mathematics, vol. 1, no. 4, 2003, pp. 485-509.
[9] Bussi K (et al.): "Neeva: A Lightweight Hash Function", Cryptology ePrint Archive Report 042/2016, https://eprint.iacr.org/.
[10] Butler J. T., T. Sasao: Fast Hardware Computation of x Mod z, IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum, Shanghai, pp. 294-297, 2011.
[11] Fan B. (et al.): Cuckoo Filter: Practically Better Than Bloom, in Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, ser. CoNEXT ’14. New York, NY, USA: ACM, 2014, pp. 75-88.
[12] Fan L. (et al.): "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol", SIGCOMM Comput. Commun. Rev., vol. 28, no. 4, pp. 254-265, 1998.
[13] Fowler G., L.C. Noll, P. Vo: Fowler/Noll/Vo (FNV) Hash, 1991
[14] Hodžić S., E. Pasalic, A. Chattopadhyay: "An iterative method for linear decomposition of index generating functions", Cryptography and Communications, pp. 1-24, 2019.
[15] Lu J. (et al.): "Low Computational Cost Bloom Filters", IEEE/ACM Transactions on Networking, vol. 26, no. 5, pp. 2254-2267, Oct. 2018.
[16] Łuba T., G. Borowik: Synteza logiczna, Oficyna Wydawnicza PW, Warszawa 2015.
[17] Łuba T., T. Mazurkiewicz: "Synteza generatorów indeksów metodami dekompozycji liniowej i funkcjonalnej", Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 5, s. 122-128, 2018.
[18] Łuba T., T. Mazurkiewicz: "Dekompozycja funkcjonalna w syntezie funkcji generowania indeksów", Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 1, s. 19-25, 2019.
[19] Mazurkiewicz T., M. Rawski: "Przegląd algorytmów kryptograficznych pod względem realizacji sprzętowego koprocesora do zastosowań mobilnych", Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 11, s. 1293-1298, 2016.
[20] Mazurkiewicz T., T. Łuba: "Metody wyboru dekompozycji dla algorytmu z wykorzystaniem zbiorów niezgodności i ich wpływ na minimalizację generatorów indeksów", Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 8-9, s. 722-725, 2018.
[21] Mazurkiewicz T., G. Borowik, T. Łuba: Construction of Index Generation Unit using probabilistic data structures, 26th International Conference on Systems Engineering (ISCEng), pp. 1-7, 2018.
[22] Pearson P.K.: "Fast Hashing of Variable-Length Text Strings", Communications of the ACM 33(6):677, 1990.
[23] Sasao T.: Memory-Based Logic Synthesis, Springer, 2011.
[24] Sasao T.: Index generation functions: Minimization methods, IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL), pp. 197-206, 2017.
[25] Simovici D.A., M. Zimand, D. Pletea: Several remarks on index generation functions, IEEE 42nd International Symposium on Multiple-Valued Logic (ISMVL), 2012.
[26] Tarkoma S., C.E. Rothenberg, E. Lagerspetz: "Theory and practice of bloom filters for distributed systems", IEEE Communications Surveys Tutorials, vol. 14, no. 1, pp. 131-155, 2012.

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


e-Publikacja (format pdf) - nr 119358 "Realizacja sprzętowego ge..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


PRZEGLĄD TELEKOMUNIKACYJNY - e-zeszyt (pdf) 2019-3 licencja: Osobista Produkt cyfrowy	30.50 zł

Prenumerata

PRZEGLĄD TELEKOMUNIKACYJNY - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

300.00 zł

PRZEGLĄD TELEKOMUNIKACYJNY - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD TELEKOMUNIKACYJNY - papierowa prenumerata roczna	348.00 zł brutto 322.22 zł netto 25.78 zł VAT (stawka VAT 8%)
PRZEGLĄD TELEKOMUNIKACYJNY - pakowanie i wysyłka	21.00 zł brutto 17.07 zł netto 3.93 zł VAT (stawka VAT 23%)

369.00 zł

PRZEGLĄD TELEKOMUNIKACYJNY - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD TELEKOMUNIKACYJNY - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	450.00 zł brutto 416.67 zł netto 33.33 zł VAT (stawka VAT 8%)

450.00 zł

Zeszyt

2019-3

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma