Database Reference
In-Depth Information
(a) GPS locations from trajectories
(b) Corresponding map of Los Angeles, CA
Figure 10.1.
Figure (a) shows a scatter plot of GPS points of approximately 200
GPS trajectories. Figure (b) is a road map of the underlying region of Los Angeles,
CA, from which these points were collected. In addition to providing an outline of
the highly traveled roads in LA, it can be seen that the GPS data represents multiple
modes of transportation (i.e. automobile, train, and walking).
fleet of taxis picking up and dropping off customers throughout the city.
There are several interesting queries and data management problems in
this setting. First, given the current position of each taxi as well as
the state (occupied or unoccupied), how can we eciently direct the
nearest unoccupied unit to respond upon receiving an incoming call?
As taxis are continually moving, how can we keep the information in
the database current in an ecient manner? Secondly, if updates occur
only intermittently, what is the most accurate approach to answering
queries when data may be stale? Third, can we identify any interesting
movement patterns? Can we identify points of interest from common
stops made throughout the city? Is it possible to infer the ecient
routes for a particular origin and destination given historical movement
patterns?
The examples presented above introduce problems in three different
areas of managing spatiotemporal data: (i) querying and indexing, (ii)
tracking, and (iii) mining. Querying mobile objects, like any temporal
data, introduces challenges in defining expressive predicates that prop-
erly handle the time domain. Additionally, constructing and maintaining
an index structure to eciently process queries over mobile objects is
dicult due to the high frequency of necessary updates. Because the
values (i.e. location) are constantly changing, the query workload is
skewed to become update-centric, forcing the index to update its struc-
