Multi-objective Query Optimization in Smartphone Social Networks

The bulk of social network applications for smart phones (e.g., Twitter, Face book, Foursquare, etc.) currently rely on centralized or cloud-like architectures in order to carry out their data sharing and searching tasks. Unfortunately, the given model introduces both data-disclosure concerns (e.g., disclosing all captured media to a central entity) and performance concerns (e.g., consuming precious smart phone battery and bandwidth during content uploads). In this paper, we present a novel framework, coined Smart Opt, for searching objects (e.g., images, videos, etc.) captured by the users in a mobile social community. Our framework, is founded on an in-situ data storage model, where captured objects remain local on their owner´s smart phones and searches then take place over a novel lookup structure we compute dynamically, coined the Multi-Objective Query Routing Tree (MO-QRT). Our structure concurrently optimizes several conflicting objectives (i.e., it minimizes energy consumption, minimizes search delay and maximizes query recall), using a Multi-objective Evolutionary Algorithm based on Decomposition (MOEA/D) that calculates a diverse set of high quality non-dominated solutions in a single run. We assess our ideas with mobility patterns derived by Microsoft´s Geolife project and social patterns derived by DBLP. Our study reveals that Smart Opt can yield query recall rates of 95%, with one order of magnitude less time and two orders of magnitude less energy than its competitors.