Transcript Querying Sensor Data in Smartphone Networks

Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Crowdsourcing Urban Data
with Smartphones
Demetrios Zeinalipour-Yazti
Data Management Systems Laboratory
Department of Computer Science
University of Cyprus
http://www.cs.ucy.ac.cy/~dzeina/
Invited Talk at the Mining Urban Data (MUD) Workshop
(with EDBT/ICDT), Athens, Greece, March 28, 2014
www.insight-ict.eu/mud
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Talk Objective
•
•
•
To review some primitive web crowdsourcing
concepts and challenges.
To show how these challenges emerge and
evolve in Urban Data Collection spaces.
To present some of our own developments
related to: i) Location Data; ii) Data Collection
Testbeds, and iii) Social Data and discuss
particular challenges and future work.
–
–
Much of the discussion is work in progress (how we
plan to apply the ideas in urban spaces).
IEEE MDM’13 Tutorial:
"Crowdsourcing for Mobile Data Management", G. Chatzimilioudis and D.
Zeinalipour-Yazti, "Proceedings of the 14th International Conference on Mobile
Data Management" (MDM '13), Milan Italy, Volume 2, Pages: 3-4, 2013.
2/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Crowdsourcing Definitions
•
Crowdsourcing = Crowd + Outsourcing
–
•
Jeff Howe (2006). "The Rise of Crowdsourcing". Wired.
From our recent work:
– Crowdsourcing refers to a distributed problemsolving model in which a crowd of undefined
size is engaged in the task of solving a
complex problem through an open call for
monetary or ethical benefit.
“Crowdsourcing with Smartphones”, Georgios Chatzimiloudis,
Andreas Konstantinidis, Christos Laoudias, Demetrios
Zeinalipour-Yazti, IEEE Internet Computing, Special Issue:
Sep/Oct 2012 - Crowdsourcing, May 2012. IEEE Press, Volume
16, Pages: 36-44, 2012.
3/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Web Crowdsourcing
Open Call (Task)
Solutions
Requester
(Crowdsourcer)
Rewards
Workers
Platform
(Solvers)
4/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Web Crowdsourcing
Microtasking Platform:
Qualifications
b) Redundancy: Each worker solves a Hit once (3-5
assignment per hit) to enable majority voting
a) Reward
5/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Web Crowdsourcing: Incentives
• Tangible (Monetary) Incentives
– Cash, Credit or Gifts (MTurk, Kickstarter)
– Unintended or as-a-by-product (reCaptchas)
• Ethical Incentives
– Socialize & Fun
– Earn Prestige
– Altruism
– Learn something New
• Usually a combination of several
incentives
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
6/50
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Web Crowdsourcing: Challenges
•
•
•
•
•
•
•
How to Recruit Contributors (randomly,
marketplaces?) / What the Contributors Can Do
(qualifications, tests)?
How to Combine their Contributions?
How to Manage Abuse?
How To Scale/Manage Complex/Larger Tasks?
Openness / Quality?
Disclosure Issues (Privacy related to Tasks,
NDAs?)
Minimum Wages & Social Contributions?
Anhai Doan, Raghu Ramakrishnan, and Alon Y. Halevy. 2011. Crowdsourcing systems on
the World-Wide Web. Commun. ACM 54, 4 (April 2011), 86-96.
7/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Declarative Crowdsourcing
• CrowdDB, Qurk, Deco, MoDaS, Crowdforge.
SELECT abstract
FROM talk
WHERE title = "CrowdDB
Crowd
Extensions
CrowdDB: Answering Queries with Crowdsourcing,M. J. Franklin, D. Kossmann
,T. Kraska, S. Ramesh, R. Xin, SIGMOD‘11 & VLDB'11Demo
8/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Mobile Crowdsourcing
•
txtEagle (now JANA) founded by Nathan Eagle
(PhD, MIT, 2005) a first-of-a-kind mobile CS system:
–
–
Requesters: can assign small tasks (translation,
transcription and surveys) on their mobile phones.
Workers (today 3.48 Billion Workers in 102 countries!): :
rewarded with airtime on their mobile subscriber accounts
or MPESA (mobile money described next).
txteagle: Mobile Crowdsourcing, Internationalization, Design and
Global Development, LNCS Volume 5623, pp 447-456, 2009.
9/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Mobile Crowdsourcing
•
Another app txtEagle SMS Bloodbank :
– Idea: to report blood levels of local hospitals centrally
by nurses.
– Initially, in the absence of an incentive, the system
was a complete failure.
– In summer 2007, automatic airtime credit was
incorporated to award nurses for their contribution =>
then a huge success!
• Other txtEagle SMS applications:
–
–
–
Transcription mentioned previously (global market $18B in
2010)
Software Localization (60 local languages in Kenya, txtEagle
generated a cookbook
Citizen Journalism, Sentiment Analysis, Surveys
10/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
The Smartphone Era
April 2013: Beginning of Smartphone Era!
• In April, 2013, for the first time in history
the number of Worldwide Smartphone
sales exceeded that of feature phones
(according to IDC)
–
–
•
51.6% were Smartphones (216M units)
48.4% were Feature Phones (186M units)
The bulk of mobile phones are acquired in
the developing world (e.g., China, India,
Africa etc.)
–
Chinese manufactures (ZTE, Huawei) started
building smartphones for the wide markets.
More Smartphones Were Shipped in Q1 2013 Than Feature Phones, An Industry First According
to IDC, 25 Apr 2013, http://www.idc.com/getdoc.jsp?containerId=prUS24085413
11/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
location-based
efficiently
calculating
the k nearest
neighbors of
forCyprus,
each
Dagstuhlinteraction
Seminar by
10042,
Demetris
Zeinalipour,
University
y, time and recall of search in a mobile social community for objects generated by a
eployed on SmartLab, a novel cloud of 40+ Android devices deployed at University of
research and development of applications on smartphones at a massive scale.
26/1/2010
Crowdsourcing with Smartphones
•
A smartphone crowd is constantly moving and
sensing providing large amounts of
opportunistic data enabling new applications
solving model
ed to solve a
ure 1). Crowdile workforce,
l of this new
smartphones’
tphones are in
nected. Thereexisting webr contributing
sent. Furthern, light, movesmartphones,
ortunistic data
12/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Smartphone Crowdsourcing: Challenges
Challenges (Beyond Web Crowdsourcing)
1. Big Data
–
Velocity by sensor data generates Volume
2. Typing and User Interfaces
–
–
Participatory typing is cumbersome due to small
form factor / display keyboard.
Scrolling & Crowded GUIs. Attention issues due to
possible mobility. Opportunistic Solutions?
3. (Location) Privacy
–
Coarse-grain (cell, wifi) vs. fine (gps)
4. Energy Consumption
–
Power Hungry (GPS, Brightness, etc.)
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
13/50
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Smartphone Crowdsourcing: Challenges
Challenges (Beyond Web Crowdsourcing)
5. Calibration and Multi-device Issues
–
–
Different readings by different sensors (e.g., Wifi
RSS, magnetic field, etc.)
Incomplete Data & Quality Issues.
6. Connectivity Issues
–
Workforce might have intermittent connectivity (e.g.,
while travelling) thus can’t provide online readings.
7. Heterogeneous Clients hinders deployment
–
–
Different OSes, sensor, features, APIs, etc.
One supports active background tasks another OS
doesn’t, etc.
14/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Talk Outline
• Introduction & Challenges
• Urban Location Data
– Anyplace Indoor Information System
• Urban Sensing Testbeds
– SmartLab Smartphone Programming Cloud
• Urban Trajectory Search
– SmartTrace Query Processing Framework
• Urban Social Networks
– Rayzit Crowd Messaging Service
15/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Location Data
•
•
•
•
People spend 80-90% of their time inside buildings,
while 70% of cellular calls and 80% of data connections
originate from indoors.
GPS has low availability indoors due to the blockage
or attenuation of the satellite signals but it is also very
power hungry.
Smartphones can nowadays localize off-the-shelf with
onboard sensors and WiFi signal fingerprints (coined
Hybrid Localization)
New Applications:
–
–
–
–
In-building Navigation (Malls, Airports, Museums, Schools, etc.)
Asset Tracking and Inventory Management (Hospitals, etc)
Elderly support for Ambient and Assisted Living (AAL)
Augmented Reality (Firefighters), Social Networking, etc.
16/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Location Data
•
Indoor Localization using proprietary
infrastructure: Infrared, Bluetooth, Visual or
Acoustic Analysis, RFID, Ultra-Wide-Band,
Wireless Sensor Network, Inertial
Measurement Units (IMU), Wireless LAN.
Smartphone Localization:
•
•
Hybrid Localization: Combination of more than 1
techniques such as IMU+WiFi (acceler., gyro, digital
compass) MapMatching, Magnetic Data, pedometer
17/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Location Data
I can see these
Reference Points,
where am I?
Cellular
WiFi
(x,y)!
...
Cellular
RadioMap
Service
User u
18/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Location Data
•
References
–
–
–
–
[Airplace] "The Airplace Indoor Positioning
Platform for Android Smartphones", C.
Laoudias et. al., Best Demo Award at IEEE
MDM'12. (Open Source!)
[HybridCywee] "Demo: the airplace indoor
positioning platform", C.-L. Li, C. Laoudias,
G. Larkou, Y.-K. Tsai, D. Zeinalipour-Yazti
and C. G. Panayiotou, in ACM Mobisys'13.
Video at: http://youtu.be/DyvQLSuI00I
[UcyCywee] IPSN’14 Indoor Localization
Competition (Microsoft Research), Berlin,
Germany, April 13-14, 2014.
[Anyplace] Crowdsourced Indoor
Localization and Navigation with Anyplace,
In ACM/IEEE IPSN’14.
http://anyplace.cs.ucy.ac.cy/
Cywee / Airplace
19/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Location Data
Anyplace Architecture
Navigator
Viewer, Widget
20/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Location Data
•
Anyplace Indoor Information Service (IIS)
http://anyplace.cs.ucy.ac.cy/
Live Demo!
21/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Anyplace Crowdsourcing Challenges
• A) Big Data
– Massively process RSS log
traces to generate a valuable
Radiomap
•
Utilized for KNN positioning
– Processing current logs in
Anyplace for a single building
might take several minutes!
– Challenges in MapReduce:
• Spatio-temporal Analysis
• Missing Values / Outliers /
Quality / Multi-device Issues
(see next)
22/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Anyplace Crowdsourcing Challenges
• B) Quality: Unreliable
Crowdsourcers, Multidevice Issues, Hardwar
Outliers, Temporal
Decay, etc.
– Remark: There is a
Linear Relation between
RSS values of devices.
– Challenge: Can we
exploit this to align
reported RSS values?
"Crowdsourced Indoor Localization for Diverse Devices through Radiomap Fusion", C. Laoudias, D.
Zeinalipour-Yazti and C. G. Panayiotou, "Proceedings of the 4th Intl. Conference on Indoor
Positioning and Indoor Navigation" (IPIN '13), Montbeliard-Belfort France, 2013.
23/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Anyplace Crowdsourcing Challenges
• C) Privacy
– Challenge: How to localize using a Radiomap
Service, without revealing my location to the service?
– Solution (ongoing): We developed a spatio-temporal
privacy scheme using bloom filters coined Temporal
Vector Map (TVM).
•
•
–
–
Provides k-anonymity guarantees
Enables both snapshot and continuous localization.
"Towards planet-scale localization on smartphones with a partial
radiomap", A. Konstantinidis, G. Chatzimilioudis, C. Laoudias, S. Nicolaou and
D. Zeinalipour-Yazti, ACM HotPlanet '12.
“Privacy-Preserving Indoor Localization on Smartphones with VectorMap”,
A. Konstantinidis, P. Mpeis, N. Pelekis, D. Zeinalipour-Yazti and Y. Theodoridis,
under submission.
24/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Anyplace Crowdsourcing Challenges
TVM Outline:
Bloom Filter (u's APs)
WiFi
K=3
Positions
...
WiFi
RadioMap
(server-side)
User u
25/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Anyplace Crowdsourcing Challenges
26/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Talk Outline
• Introduction & Challenges
• Urban Location Data
– Anyplace Indoor Information System
• Urban Sensing Testbeds
– SmartLab Smartphone Programming Cloud
• Urban Trajectory Search
– SmartTrace Query Processing Framework
• Urban Social Networks
– Rayzit Crowd Messaging Service
27/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Sensing
•
•
•
Use sensors in urban environments in support
of more classic environmental sensing
applications.
"People sense and contribute data about their
surroundings using mobile devices" (Kanhere)
Example Projects:
–
–
–
–
Dartmouth | Metrosense: SoundSense, CenceMe,
Sensor Sharing, BikeNet, AnonySense, and Second
Life Sensor.
MIT | Cartel: VTrack/CTrack, PotHole
Harvard : Citysense (grew out of MoteLab)
UNSW: Noise (Earphone) & Air pollution
28/50
(HazeWatch, CommonSense),
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Sensing
• Monitoring Urban Spaces
NoiseMap
"Ear-Phone: An End-to-End Participatory Urban Noise Mapping System " Rajib Rana, Chun
Tung Chou, Salil Kanhere, Nirupama Bulusu, and Wen Hu. In ACM/IEEE IPSN 10, SPOTS
Track, Stockholm, Sweden, April 2010.
29/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Sensing
• This kind of a paradigm has
nowadays an industrial
success.
• CrowdSensing app by Waze
(Israel) now Google!
• Waze: Free GPS Navigation
with Turn by Turn
– Workers report their GPS
location and events (gas prices,
traffic jams, etc.)
– Real-time updates to users
31/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Testbeds
•
Smartphone Testbeds: Allow the requestor
to deploy a task (app, data collection,
remote terminal etc.) directly on the end
smartphone devices.
–
–
–
–
–
[PRISM] T. Das, P. Mohan, V.N. Padmanabhan, R. Ramjee, and A.
Sharma, “PRISM: Platform for Remote Sensing using Smartphones”, In
ACM MobiSys’10.
[CrowdLab] E. Cuervo, P. Gilbert, B. Wu, and L.P. Cox, “CrowdLab: An
Architecture for Volunteer Mobile Testbeds”, In COMSNETS’11.
[PhoneLab] G. Challen et. al. “PhoneLab: A Large-Scale Participatory
Smartphone Testbed”, In USENIX NSDI’12 (poster).
[SmartLabDemo] "Demo: a programming cloud of smartphones", A.
Konstantinidis, C. Costa, G. Larkou, D. Zeinalipour-Yazti, In ACM Mobisys
'12.
[SmartLab] "Managing Smartphone Testbeds with SmartLab", G. Larkou,
C. Costa, P. Andreou, A. Konstantinidis, D. Zeinalipour-Yazti, In 27th
USENIX LISA '13, Washington D.C. USA, 115-132, 2013.
32/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Sensing TestBeds
•
PhoneLab: a Participatory SmartPhone Sensing
Testbed (People-Centric Testbed)
200 Nexus S 4G phones used by Students and
Faculty Members at the Univ. of Buffalo
•
•
•
Incentive: Free Sprint Phone for 1st year. After that, only
$44.23/month for an unlimited plan (claimed to be better than
competition)
Targeted for Data Collection Scenarios (not fine-grain
access like SmartLab)
–
–
Each Data Collection task need to undergo an Institutional
Review Board process (similar to other projects touching
ethical issues)
Data Collection: Workers (Students) have to bring in their
smartphones to have the app installed + data collected.
[PhoneLab] G. Challen et. al. “PhoneLab: A Large-Scale Participatory Smartphone
Testbed”, In USENIX NSDI’12 (poster).
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
33/50
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Sensing Testbeds
• We developed a comprehensive architecture for
managing smartphones through a web browser.
• SmartLab (http://smartlab.cs.ucy.ac.cy/):
– 40+ Android Devices, Real Sensors, Real Computing Stack
– Different Connection Modalities: 3G (unlimited 3G bancwidth
by MTN Telecom), Wifi, Wired, Remote
Static Androids
Mobile Androids
34/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Sensing Testbeds
SmartLab (http://smartlab.cs.ucy.ac.cy/)
Rent
Manage
See/Click
Shell
File Sys.
Automation
Debug
Data
Live Demo!
35/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Sensing Testbeds
Scenario I: Data Collection in Smart Cities
– How to handle a fleet of Android-powered
entertainment equipment installed on 1000
buses?
– How to manage a city-scale infrastructure
comprising of low-power, low-value Androidoriented devices (installed on traffic lights, etc.)
– How to manage a city-scale SETI-like
computational cluster comprising of
Smartphones.
• We tend to change smartphones faster than PCs …
36/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Sensing Testbeds
Scenario II: Application Testing (Mockup Studies)
– How to test my app automatically on N different
smartphones scattered around in a city?
Mockup Sensors
• GPS mockup
• Accelerometer sensor
• Compass sensor
• Orientation sensor
•Temperature sensor
• Light sensor
• Proximity sensor
• Pressure sensor
• Gravity sensor
37/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Sensing Testbeds
Scenario III: Personal Gadget Management
– How to manage my personal gadgets at a finegrain (i.e., clicks, file-transfer, update, etc.)
Smart
Watches
Tablets
Smart Glasses
eReaders
SmartBooks
Smart Home
Phones
Smart TVs
Rasperry PI
38/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Talk Outline
• Introduction & Challenges
• Urban Location Data
– Anyplace Indoor Information System
• Urban Sensing Testbeds
– SmartLab Smartphone Programming Cloud
• Urban Trajectory Search
– SmartTrace Query Processing Framework
• Urban Social Networks
– Rayzit Crowd Messaging Service
39/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Trajectory Search
Fact:
Smartphones can collect positional (x,y) in a power
efficient manner (e.g., iPhone triangulated log file,
Android Geolocation wardriving).
Crowdsourcing Incentive:
Contribute to the resolution of queries for Social Benefit
(without revealing traces).
Applications:
•
•
•
Intelligent Transportation Systems: “Find whether a new bus
route is similar to the trajectories of K other users.”
Social Networks: “Find if there is an evening cycling route from
MOMA to the Julliard”
GeoLife, GPS-Waypoints, Sharemyroutes, etc. offer centralized
counterparts.
40/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Trajectory Search
•
Problem: Compare a query with all distributed
trajectories and return the k most similar
trajectories to the query.
•
Similarity between two objects A, B is associated
with a distance function.
Distance
D = 7.3
?
D = 10.2
K
D = 11.8
Query
D = 17
D = 22
41/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Trajectory Search
•
•
•
An intelligent top-K processing algorithm for
identifying the K most similar trajectories to Q
in a distributed environment.
Step A: Conduct an inexpensive lineartime LCSS(MBEQ,Ai) computation on the
smartphones to approximate the answer.
Step B: Exploit the approximation to
identify the correct answer by iteratively
asking specific nodes to conduct
LCSS(Q, Ai).
•"Crowdsourced Trace Similarity with Smartphones", Demetrios Zeinalipour-Yazti and
Christos Laoudias and Constandinos Costa and Michail Vlachos and Maria I. Andreou
and Dimitrios Gunopulos, IEEE TKDE, Vol. 25, 1240-1253, 2013.
• "SmartTrace: Finding similar trajectories in smartphone networks without disclosing the
traces", Costa et al., IEEE ICDE'11.
42/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Trajectory Search
SmartTrace for Android (open source)!
http://smarttrace.cs.ucy.ac.cy/
Query Q
Device B
Device C
43/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Trajectory Search
Answer
Privacy
Setting
Answer
With Trace
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
44/50
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Talk Outline
• Introduction & Challenges
• Urban Location Data
– Anyplace Indoor Information System
• Urban Sensing Testbeds
– SmartLab Smartphone Programming Cloud
• Urban Trajectory Search
– SmartTrace Query Processing Framework
• Urban Social Networks
– Rayzit Crowd Messaging Service
45/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Social (Crowd) Networks
• Social Media (Facebook, Linked-in, … ) utilize a
Social Graph (friendship, follower, followee) to
map the relationships between users.
• Social Media in Urban Settings: Issues
– Urban Applications many times require locationbased rather than social-based interactions, e.g.,
• Inform my neighboring drivers about an accident (e.g., in
Waze).
• Inform people in a city about an event.
– Location-based services suffer from bootstrapping
• e.g., Check in to Foursquare and find nobody else there
– Interacting with the Crowd, calls for stronger Privacy!
46/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Social (Crowd) Networks
• We developed Rayzit for Windows Phone after
receiving an Industrial Award by the Appcampus
Program (Microsoft, Nokia & Aalto, Finland).
– Ranked among the 5 best apps of the given program
among 3500 submissions.
– A few thousand downloads and active users on our
big-data backend.
47/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Urban Social (Crowd) Networks
Find 2 Closest Neighbors for ALL User
"Continuous all k-nearest neighbor querying in smartphone networks", Georgios Chatzimilioudis,
Demetrios Zeinalipour-Yazti, Wang-Chien Lee, Marios D. Dikaiakos, In IEEE MDM'12.
48/50
© Demetrios Zeinalipour-Yazti, Mining Urban Data, EDBT’14, Athens, Greece
Dagstuhl Seminar 10042, Demetris Zeinalipour, University of Cyprus, 26/1/2010
Crowdsourcing Urban Data
with Smartphones
Demetrios Zeinalipour-Yazti
Data Management Systems Laboratory
Department of Computer Science
University of Cyprus
Thanks!
Questions?
http://www.cs.ucy.ac.cy/~dzeina/
Invited Talk at the Mining Urban Data (MUD) Workshop
(with EDBT/ICDT), Athens, Greece, March 28, 2014
www.insight-ict.eu/mud