Please use this identifier to cite or link to this item: https://hdl.handle.net/1822/81094

Full metadata record
DC FieldValueLanguage
dc.contributor.advisorBaquero, Carlospor
dc.contributor.authorRodrigues, Ana Catarina Gomespor
dc.date.accessioned2022-12-12T14:04:19Z-
dc.date.available2022-12-12T14:04:19Z-
dc.date.issued2021-04-06-
dc.date.submitted2021-03-
dc.identifier.urihttps://hdl.handle.net/1822/81094-
dc.descriptionDissertação de mestrado integrado em Engenharia Informáticapor
dc.description.abstractA Bloom Filter is a probabilistic data structure designed to check, rapidly and memory-efficiently, whether an element is present in a set. It has been vastly used in various computing areas and several variants, allowing deletions, dynamic sets and working with sliding windows, have surfaced over the years. In many systems, it becomes relevant to identify the more recent information in the data stream. However, the majority of the sliding window schemes consider the most recent elements of a data stream without taking into account time as a factor. While this allows, e.g., saving the most recent 10000 elements, it does not easily translate into storing data received in the last 60 seconds, unless the insertion rate is stable and known in advance. In this thesis, a new technique is explored, Unproved in terms of time complexity and memory usage compared to the already existing ones, that can save information of a given time period and correctly identify it as present when queried, while also being able to retire data when it becomes stale. This new solution can be employed in a wide range of real world applications, such as in advertising, networking, fraud detection and distributed denial of service attacks prevention.eng
dc.description.abstractUm Bloom Filter é uma estrutura de dados probabilistica, cuja função é verificar, rapida-mente e eficientemente em termos de memória, se um elemento está presente no set. Tem sido vastamente utilizado em diversas áreas da informática e várias variantes, que permitem remoções, seis dinâmicos e funcionam com sliding windows, têm surgido ao longo dos anos. Em inúmeros sistemas, toma-se relevante identificar a informação mais recente do fluxo de dados. Contudo, a maioria dos esquemas em sliding windows considera os elementos mais recentes de um fluxo de dados sem ter em conta o tempo como um fator. Enquanto que isto permite, e.g., guardar os 10000 elementos mais recentes, não se traduz facilmente em armazenar dados recebidos nos últimos 60 segundos, a menos que a taxa de inserção seja estável e conhecida antecipadamente. Nesta dissertação, uma nova técnica é explorada, melhorada em termos de complexidade temporal e uso de memória comparativamente a outras já existentes, que consegue guardar informação de um dado período de tempo e identificá-la corretamente como presente quando uma consulta é feita, como também é capaz de eliminar dados quando estes "envelhecem". Esta nova solução pode ser utilizada numa vasta gama de aplicações do mundo real, tais como em publicidade, networking, deteção de fraude e prevenção de ataques distribuídos de negação de serviço.por
dc.language.isoengpor
dc.rightsopenAccesspor
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/por
dc.subjectBloom filterpor
dc.subjectData streamspor
dc.subjectData structurespor
dc.subjectDictionariespor
dc.subjectWindow modelspor
dc.subjectFluxo de dadospor
dc.subjectEstruturas de dadospor
dc.subjectDicionáriospor
dc.subjectModelos de janelaspor
dc.titleBloom filters for stream windowspor
dc.typemasterThesiseng
dc.identifier.tid203047753por
thesis.degree.grantorUniversidade do Minhopor
sdum.degree.grade18 valorespor
sdum.uoeiEscola de Engenhariapor
dc.subject.fosEngenharia e Tecnologia::Engenharia Eletrotécnica, Eletrónica e Informáticapor
Appears in Collections:BUM - Dissertações de Mestrado
DI - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat 
Ana Catarina Gomes Rodrigues.pdf9,68 MBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID