Reverse Nearest Social Group Query

Open Access
- Author:
- Upreti, Nitish
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Master of Science
- Document Type:
- Master Thesis
- Date of Defense:
- July 01, 2015
- Committee Members:
- Wang Chien Lee, Thesis Advisor/Co-Advisor
Kamesh Madduri, Thesis Advisor/Co-Advisor - Keywords:
- socio-spatial
database
query
social
spatial
influence
query design - Abstract:
- Spatial data management issues, widely studied in the past few decades, have posed great challenges to researchers. A variety of efficient queries for calculating containment, intersection, nearest neighbors, reverse nearest neighbors among others have been proposed and studied. However, in recent years, increasing smartphone proliferation and web connectivity has lead to a new wave. The increasing popularity of modern LBSNs (Location Based Social Networks) such as Facebook, Foursquare, Periscope, Meetup among others that have never before existed. These services allow users to instantly share their location experiences around this activity with others. Location Based Service providers thus have a lot of user generated socio-spatial data that needs to be stored, processed and analyzed. We strongly believe that novel socio-spatial storage and querying systems are required to meet this need in the near future. In this work, we particularly focus on the challenge of quantifying influence in the socio-spatial domain. The idea is to find groups that satisfy spatial (proximity) and social (group cohesion) constraints and thus can be considered in the influence set for a given query point. To solve this problem, we propose the idea of Reverse Nearest Social Group (RNSG) Query. This socio-spatial query is strongly related to Reverse Nearest Neighbor (RNN) query that has been of much interest to spatial data researchers in the past. Unlike the Reverse Nearest Neighbor query that finds individuals having query point as the Nearest Neighbor, RNSG query finds all social groups that satisfy k-core constraint and have their farthest member (individual with maximum euclidean distance to the query point) as a Reverse Nearest Neighbor of the query point. Compared to conventional RNN queries, RNSGQ is much more challenging because of the added social constraint. To tackle this challenging research problem, we propose an algorithm R-SAGE(Rnn-based Social-Aware Group discovEry Algorithm) to find all RNSG(s) efficiently. Experiments conducted on real world datasets show that the proposed R-SAGE algorithm outperforms the other baselines sig- nificantly. The proposed solution thus has huge implications on solving various problems in a variety of existing and upcoming domains such as Location Based Systems, Decision Support Systems, Social Marketing, Continuous Referral Systems to name a few. The efficient RNSGQ framework facilitates solving these novel socio-spatial problems and thus coping up with the recent challenges.