Query Processing in Geo-Social Networks

PhD Thesis Proposal Defence


Title: "Query Processing in Geo-Social Networks"

by

Mr. Nikolaos ARMENATZOGLOU


Abstract:

The proliferation of GPS-enabled mobile devises and the popularity of social 
networking have recently led to the rapid growth of Geo-Social Networks 
(GeoSNs). GeoSNs have created a fertile ground for novel location-based social 
interactions, advertising and market analysis. In this proposal we introduce: 
i) a general framework for Geo-Social query processing, ii) GeoSN queries, 
which extract useful information combining both the social relationships and 
the current location of the users, iii) Geo-Social Ranking (GSR) problem that 
ranks the users based on their social and spatial attributes, and iv) Real-Time 
Multi-criteria Graph Partitioning (RMGP) task for partitioning the social graph 
of a GeoSN.

Initially, we propose a general framework for Geo-Social query processing that 
offers flexible data management and algorithmic design. It segregates the 
social, geographical and query processing modules. Then, each GeoSN query is 
processed via a transparent combination of primitive queries issued to the 
social and geographical modules. We demonstrate the power of our framework by 
introducing several "basic" and "advanced" query types, and devising various 
solutions for each type.

GSR ranks the users of a GeoSN based on their distance to a given query 
location q, the number of their friends in the vicinity of q, and possibly the 
connectivity of those friends. We propose four GSR functions that assign scores 
in different ways: i) LC, which is a weighted linear combination of social 
(i.e., friendships) and spatial (i.e., distance to q) aspects, ii) RC, which is 
a ratio combination of the two aspects, iii) HGS, which considers the number of 
friends in coincident circles centered at q, and iv) GST, which takes into 
account triangles of friends in the vicinity of q. We investigate the behavior 
of the functions, qualitatively assess their results, and study the effects of 
their parameters. Moreover, for each ranking function, we design a query 
processing technique that utilizes its specific characteristics to efficiently 
retrieve the top-k users.

RMGP groups the users based on their social connectivity and their distance to 
a set of input geographical points that represent the locations of social 
events. We consider RMGP as an on-line graph partitioning task, which may be 
frequently performed for different query parameters (e.g., social events). In 
order to overcome the serious performance issues associated with the large 
social graphs found in practice, we develop solutions based on a game theoretic 
framework. Specifically, we consider each user as a player, whose goal is to 
find the class that optimizes his objective function. We propose algorithms 
based on best-response dynamics and analyze their properties.

Finally, we perform an exhaustive experimental evaluation for all proposed 
methods with real and synthetic datasets in centralized and decentralized 
settings. Our results confirm the viability of our approaches in typical 
large-scale GeoSNs.


Date:			Wednesday, 28 January 2015

Time:                   12:00noon - 2:00pm

Venue:                  Room 4483
                        lifts 25/26

Committee Members:	Prof. Dimitris Papadias (Supervisor)
  			Dr. Raymond Wong (Chairperson)
  			Dr. Qiong Luo
  			Prof. Daniel Palomar (ECE)


**** ALL are Welcome ****