Transcript Algorithms and Data Structures

Location Based M-Services


Soon there will be more on-line personal mobile
devices than on-line stationary PCs.
Location based mobile-services


Moving users equipped with mobile phones, PDAs,
etc., periodically disclose their positions to the service
provider
The service provider tracks the movement of the users
and provides useful services:


“If you want to get home faster today, do not turn into street
X (where you will get into a traffic jam)”
“On the right, you should see the Smithsonian Air and Space
Museum – the museum you should definitely visit before
leaving Washington D.C.”
February 4, 2002
1
LBS Architecture
Location info
Positioning
Service requests (queries)
Service provider
DBMS
Services (location-specific,
on-time, personalized
information)
Data structures
Locations Maps,
of users other info
February 4, 2002
2
1.Reducing the Update-Load

In LBS scenarios and in other pervasive
computing scenarios (e.g., sensor nets) one of
the problems is a high load of updates

A million objects, each reporting its position once a
minute:




Too high communication loads
A database may not be able to keep up (We want to handle
as much as possible updates using a centralized database)
If objects move completely randomly and we want to
have very precise positions, not much can be done.
In the real world:


Objects move “orderly”
We may be satisfied with reduced accuracy
February 4, 2002
3
1.Reducing the Update-Load

Let the database have a much richer knowledge about
the future predicted movement of objects and let the
objects know what the database “assumes”:



No matter how a road is twisted, if I move with a constant
velocity on this road and the database knows the map of roads
and my velocity, there is no need to keep reporting my position
to the database
Allow for lazy updates. Two step query processing:
retrieve a larger candidate set, ask each of the objects
to report its latest position, and check if it really satisfies
the query
The goal of the project would be to develop and
evaluate these techniques assuming a specific type
of data (e.g., positions of moving cars)
February 4, 2002
4
2.Indexing in Oracle


Indexes are data structures that support
fast answers to queries
Commercial ORDBMSs support indices for
static spatial data:


“Find gas stations close to me”
No support for the indexing of continuously
moving objects:

“Find customers close to my gas station”
February 4, 2002
5
2.Indexing in Oracle

The goal of the project – to implement and
compare a number of alternatives for how
to index moving objects in Oracle:


One could view moving objects represented by
(x,y,vx,vy) as four dimensional moving points
and index them with the built-in spatial index
One could try to use Oracle index-extensibility
interface and implement a new index
specifically for continuously moving points
February 4, 2002
6
3.Managing Traffic using DB

The goal of this project would be to investigate a
specific application area – traffic management
using on-line vehicles:

I want to maintain an overview (and possibly record a
history of) the current traffic situation – an
approximate number of vehicles on each segment of
any road


I need to maintain this aggregate information in the database,
not enough just to have possitions of objects
I want to ask “shortest-path” queries, that take into
account traffic information
February 4, 2002
7
3.Managing Traffic using DB

Two directions for the project:


More theoretical (what kind of external data
structures are needed, how external
algorithms, e.g., graph algorithms, work)
More practical – again, take Oracle and look
how much we can squeeze out of it to
implement the desired functionality
February 4, 2002
8
Realistic Data for Experiments


Data from the tracking of a number of test
cars in Aalborg.
Moving object data generated with IBM's
City Simulator
February 4, 2002
9
Contact

Simonas Šaltenis and Michael Böhlen



Mike is not at the university this week
E1-215b and E1-215
[email protected], [email protected]
February 4, 2002
10