Transcript Andreas Konstantinidis - Department of Computer Science

Socially-aware Query Routing in Mobile
Social Networks
Hellenic Data Management Symposium, 2010
Andreas Konstantinidis, Demetrios Zeinalipour-Yazti
Department of Computer Science, University of Cyprus, Cyprus
and Kun Yang
School of Computer Science and Electronic Engineering, University of Essex, UK
Social Networks (on the Web)
Social Network: a set of people or groups of people
with some pattern of contact or interaction among
them
– Attracted billions of active users under major online social
network systems
– Examples: MySpace, Facebook, Twitter
Speaker: Andreas Konstantinidis – University of Cyprus
Mobile Social Networks (MoSoNets)
Mobile Social Network: Social Network applications
for smartphone devices.
– Examples: Google Latitude and Google Buzz, Foursquare,
Gowalla and Loopt.
•
•
Smartphone: offers more advanced
computing and connectivity than a
basic 'feature phone'.
E.g., OS: Android, Nokia’s Maemo, Apple X
Speaker: Andreas Konstantinidis – University of Cyprus
Mobile Social Networks (MoSoNets)
• Mobile Social
Network applications
are projected to
grow in the future.
• Google Latitude
already reports over
3 Million Users with
more than 1 Million
Users available
online concurrently.
Speaker: Andreas Konstantinidis – University of Cyprus
Motivation
• Numerous research challenges arise in the context of
Mobile Social Networks
– Data Management Challenges: Query Processing and
Retrieval, Storage (Cloud vs. Local), Access Methods, etc.
– Mobility Challenges: Context Awareness, etc.
– Social Challenges: Privacy, etc.
– System Challenges: Architectures, Platforms etc.
In this work we attempt to exploit knowledge about
the underlying social network in order to improve
query routing in Mobile Social Networks.
Speaker: Andreas Konstantinidis – University of Cyprus
Example Scenario
Scenario: Five (5) users moving in Lower Manhattan
collecting data (video, photos, sound, rss, …)
U5
U2
U3
U4
U1
Speaker: Andreas Konstantinidis – University of Cyprus
Example Scenario: Assumptions
Assumptions
• Users feature “long-range” connectivity (e.g., WiFi |
3G) and “short-range” connectivity (e.g., Bluetooth)
• Communication Links are Expensive (i.e., due to
energy and bandwidth constraints)
>> Bandwidth Constraints
• 4G nets in the US (Sprint, AT&T) promise 310MBps but offer as low as 0,6MBps.
>> Power Constraints :
• 0.40W – No connections
• 0.52W – Bluetooth Connection Established
• 1.73W – Download 120KBps via 3G
Speaker: Andreas Konstantinidis – University of Cyprus
Example Scenario
Mobile Social
Networking Service
Find Video of street artists
performing right now?
U1
U2
U3
Fact: Content is
Distributed and there
is no Global Index!
Problem: How to find
the answer without
flooding the SmartNet
U4
U5
{(X,Y,T,obj) | X,Y: spatial, T: temporal, Obj: object}
Speaker: Andreas Konstantinidis – University of Cyprus
Example Scenario
Social Graph (G)
Interest Matrix (Profile)
MoSoNet Service
Query
Processor
Query
Routing Tree
(T)
U1
U2
Arts
Food
X
X
X
U3
X
U4
…
Cinema
X
X
Disseminate Query using T
(WiFi| 3G)
Bluetooth (cheaper)
Bluetooth
(cheaper)
U1
U2
U3
U4
U5
Speaker: Andreas Konstantinidis – University of Cyprus
Example Scenario
MSN Service
Query
Processor
We do not consider this phase
in greater detail
Download Photo\Video
(via WiFi|3G|Bluetooth)
U1
U2
U3
U4
U5
Speaker: Andreas Konstantinidis – University of Cyprus
Overview
• Introduction and Motivation
• Problem Formulation
• Multi-objective Optimization of Query
Routing Trees
• Experimental Setup & Evaluation
• Current/Future work
Speaker: Andreas Konstantinidis – University of Cyprus
Query Routing Trees (T)
• Why Use Query Routing Trees (T)?
– Avoid Flooding the Network w/ Queries (Scalable)
• More Efficient in terms of Energy, Communication, etc.
– Better Query response quality
• An out-of-sync centralized data repository performs worse
than a “live” decentralized data repository.
– Optimally exploit short vs. long range
communication links (i.e., Bluetooth vs. WiFi|3G)
– Finally, it offers more Privacy (No single authority
has a global view of all data).
Speaker: Andreas Konstantinidis – University of Cyprus
Query Routing Tree Problem (QRTP)
Problem: Construct a Query Routing
Tree (T), for a mobile social network, that
optimizes the following three (3)
conflicting objectives, concurrently:
– Α) Minimize Overhead, in conducting the
query
– B) Maximize (Query Result) Quality.
– C) Maximize Social Interaction (i.e., exploit
interactions in the physical space)
More formal measures defined next…
Speaker: Andreas Konstantinidis – University of Cyprus
QRTP: Objective 1
• A) Minimum Overhead: a lower number
of answers, assures lower traffic load
and lower bandwidth consumption.
min Ov ( X ) | X |
Smaller Tree, Less Answers
 Lower Quality! 
 Lower Overhead 
 Neutral Interactions 
Speaker: Andreas Konstantinidis – University of Cyprus
QRTP: Objective 2
• B) Maximize Quality: higher number of
relevant answers based on interests matrix.
n
max QI ( X | Q j )   (vij | i  X , n  N , j  Ints)
i 1
Larger Tree, More Answers
 Higher Quality! 
 Higher Overhead 
 Neutral Interactions 
Speaker: Andreas Konstantinidis – University of Cyprus
QRTP: Objective 3
• C) Maximize Social Interaction: Frequency
of user interaction in physical space.
– How this can be determined? Based on Bluetooth
interactions of users in physical space
max SI ( X )   (miz | i, ( z ) X )
i
– Solution 1: few users with HIGH SI
 Lower Quality! 
 Lower Overhead 
– Solution 2: many users with HIGH SI
High Quality! 
High Overhead 
Speaker: Andreas Konstantinidis – University of Cyprus
Overview
• Introduction and Motivation
• Problem Formulation
• Multi-objective Optimization of Query
Routing Trees
• Experimental Setup & Evaluation
• Current/Future work
Speaker: Andreas Konstantinidis – University of Cyprus
Multi-Objective Optimization (MOO)
• Classical single objective optimization has the form:
max y  f ( x)
– where x is a discrete vector representing a solution (e.g. a network design, a route)
– y is a real value representing the solution quality
– f is the objective function
• Multi-Objective Optimization
f2
x
max Z  f ( x )  ( f1 ( x ), f 2 ( x ),..., f m ( x ))
where x  ( x1 , x2 ,..., xn )
– No single solution is optimal under all objectives
– Improve one deteriorates the others
– Partial ordering of solutions (“y dominates z“)
y, z  Z , y  z  i 1..m, yi  zi  j 1..m, yi  z j
y
z
PF
f1
non-dominated solutions in PF
dominated solution
– Pareto optimal set (maps to the Pareto Front (PF) )


 *  x*  X | x  X , f (x)  f (x* )
Speaker: Andreas Konstantinidis – University of Cyprus
MOO Approaches: MOEAs
EAs to MOEAs, good in obtaining a set of non-dominated solutions in a single run:
– Deal with a population
of solutions.
– Converge towards nearoptimal solutions fast.
Initialization
Selection
Main steps of EAs:
–
–
–
–
…
Objective functions
Encoding Representation
Initialization
Genetic components
…
Update Reproduction:
• Selection
• Crossover
• Mutation
…
Crossover
Mutation
…
Survival
– Update (elitism: use of archive)
Speaker: Andreas Konstantinidis – University of Cyprus
MOEA/D framework
KEY CHRACTERISTICS
•
Decomposes a MOP into a set of SOPs
using any technique for aggregating
functions:
– e.g. weighted sum, Tchebycheff:
•
Tackles them simultaneously, using
neighbourhood information and SOO
techniques.
Hybridize with local-search based
techniques.
Incorporate problem-specific knowledge.
•
•
•
Andreas Konstantinidis, Kun Yang, Qingfu Zhang and Demetrios Zeinalipour-Yazti, "A
Multi-Objective Evolutionary Algorithm for the Deployment and Power Assignment
Problem in Wireless Sensor Networks", SI-New Network Paradigms, Computer Networks,
vol. 54, pp. 960-976, 2010.
Speaker: Andreas Konstantinidis – University of Cyprus
QRTP Operation Summary
Speaker: Andreas Konstantinidis – University of Cyprus
Overview
• Introduction and Motivation
• Problem Formulation
• Multi-objective Optimization of Query
Routing Trees
• Experimental Setup & Evaluation
• Current/Future work
Speaker: Andreas Konstantinidis – University of Cyprus
Experimental Setup
– Simulator: We have implemented a tracedriven simulator in Java (a good starting point
for evaluating ideas at a preliminary stage)
– Datasets: Synthetic based on Random
Distributions (for Social Interaction and
Interest Matrix)
– Query-By-Example:
• SELECT IP, Filename
• FROM MobileSocialNetwork
• WHERE similar(multimedia-object)
– Evaluation Metrics: Next Slide
Speaker: Andreas Konstantinidis – University of Cyprus
Performance Metrics
Evaluation metrics
– Quality & diversity of solutions (using five metrics).
– Bandwidth cost BW(X): the product of n ≤ N in
tree X and the number of fragmented packets f of
size MTU for data of a particular type (e.g. video,
image, email) and size l:
– Latency L(X): the sum of the information of size
f×MTU, transferred per node over a specific
wireless network (e.g. WiFi) with a data rate DR:
where f = l/(MTU −hd) and hd is the TCP/IP header size.
Speaker: Andreas Konstantinidis – University of Cyprus
Results & Discussion
• MOEA/D vs NSGA-II
•
•
•
Higher Quality of QRTs
Higher number of Non-dominated Solutions
Better Diversity
NSGA-II the state-of-the-art in MOEAs based on Pareto dominance.
Pairs of two objective are used.
Similar conclusions for the third objective.
Speaker: Andreas Konstantinidis – University of Cyprus
Results & Discussion
• Bandwidth Consumed during Searches
A) Agnostic Approach: Search by flooding.
B) Informed Approach: Search over Optimal QRT.
180MB
50GB
Standard
Deviation
is low
20MB
7GB
Speaker: Andreas Konstantinidis – University of Cyprus
Overview
• Introduction and Motivation
• Problem Formulation
• Multi-objective Optimization of Query
Routing Trees
• Experimental Setup & Evaluation
• Conclusions and Future work
Speaker: Andreas Konstantinidis – University of Cyprus
Conclusions and Future Work
• Mobile Social Networks are a new area with
many new opportunities.
• In the future we aim to:
– Deploy more realistic mobility models (GEOLife
GPS Trajectories by Microsoft Asia).
– Real implementation using Android technology.
– Use realistic data sets for generating the interests
matrix (currently working on DBLP dataset).
– Evaluate the time cost for solving the QRT problem
on larger-scale information spaces.
Speaker: Andreas Konstantinidis – University of Cyprus
Socially-aware Query Routing in Mobile
Networks
Thank you!
Questions?
Andreas Konstantinidis
University of Cyprus
[email protected]
Speaker: Andreas Konstantinidis – University of Cyprus