Utilização de algoritmos de sketching na análise de streams de dados: um caso de estudo

Abstract

Hoje é vulgar encontrarmos inúmeras aplicações que envolvem nos seus serviços tarefas de processamento e análise de streams de dados. Estas tarefas não são de fácil implementação nem de execução, pelo menos em situações nas quais pretendemos fazer a análise do conteúdo de uma stream no tempo próximo do tempo real. Um dos principais problemas que enfrentamos na realização dessas tarefas é saber como identificar um ou mais elementos de dados que possam estar a circular na stream em tempo útil. A rapidez com que os dados são transportados por uma stream é enorme o que complica imenso o seu processo de análise, dificultando, obviamente, a identificação dos elementos de dados que se pretendem analisar. Uma das técnicas que podem ser utilizadas para implementar a análise de streams de dados é o sketching, que nos fornece mecanismos muito interessantes para descobrir padrões de dados de forma bastante expedita. Isso é possível, porque o sketching permite armazenar pequenos elementos de informação sobre os dados que circula numa stream, usando para isso uma combinação de técnicas de hashing, de contagem e de filtragem, mantendo um bom equilíbrio entre o uso de memória e a precisão da identificação dos elementos de dados em análise. Nesta dissertação estudámos e analisámos um conjunto de algoritmos de sketching, com o objetivo de verificar a forma como cada um deles atua no processamento e análise de streams de dados em tempo muito próximo do real. Para isso, desenvolvemos um sistema específico capaz de fazer a identificação de eventuais pontos de estrangulamento de uma rede de distribuição de água, aplicando cada um dos diferentes algoritmos que estudámos. O sistema desenvolvido permitiu correlacionar os diferentes parâmetros que podem influenciar o funcionamento de uma rede de distribuição de água, que utilizámos como caso de estudo, e, consequentemente, avaliar o desempenho de cada um dos algoritmos aplicados.

Nowadays it is usual to find several applications that engage, in its services, processing tasks and data stream analysis. In this context, given certain situations, for example, when the purpose is to analyse the content of a stream in time near the real time, these tasks are neither easy to implement nor to execute. One of the biggest problems faced during the implementation of these tasks is to understand how to identify one or more data elements that may be circulating in the stream in useful time. Moreover, the quickness of the data transportation throughout a stream is huge and this stunts its analysis process, making the identification of the data elements intended to be analysed more difficult. Therefore, one of the techniques that can be applied to implement the data stream analysis is the sketching that provides interesting mechanisms used to find data patterns in a very spontaneous way. Obviously, this is possible hence the sketching allows to store small elements of information about the data that circulates in a stream through a combination techniques of hashing, counting and filtration, while keeping a good balance between the memory use and the precision about the identification of the elements in the data in analysis. Throughout this dissertation it was studied and analysed a range of sketching algorithms with the aim to verify the way as each of them proceed in the processing and analysis of data stream in a time very near the real time. To do that, it was developed a specified system capable to do the identification of possible strangulation points in a water distribution grid applying each one of the algorithms that were studied. The developed system allowed to correlate the different parameters that can disturb the normal function of a water distribution grid, the case used as the study case, and, consequently, evaluate the performance of each one of the applied logarithms.