Accelerated processing of spatio-temporal social graphs

From Master Projects
Revision as of 17:29, 16 January 2014 by Cma330 (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


About Accelerated processing of spatio-temporal social graphs


Description

Wearable sensors are important assets for the emerging field of Computational Social Science which investigates complex social systems through quantitative modeling. While research in this field has mainly focused, so far, on the analysis of online social networks, the study of crowds is emerging as an equally interesting field.

Physical proximity is one of the signals that has been used to study the collective behavior of a crowd. Of particular interest are crowd dynamics with a strong spatio-temporal nature, such as pedestrian lanes, bottlenecks, or social groups. Physical proximity between individuals can be conveniently measured through miniatured wearable sensors (e.g. in a mobile phone, a smart watch, an e-bracelet) and represented through a spatio-temporal graph. In such a graph, individuals are represented through vertices, and two vertices are connected through an edge if, at any given time, the two individuals were in physical proximity. Within this framework, detecting crowd dynamics boils down to matching patterns in a graph. Timely detection of crowd dynamics, and characterizing for example whether they represent a dangerous scenario, is important to avoid disasters. Unfortunately, graph pattern matching is an expensive computation, worsened by the nature of spatio-temporal social graphs, which are characterized by tens of thousands of vertices and a high rate of edges being added and/or removed every second.

Dealing with large-scale graph processing has recently become a challenge for high-performance computing (HPC). Making efficient use of the massive parallelism of modern architecture to solve large-scale graphs analytics is a very relevant, yet challenging research topic.

We aim at addressing the computational challenges of large spatio-temporal graphs using modern HPC architectures. We will focus on designing parallel graph pattern matching algorithms to address a number of interesting crowd dynamics, and implementing them efficiently on many-core CPUs, GPUs, and combinations thereof.

This project is part of a DSRC project, and there are two funded positions for 0.2fte in 12 months.