Transcript Moving Objects Databases - Worcester Polytechnic Institute

Moving Objects
Databases
Worcester Polytechnic Institute
Worcester, MA
April 8, 2004
Presented by
Rimma Kaftanchikova
[email protected]
Where are we?
CS561
Roadmap
► Location-Based
Services
► Why this is a hot technology?
► Overview
► Moving Objects Databases
► Problems with current databases
► Solution
► MOST+FTL
► Questions
CS561
Location Based Services Categories
►
Information Services
 Identify and provide directions to the nearest restaurants, ATMs or
gas stations
 Allow travelers to obtain other information specific to their location
►
Corporate applications
 Enable enterprises to better manage mobile assets to optimize
services or cut costs
 E.g., fleet or asset tracking
►
Entertainment/Community Services
 Allow mobile users to create a localized community of people with
similar interests
 Notify a user when a group member is close-by, e.g. friend-finder
CS561
Location Based Services Categories
(cont.)
►
Mobile Commerce Services
 Help users shop or purchase goods/services from the retailer
closest to their current location.
 (Businesses can) send special offers to users in proximity to one of
their establishments.
►
Safety Related Applications
 Help public or private safety organizations find or track mobile
users in need of assistance.
 Help locate stolen property.
CS561
Location Based Services Examples
Examples:
Where is closest gas station? How do I get there?
What is the average speed on the highway 1 mile ahead?
What are the available parking slots around me?
Mobile E-Commerce
 Remind me to buy drinks when I’m close to a supermarket
 Send a coupon (10% off) to a customer with interest in Nike
sneakers that is close to the store
 Alert a person entering a bar if two of his “buddies”
(wife and girlfriend) are both in the bar;
he may want to turn around
Generally, queries involve spatial objects (e.g. points, lines, regions, polygons)
“Retrieve the objects that will intersect the polygon within 3 minutes”
“Retrieve the objects that will intersect P within 3 minutes and stay in the poly
CS561
for 1 minute, and 5 minutes later enter another polygon Q”
Why now?
► E911
– FCC mandate
► Drop
in equipment/service prices
(In 1996, the Federal Communications
Commission (FCC) mandated that all wireless carriers offer a 911 service with
the ability to pinpoint the location of callers making emergency requests)
► Portable/wearable/wireless
► Vehicular
device proliferation
communication networks (UWB, 802.11)
CS561
A spatial database
is a collection of
spatially referenced
data that acts as a
model of reality
Overview
Spatial information
A temporal database
can store and retrieve
temporal data, that is,
data which depends on
time in some way.
Temporal information
Moving objects databases
Location management
A moving objects database
represents information
about moving objects
and their location
CS561
Source: http://www.cs.uic.edu/~wolfson/html/mobile.html
Database Perspective –
how to manage and query
the data?
Problems With Current Databases
Moving Objects: “Objects whose
position changes continuously
over time”
Database Perspective – how to
manage and query the data?
Not well equipped to handle
continuously changing data
(e.g position of moving objects)
Reason: data is assumed to
be constant unless it is
explicitly modified
CS561
Problems With Current Databases
(cont.)
To represent a moving object in a
database, you have to update very
frequently the position of the
moving object
THIS IS A PROBLEM!
• Serious performance and
wireless-bandwidth overhead
• If not, the answer to queries
is outdated.
SOLUTION???
CS561
Trajectory
► Solution
represent the position as a
function of time (it changes as time passes,
even without an explicit update)
CS561
Model of a trajectory
Geometrical
representation
in 3D space
(2D spatial +
1D temporal)
The resulting line segments comprise a polyline in
3D, the trajectory of the moving point object.
CS561
Trajectory construction
Moving objects create trajectories
► Trajectory: a sequence of 2 or 3-dim locations
► Based on GPS points (x1,y1,z1,t1), (x2,y2,z2,t2),…
► “Snap” points on road network
►
Find shortest path on map between consecutive gps points
Usually we can sample the positions of the objects at periodic time intervals Dt
► Linear Interpolation: easy and usually accurate enough
► For vehicles moving on road networks, construction uses a map.
►
►
CS561
Map
►
A relation
tuple <----> block, i.e.
section of street between
two intersections
name
category
Avg
speed
one_way
……
167980
INSTITUTE RD.
A40
25
No
……
167985
HIGHLAND ST.
A40
25
No
……
167982
WEST RD.
A31
25
No
……
167981
DEAN ST.
A31
25
No
……
bid
polyline
CS561
Trajectory Reduction
► Line
simplification: approximate a
trajectory by another which is not farther
than ε.
e
e
CS561
Three Time-series Prediction
Methods
► Two
widely used methods:
 Moving Averages: the next predicted value is the
average of the latest h values of the series
 Exponential Smoothing: The next predicted value is the
weighted average of the latest h values, and the
weights decrease geometrically with the age of the
values
► Neural-Fuzzy
Inference Systems (NFIS)
 Fuzzy rule based inference +
 Neural back-propagation rule base learning
CS561
Moving Objects Spatio-Temporal
(MOST) data model
►
MOST model is designed for databases with dynamic
attributes, i.e. attributes that change continuously as a
function of time, without being explicitly updated.
►
Answer to a query depends on:
 Database content
 Time at which the query entered
►
Advantage of this model:
 Future queries
 Example: Retrieve all the airplanes that will come within 30 miles of
the airport in the next 10 minutes.
CS561
The MOST data model
► Database=set
► Special
of object-classes
database object time
► Object
class=set of attributes (MOTELS(name,
location, num_of_rooms, price_per_room))
► Some
object-classes are spatial w/ 3 attributes:
 X.POSITION, Y.POSITION, Z.POSITION
 Set of spatial methods associated w/ them (e.g.
INSIDE(o,P), OUTSIDE(o,P), DIST(o1,o2))
CS561
Dynamic Attributes
►
Attributes:
 Static (changes only when an explicit update of the database occurs)
 Dynamic (changes over time according to some given function, even if it is not explicitly
updated)
 Example: a moving object whose position in 3D space at any point in time( x, y, z are dynamic
attributes)
►
Dynamic attribute A is represented by 3 sub-attributes:
 A.value (depends on time)
 A.updatetime
 A.function (function of a single variable t that has a value 0 at t=0)
►
A.value:
 At time A.updatetime the value of A is A.value, and
 until the next update of A the value of A at time A.time+t0 is given by A.value+A.function(t0)
►
An explicit update of a dynamic attribute can change
 A.value,
 A.function
 or both.
►
Advantage to this approach:
 user can query each sub-attribute independently
 can ask “Retrieve all objects for which X.POSITION.function = 5*t, i.e. the objects whose speed
in the X direction is 5”
CS561
Three types of queries in MOST
► Instantaneous
- answer as of that time
 Example: the motels within 5 miles of my current
location
► Continuous
- the answer of the query is needed at
each of the future instances. Query pertains to
snapshot database
► Persistent
- Like a continuous query but uses past
as well future history.
CS561
Database Histories
►
Traditional databases: queries refer to the current database state (i.e.
query languages are nontemporal, i.e. limites to accessing a single
(current) database state)
►
MOB database: database implicitly represents future states of the
system being modeled (e.g future positions of moving objects)
►
Can have queries pertaining to the future (a moving car can request all
the motels it will reach in the next 20 minutes)
►
To interpret this type of queries , authors use the notion of a database
history, i.e. a sequence of database states (abstract concept).
►
A database state is a mapping that associates a set of objects of the
appropriate type to each object class.
CS561
Database Histories (cont.)
►
Each database state has an associated time stamp.
►
In the state, the value of a dynamic attribute is
 value of the attribute at the time t=time stamp.
►
Queries are interpreted over database histories (A database history is an
infinite sequence of database states, one for each clock tick)
►
The time stamps along the database history are strictly increasing
►
At a particular point in time t,
 the database states with a lower time-stamp than t are called past-database history
 states with a time-stamp higher than the current time t are called future database
history.
►
Each state in the future history is identical to the state at time t, except for the
value of the dynamic attributes.
CS561
Future Temporal Logic (FTL)
Language
How many cars will arrive
to WPI’s parking lot in the
next 5 minutes?
►
Motivation: Expressing temporal
queries on moving objects using
SQL and OQL are cumbersome
►
New query language for moving
objects database ->FTL (query
in FTL is simpler and more
intuitive)

Answer to future queries is
tentative
What are the traffic conditions 2 miles
ahead of me in the next 3 minutes?
CS561
FTL (cont.)
► Syntax: Retrieve <target-list> where <condition>
► FTL
employs spatial and temporal predicates
and operators
INSIDE(O,P), DISTANCE(O1,O2)<=5
EVENTUALLY-WITHIN-C, UNTIL g, ALWAYS-FOR-C, etc.
CS561
Future Temporal Logic (FTL)
Language
►
The answer is regarded as correct according to what is
currently known about the real world, but this knowledge
(the motion vector) can change.
►
Query=“Retrieve the pairs of objects o and n such that the
distance between o and n stays 5 miles until they both
enter polygon P”
FTL syntax:
RETRIEVE o,n
WHERE DIST(o,n)≤5
Until(INSIDE(o,P)^INSIDE(n,P))
CS561
Problems with FTL
►
Can only query about the future states, not the "past"
states.
 For example, if we want to query: " who has been in polygon area
A one hour ago?"
►
The General idea of solution is
 for the "immediate" past history, we can using the same indexing
function to trace back.
 for the "longer" past history, What can we do?
►
Question not addressed in the paper: how to record the
past states of the database efficiently and accurately and
how the query logic would look like?
CS561
Continuous Queries
►
Example:
 Consider a relation
MOTELS (geographic_coordinates, room_price, availability)
 Consider a moving car issuing a query “Display motels (with availability
and cost) within a radius of 5 miles”
 Query is continuous!!!
The car requests the answer to the query to
be continously updated.
►
As the car moves, the answer changes, so WHEN and HOW often
should the query be reevaluated?
►
Authors’ Solution:
 Single evaluation of the query
 Reevaluation has to occur only if the motion vector of the car changes.
CS561
Indexing
►
For performance consideration, in answering the queries
we would like to avoid examining each moving object in
the database (i.e. would like to index dynamic attributes)
►
Problem: since objects are continuously moving, the spatial
index has to be continusly updated
UNNACCEPTABLE SOLUTION!
►
Authors’ solution: a method of indexing dynamic attributes
which guarantees logarithmic (in the # of objects) access
time.
CS561
Indexing dynamic attributes
►
Objective: enable answering queries of the form “Retrieve the objects that are currently
in the polygon” without examining all the objects.
►
Authors’ solution:




Plot all the functions representing the way a dynamic attribute A changes with time.
Use spatial index for each dynamic attribute A
Spatial indexes use a hierarchical recursive decomposition of space, usually into rectangles;
The id for each object o is stored in the records representing the rectangles crossed by the
A.function of o.
►
Example: “Retrieve the objects for which currently 4<A<5” is entered at time 1:00AM
►
Then using the index we retrieve the records representing the rectangles that intersect
the rectangle



4<A<5
And 1-ε<t<1+ ε
For each object id in these records we check whether “currently” 4<A<5.
CS561
Indexing dynamic attributes (cont.)
► Update
of o.A causes the following:
 Updating the records representing rectangles ending
after time t;
 O is removed from the records representing rectangles
crossed by the old functon-line
 And is added to the records representing rectangles
crossed by the new function-line.
CS561
Indexing of dynamic attribute
► Note:
► In
spatial indexing is limited to finite space.
order to use this scheme we have to consider
 the time dimension starting at 0 and ending at some
time-point T.
 Consequently, the index needs to be reconstructed
every T time units.
 Choosing an appropriate value for T is an important
future-research question.
CS561
Implementing MOST on top of DBMS
Assumption: the relational model and SQL for the underlying DBMS (can be
extended to OO model).
Store each dynamic attribute A as three DBMS attributes A.value,
A.updatetime, A.function
1.
2.
If the query does not contain a reference to a dynamic attribute nor does it
contain temporal operators the query is simply passed to the DBMS and the
answer returned to the user.
Query contains references to dynamic attributes, but not temporal
operators:

“SELECT A” : The MOST system retrieves the attributes for A and
computes the value of A for each retrieved object before returning it to
the user
CS561
Implementing MOST on top of DBMS
(cont.)
 “WHERE clause F” (e.g. A>5):
► F is a boolean combination of atoms
► DBMS replaces Q (original query) by two queries Q1 and Q2.
► Transformation is F=(F’^p) and (F’’ ^ ~p) i.e. (true) and
(false)
► Q1 and Q2 are defined as follows:
 The target list of Q1 and Q2 consists of the target list of Q, plus
the subattributes of the dynamic attributes in p.
► The
FROM clause of Q1 and Q2 is identical to that of Q. The
WHERE clause of Q1 is F’ and that of Q2 is F’’.
► Q1 and Q2 are submitted to the underlying DBMS, and the
results are processed as follows before returning them to the
user.
CS561
Implementing MOST on top of DBMS
(cont.)
►
The atom p is evaluated on each tuple in the result of Q1 , and the
atom ~p is evaluated on each tuple in the result of Q2
►
The tuples that do not satisfy the respective atoms are eliminated, and
the projection of the union of the resulting tuples on the original target
list is returned to the user.
►
If the WHERE clause has multiple atoms referencing dynamic attributes
then we can give a function EVAL(Q) that performs the above
procedure recursively, each time eliminating one of the atoms
containing a dynamic variable.
►
If the original query has k atoms referring to a dynamic variable then,
in the worst case, this might mean evaluating up to 2^k queries that
do not contain dynamic variables. However, if k is small this may not
be a serious problem.
CS561
Evaluating a Query
►
Observe that the above procedure does not use indexing of the
dynamic attributes. In other words, the results of Q1 and Q2 are are
examined in their entirety. If indexing on the dynamic attributes is
available, then we can modify the above procedure as follows. Instead
of evaluating the atoms p and ~p on each tuple retrieved by Q1 and
Q2 respectively, we retrieve the tuples that satisfy p and ~p
respectively.
►
Then we join the relation returned by Q1 with the relation that satisfies
p; similarly, we join the relation returned by Q2 with the relation that
satisfies ~p.
►
Observe that in order for this procedure to produce correct results, we
must ensure that F’ and p are satisfied for the same tuple in the
cartesian product of the FROM relations. We ensure this by including in
the target list of all four queries, a key of each relation in the FROM
clause. The above method can extended to nested SQL queries as well.
CS561
New Research Topics in
Moving Objects Database
Distributed/Mobile query and trigger processing
with incomplete/imprecise location information
► Extensible and visual languages
► Comparison of indexing methods
► Uncertainty for moving objects that do not report their location
►
►
►
►
►
►
Data Mining
Privacy/Security
Location prediction
Performance/indexing for join queries
…and many more (not listed here)
CS561
Thank you
CS561