Transcript Work Items - Department of Computer Science

Processing Monitoring Queries on
Mobile Objects
CS461 Lecture
Department of Computer Science
Iowa State University
What is a mobile database?
• A mobile database is a set of mobile devices
- Centralized: there exists a central server with
which each mobile device can communicate
- Decentralized: these devices form a network by
themselves
- Mobile ad hoc network (MANET)
- Mesh networks
Characteristics
• Large number of mobile objects
• Continuous movement of mobile objects
- Limited battery power
- Limited communication bandwidth
Processing Range-Monitoring Query
• What is range-monitoring query?
– Retrieve mobile objects in a spatial region, and
– continuously monitor the population in the area
Range-Monitoring Queries
Q2
a
d
Q1
c
f
b
e
Range-Monitoring Queries
Q2
a
d
Q1
c
f
b
e
Some Potential Applications
• Tourist guiding
• Automatic traffic control
• Digital battlefield vehicle tracking
• Wild animal tracking
Research Issues
• How to minimize location updates?
– Excessive mobile communication could drain
battery power quickly
• How to minimize server processing cost?
– Query results keep changing
Related Works
• Location Estimation
[Woflson98, Woflson99, etc.]
• Trajectory Indexing
[Kollios99, Saltenis00, etc.]
• Safe Region Approach
[Prabhakar00, Prabhakar01]
Safe Regions
Rectangular
Safe Region
Q1
Q2
a
Q5
Q3
Q4
Circular
Safe Region
Problems with Safe Regions
• Computing a safe region takes from
O(n) to O(n log3 n)
• Adding a new query requires to recompute safe regions for all objects
Challenge
How to provide
– accurate query results, and
– real-time updates?
Proposed: Monitoring-Query Management
Q1
Q6
Q3
Q2
a
Q5
Q7
Q4
Resident Domain
Computing a Resident Domain
• Given an object’s position P and its
processing capability N, its resident
domain should
– contain position P, and
– be as large as possible, but
– contain no more than N queries
Domain and Query Decomposition
Q1
R1
Q2
R21
Q3
Q4
R22
R31
R41
R42
Domain and Query Decomposition
Q1
R1
Q2
Q3
Q4
R41
R42
R21
R22
a
R31
Domain and Query Decomposition
Q1
R1
Q2
Q3
Q4
R41
R42
R21
R22
a
R31
Domain Tree (D-tree)
D
D
domain node
data node
Domain Tree (D-tree)
D
d1
d2
d1
d2
Domain Tree (D-tree)
D
d21
d1
d22
d1
d2
d21
d22
Number of messages sent by mobile objects (millions)
Mobile Communication Cost
30
25
20
Safe Region
MQM
15
10
5
0
10
20
30
40
50
60
70
80
90
Number of monitoring queries (thousands)
100
Number of index nodes accessed (millions)
Server Processing Cost
1000
100
Safe Region
MQM
10
1
0.1
10
20
30
40
50
60
70
80
90
Number of monitoring queries (thousands)
100
Significant and Impact of MQM
• MQM is the first scalable technique, in
terms of mobile communication and server
processing costs, for real-time rangemonitoring query management
Questions
• Any other types of queries?
• Can any type of queries be converted
into one or a number of range
monitoring query?