New Perspectives in
Social Data Management
Sihem Amer-Yahia
Research Director
CNRS @ LIG
Sihem.Amer-Yahia@imag.fr
TSUKUBA University
May 20th, 2014

Traditional data management stack
Application Layer
High-level specification
Logical Layer
Logical and physicaloptimizations
Physical Layer
Index creation
relational tables++native XML backend

TSUKUBA Univ. – May 2014Collaborative data model
Item space(with attributes)

User space(with attributes)
boolean, rating, tag,sentiment…

Item 1

user1

Item 2user2

Item 3user3

Item 4Item 5user4

Item 6
user5

Item 7User6

TSUKUBA Univ. – May 2014

Let’s examine a canonical social
application

Extracting travel itineraries from Flickr

Goal: extract the itinerary of each traveler by mapping
photos into Points Of Interest (POIs) and aggregate actionsof many travelers into coherent queryable itineraries

Automatic construction of travel itineraries using social breadcrumbs: with Munmun De Choudhury(Arizona State University), Moran Feldman (Technion), Nadav Golbandi, Ronny Lempel (Yahoo!
Research), Cong Yu (Google Research). HyperText Conference 2010
Interactive Itinerary Planning: with Senjuti Basu Roy (Univ. of Washington), Gautam Das (Univ. ofTexas at Arlington), Cong Yu (Google Research). ICDE 2011
Deployed on Yahoo! Mobile
TSUKUBA Univ. – May 2014

Photo	  Streams	  Photo-­‐POI	  Mapping	  •••Iden%fy	  photos	  of	  a	  given	  city	  Filter	  out	  residents	  of	  a	  city	  Validate	  photo	  %mestamps	  •Extract	  Candidate	  POIs	  oo•Tag	  &	  geo-­‐based	  POI	  associa%on	  •Photo	  Streams	  Segmenta%on	  	  oTimed	  Paths	  Lonely	  Planet/Y!	  Travel	  to	  extract	  landmarks	  Yahoo!	  Maps	  API	  to	  retrieve	  their	  geo-­‐
loca%ons	  Split	  the	  stream	  whenever	  the	  %me	  diﬀerence	  between	  two	  successive	  photos	  is	  “large”	  • Dis%lla%on	  of	  Timed	  Visits	  •<POI,	  start	  %me,	  end	  %me>	  • Construc%on	  of	  Timed	  Paths	  o
TSUKUBA Univ. – May 2014A	  sequence	  of	  Timed	  Visits	  Problem definition•Definitions– Each itinerary is a timed path
– The set of timed paths implies a weighted graph G over POIs
– An itinerary is a path in the graph G– The value of an itinerary is the sum of popularities of its POIs
– The time of an itinerary is the sum of POI visit and transit times•

Problem Instance (“Orienteering”)– Find an itinerary in G from a source POI to a target POI of budget (=time) atmost B maximizing total value– The time budget B is typically whole days
– source and target POIs provided by user (e.g. hotel)

TSUKUBA Univ. – May 2014

Example	  i*nerary	  for	  NYC	  (single-­‐day)	  TSUKUBA Univ. – May 2014

Social data management stack
Application evaluation
Application logic
Search and Recommendation
Social Analytics
Data preparation

raw data
TSUKUBA Univ. – May 2014

Architecture of a typical Data Mining system

Graphical user interface

Pattern evaluation

Data cleaning &Data mining engine

data integration

Filtering
Knowledge-baseDatabase

DataWarehouse

TSUKUBA Univ. – May 2014

Architecture of a typical Data Mining system

TSUKUBA Univ. – May 2014

SOCLE: A framework for social data preparation
with N. Ibrahim, C. Kamdem-Kengne, F. Uliana, M.C. Rousset
submitted for publication•

Examined typical social applications: URL recommendation in Delicious,
group recommendation in MovieLens, social analytics on Twitter, itinerary
extraction in Flickr– Data Collection• mapping data into <u,i,label> triples– Data Sanitation• Pruning: cut long tails of user actions, remove photos taken by residents –in delicious, removing URLs tagged with less than 5 tags reduces input data to 27% of
input size

• Text processing: topic extraction• Normalization: of ratings– in MovieLens, critics are more moderate than less-active
reviewers• Enrichment: POI-to-photo association, named entity extraction, twitter
vocabulary expansion (e.g., using Yahoo! Boss interface), sentiment analysis– Data Transformation• from <u,i,label> to <u,i,label> and <u,{(v,w)}> …

TSUKUBA Univ. – May 2014

Search & Recommendation
output<u, i, label>Social Analytics<u, {(v,w)}>

Data Transformation
User Similarity
Functions

NetworkConstruction
Functions

IndexGeneration<u, i, label>

Data Sanitation
Pruning

Text Processing

Normalization

Enrichment<u, i, label>

Data Collectionrawsocialdata<u, i, label>
TSUKUBA Univ. – May 2014

Data Preparation

SOCLE model– Which data model? an extensible type system– Which storage model?

TSUKUBA Univ. – May 2014

SOCLE model and algebrawith L. Lakshmanan and C. Yu
SocialScope: Enabling Information Discovery on Social Content Sites
at CIDR 2009

Enrich a node with attributes -> new node type
• Algebra operator : γNC,d,att,A(G){id=10;Name=Paris;
Type=destination}

L12 = {id=30, type=visit, ..}L13 = {id=31, type=visit, ..}L14 = {id=32, type=visit, ..}n2n3 {id=11;
Name=Grenoble;

L12

Type=destination}

L13n4

L14{id=15;
Name=Pekin;
Type=destination}TSUKUBA Univ. – May 2014n1

{id=101;Name=John;
Type=user,traveler,
Vst={Paris, Grenoble, Pekin}}Storage Model: native or relational++?

TSUKUBA Univ. – May 2014

SOCLE algebra– Examine how existing algebras/languages for querying social
data can be used for data preparation– Properties• Declarativity• Expressivity and closure• Provenance• Invertibility

TSUKUBA Univ. – May 2014

What makes SDM different from DM?
• SDM needs a different data management stack: datapreparation• In social computing, analysts do not always know whatto look for• In social computing, application output must beevaluatedTSUKUBA Univ. – May 2014

Social data exploration instances• Since analysts do not know what to look for, let’s
examine some social data exploration instances– Rating exploration
MRI: Meaningful Interpretations of collaborative Ratings
with M. Das, S. Thirumuruganathan, G. Das (UT Arlington), C. Yu (Google)
at VLDB 2011

– Tag exploration
Who tags what? An analysis frameworkwith M. Das, S. Thirumuruganathan, G. Das (UT Arlington), C. Yu (Google)
at VLDB 2012

– Temporal explorationEfficient sentiment correlation for Large-scale Demographics
with M. Tsytsarau and T. Palpanas (Univ. of Trento)
at SIGMOD 2013
TSUKUBA Univ. – May 2014

Rating exploration

Collaborative rating model• Rating tuple: <item attributes, user attributes, rating>
ID

Title

Genre

Director

Name

GenderLocation

Rating1

Titanic

Drama

James
CameronAmyFemale

New York

8.5

2

Schindlerʼs ListDrama

StevenSpeilberg

John

MaleNew York

7.0

• Group: a set of ratings describable by a set of attributevalues– Based on data cubes in OLAP (for mining multidimensional data)TSUKUBA Univ. – May 2014

Exploration space
Each node/data cube/cuboid in lattice is a group
Example group:
Gender: MaleAge: Young
Location: CA
Occupation: Student

Partial Rating Lattice for a Movie(M:Male, Y:Young, CA:California, S:Student)

TSUKUBA Univ. – May 2014

Task
Quickly identify“good” groups in thelattice that help users
understand ratingseffectively

TSUKUBA Univ. – May 2014

DEM: Meaningful Description Mining•

For an input item covering RI ratings, return set C of cuboids, s.t.:– description error• |C| ≤ k;
• coverageis minimized, subject to:≥ α	Description Error: how well a cuboid average rating approximates
the numerical score of each individual rating belonging to it

Coverage: percentage of ratings covered by the returned cuboids

TSUKUBA Univ. – May 2014

DEM: Meaningful Description Mining
Identify groups of reviewers who consistently share similar ratings onitems

TSUKUBA Univ. – May 2014

DEM: Meaningful Description Mining

To verify NP-completeness, we reduce the Exact 3-Set Cover problem(EC3) to the decision version of our problem. EC3 is the problem offinding an exact cover for a finite set U, where each of the subsets
available for use contain exactly 3 elements.

TSUKUBA Univ. – May 2014

DEM Algorithms•Exact Algorithm (E-DEM)– Brute-force enumerating all possible combinations of cuboids inlattice to return the exact (i.e., optimal) set as rating descriptions•

Random Restart Hill Climbing Algorithm– Often fails to satisfy Coverage constraint; Large number of restarts
required– Need an algorithm that optimizes both Coverage and Description
Error constraints simultaneously•

Randomized Hill Exploration Algorithm (RHE-DEM)

TSUKUBA Univ. – May 2014

RHE-DEM Algorithm
Satisfy Coverage
Minimize Error

C= {Male, Student}{California, Student}

Figure: Partial Rating Lattice for a Movie; k=2, α=80%(M:Male, Y:Young, CA:California, S:Student)
TSUKUBA Univ. – May 2014

RHE-DEM Algorithm
Satisfy Coverage
Minimize Error

C= {Male, Student}{California, Student}
Say, C does not satisfy
Coverage Constraint

Figure: Partial Rating Lattice for a Movie; k=2, α=80%(M:Male, Y:Young, CA:California, S:Student)
TSUKUBA Univ. – May 2014

RHE-DEM Algorithm
Satisfy Coverage
Minimize Error

C= {Male, Student}{California, Student}

C= {Male}{California,Student}

C= {Student}{California,Student}

Figure: Partial Rating Lattice for a Movie; k=2, α=80%(M:Male, Y:Young, CA:California, S:Student)
TSUKUBA Univ. – May 2014

RHE-DEM Algorithm
Satisfy Coverage √Minimize Error

C= {Male}{California, Student}
Say, C satisfies
Coverage Constraint

Figure: Partial Rating Lattice for a Movie; k=2, α=80%(M:Male, Y:Young, CA:California, S:Student)
TSUKUBA Univ. – May 2014

RHE-DEM Algorithm
Satisfy Coverage √Minimize Error

C= {Male}{California, Student}

Figure: Partial Rating Lattice for a Movie; k=2, α=80%(M:Male, Y:Young, CA:California, S:Student)
TSUKUBA Univ. – May 2014

RHE-DEM Algorithm
Satisfy Coverage √Minimize Error

C= {Male}{California, Student}

Figure: Partial Rating Lattice for a Movie; k=2, α=80%(M:Male, Y:Young, CA:California, S:Student)
TSUKUBA Univ. – May 2014

RHE-DEM Algorithm
Satisfy Coverage √Minimize Error√

C= {Male}{Student}

Figure: Partial Rating Lattice for a Movie; k=2, α=80%(M:Male, Y:Young, CA:California, S:Student)
TSUKUBA Univ. – May 2014

What makes SDM different from DM?
• SDM needs a different data management stack: datapreparation• In social computing, analysts do not always know what
to look for• In social computing, application output must beevaluatedTSUKUBA Univ. – May 2014

City

#POIs

#Timed Paths Sample POIs

Barcelona

74

6,087

Museu Picasso, Plaza Reial

London163

19,052

Buckingham Palace, Churchill Museum,Tower Bridge

New YorkCity

100

3,991

Brooklyn Bridge, Ellis Island

Paris

114

10,651

Tour Eiffel, Musee du Louvre

San
Francisco80

12,308Aquarium of the Bay, Golden Gate Bridge,
Lombard Street

City

Ground Truth Sources

Barcelonawww.barcelona-tourist-guide.com

Londonwww.theoriginaltour.com

New York City

www.newyorksightseeing.com

Paris

www.carsrouges.com

San Francisco

www.allsanfranciscotours.com
TSUKUBA Univ. – May 2014

Comparative evaluation
Globalcomparison

POI quality

Transit times

TSUKUBA Univ. – May 2014

Results for side-by-side comparison

TSUKUBA Univ. – May 2014

Challenge 1:
Filtering expert AMT workers
Multi-answer questions on “less-known” POIsTSUKUBA Univ. – May 2014

Challenge 2:
How to better exploit the crowd?

Crowds, not drones: modeling human factors in crowdsourcing
with S. B. Roy (U. of Washington), G. Das, S. Thirumuruganathan (UTArlington), I. Lykourentzou (Tudor Institute and INRIA) at DBCrowd 2013
TSUKUBA Univ. – May 2014

Summary•

There are three kinds of users in SDM– End user who generates content of varying quality and demands highquality content– Analyst (data scientist and application developer) who needs a better
understanding of the underlying data and users– Worker who helps relate to end user and evaluate content utility•

Data preparation tools and efficient social exploration would helpanalysts– new opportunities for algebraic optimizations– a collection of optimization problems with data-centric or analyst-centric
goals– often a reduction of hard problems with heuristics/approximation algorithms– but also appropriate indexing•

Application validation could benefit from worker profiling andcrowd indexing
TSUKUBA Univ. – May 2014