Projecte realitzat en el marc d’un programa de mobilitat amb la University of Southern California

[ANGLÈS] Graph representation of data is a current trend in research nowadays, especially for those problems dealing with huge amounts of information that need to be analyzed and studied. Many fields can benefit from the use of graphs. Just recently, signal processing has begun to be applied to them, still being a fairly new concept that needs to be explored in more depth. Various applications of the signal processing applied on graphs are currently studied, such as solving the Recommendation System problem. This project extends the work and research done in the field of signal processing applied to graph, but taking into account the current trend of using large graphs from massive datasets. For this case, frameworks have been developed that allow us to operate with graphs in a distributed environment. GraphLab will be used in this project as it is a leading high-performance distributed computation graph-based framework that has already been used in research to study and apply algorithms on large graphs. In this project, a specific signal processing tool commonly used is studied and developed: the filtering operation. Two different implementations of a filtering technique are made, taking into account the needs for a distributed computation design. The performance and scalability of the distributed graph filter will be analyzed in order to observe how the framework behaves with different graphs, varying the size and the scarcity of them. The filtering program proposed in this project delivers an efficient way to compute on a graph allowing multiple applications.

[CASTELLÀ] Las representaciones de datos mediante grafos suponen una tendencia en investigación actualmente, especialmente para aquellos problemas que tratan con grandes cantidades de información que necesitan ser analizadas y estudiadas. Muchos campos se pueden beneficiar del uso de grafos. Recientemente, el procesado de señal se ha empezado a aplicar en grafos, siendo aún un concepto bastante nuevo que requiere ser explorado en más detalle. Varias aplicaciones del procesado de señal en grafos se están estudiando actualmente, como por ejemplo resolver el problema de Sistema de Recomendaciones. Este proyecto extiende la investigación hecha en el campo de procesado de señal aplicado en grafos, pero teniendo en cuenta la tendencia actual de usar grafos grandes provenientes de bases de datos masivas. Para este caso, se han desarrollado frameworks que nos permiten operar con grafos en un entorno distribuido. GraphLab se usará en este proyecto ya que es un framework líder en computación distribuida de alto rendimiento basado en grafos que se ha usado ya en investigación para estudiar y aplicar algoritmos en grandes grafos. En este proyecto, una herramienta de procesado de señal especifica ha sido estudiada y desarrollada: la operación de filtrado. Dos implementaciones diferentes de técnicas de filtrado han sido desarrolladas, teniendo en cuenta las necesidades de diseño para una computación distribuida. El redimiendo y escalabilidad del filtrado distribuido para grafos se ha analizado para poder observar como se comporta el framework con diferentes grafos, variando el tamaño y la conectividad entre nodos. El programa de filtrado propuesto en este proyecto ofrece una forma efectiva para computar en grafos permitiendo múltiples aplicaciones.

[CATALÀ] Les representacions de dades mitjançant grafs suposa una tendencia en investigació actualment, especialment per aquells problemes que tracten amb grans quantitats d’informació que necessiten ser analitzades i estudiades. Molts camps es poden beneficiar de l’ús de grafs. Recentment, el processat de senyal s’ha començat a aplicar en grafs, essent encara un concepte bastant nou que requereix ser explorat en més detall. Varies aplicacions del processat de senyal en grafs s’estan estudiant actualment, com per exemple resoldre el problema de Sistemes de Recomanació. Aquest projecte extén la investigació feta en el camp del processat de senyal aplicat a grafs, però tenint en compte la tendencia actual d’usar grafs grans que provenen de bases de dades massives. Per aquest cas, s’han desenvolupat frameworks que ens permeten operar amb els grafs en un entorn distribuit. GraphLab s’usarà en aquest projecte ja que és un framework lider en la computació distribuida d’alt rendiment basat en grafs que s’ha usat ja en investigació per estudiar i aplicar algorismes en grans grafs. En aquest projecte, una eina de processat de senyal específica ha estat estudiada i desenvolupada: la operació de filtrat. Dos implementacions diferents de tècniques de filtrat han estat desenvolupades, tenint en compte les necessitats de diseny per a una computació distribuida. El rendiment i escalabilitat del filtrat distribuit per a grafs s’ha analizat per poder observar com es comporta el framework amb diferents grafs, variant la mida i la connectivitat entre nodes. El programa de filtrat proposat en aquest projecte ofereix una forma efectiva per a computar en grafs permetent múltiples aplicacions.