Practical theory
While some of the symposium’s presenters focused on purely theoretical spatio-temporal
issues — such as query methods or index performance comparisons —
others have tightly coupled their research to specific real-world applications, such
as astronomy, tourism, or LBS.
Galactic geometry. In a presentation titled “Cross-Outlier Detection,”
Spiro Papadimitriou of Carnegie Mellon University’s
Computer Science Department explained that the common approach to
discovering suspicious spatial data (also known as outliers) is to search within a
single set of observations for those that deviate from the norm. Recognizing the
limitations of the single-set approach, Papadimitriou has extended the range of
analytical tools with techniques for examining two datasets against each
other. One of his test cases involves astronomical data which, he explained, may
involve multiple types of inter-related galaxies.
For instance, referencing 993 spiral galaxies to 1,218 elliptical galaxies (see
Figure 4) reveals a phenomenon that would not make sense if the two
datasets were analyzed independently. Namely, in Papadimitriou’s words,
“elliptical galaxies form clusters, intertwined with clusters of spiral galaxies.
The distribution is overall even; however, a few of the elliptical galaxies are
within unusually dense clusters of spiral galaxies.” As with density queries,
the concept of multiset outlier detection is simple enough, but the implementation
is complex. |
FIGURE 4: Elliptical and spiral galaxy datasets
from the Sloan Digital Sky Survey are one of Papadimitriou’s real-world test cases
for multiset outlier detection. At top, “plain” (single-set) outliers are
red points. At bottom, multi-set analysis reveals red crossoutlier points. |
Off the (Berlin) wall. Closer to home is
LBS research by three professors interested in how to supply mobile PDAs with
the right data at the right time, no more, no less. Agnes Voisard, from Fraunhofer
Insitut für Software und Systemtechnik in Berlin, Germany, is prototyping an LBS
application with “richer and more targeted information” than the typical
“fastest route to the nearest drugstore” approach. In preparation for deployment
at the 2008 Olympics in China, Voisard is prototyping a TIP that provides information
to mobile devices and keeps a history of previous communications in order to
avoid unwanted duplication of messages.
Voisard describes how her focus differs from traditional LBS applications as follows:
“We are concerned here with applications involving mobile end users who
already acquired knowledge on a particular area and who would like to get more
information at a certain location, at a certain time, on particular topics and to
relate pieces of information (current and past) with each other.” To accomplish
this, TIP captures a history of pages visited and steadily builds a profile of the
user.
Her system also hinges on an event notification system that informs tourists
of concerts, plays, and other occurrences — either to suggest attendance or report
cancellations. In other words, users get information they may not have explicitly
asked for if their profiles suggest that they might be interested. To simulate how
such a system would work, Voisard has created a scenario of a day in the life of a
fictional user touring Berlin (see Figure 5). |
FIGURE 5 Voisard’s fictional tourist
follows a trajectory through Berlin, exploring the former Berlin Wall with
help from a clever TIP. |
Over the course of the tourist’s stroll,
the PDA reports facts based on nearby landmarks, and suggests a philharmonic
concert and places for lunch based on the user’s profile (see
Figure 6). |
FIGURE 6 A day in the life of a tourist unfolds
in a series of screens on a PDA. Some information is “pulled” by the tourist; some
is “pushed” by the TIP server. |
Que sera? Voisard explicitly notes that her concern is with the interface and
content of a mobile PDA application, not with underlying content delivery mechanisms.
Not to worry. Two professors of computer science, Jensen (Aalborg University),
and Ouri Wolfson (University of Illinois) have delved deeply into just this
topic. Both recognize the need to supply moving PDAs with map updates more
efficiently than periodic updates (such as every two minutes).
Their parallel research efforts indicate that if a map server guesses a moving
object’s future path, the efficiency of communications between server and PDA
increases dramatically. The challenge is to keep the prediction roughly in sync with
reality, readjusting when error exceeds a threshold. Jensen illustrated this approach
with a series of animated slides in which a moving vehicle stopped in traffic
or took an unexpected route (see Figures 7a–g). In both cases, the central server
recognized the irregularity and adjusted its prediction accordingly, in real
time. |
FIGURE 7a Efficient updates require a
predicted route: As the vehicle (red point) begins its journey, the map server guesses
its intended route (blue line). |
FIGURE 7b The anticipated vehicle location
(blue point) doesn’t match its actual location (red point). |
FIGURE 7c Predicted and actual vehicle locations
differ enough to signal a recalibration of the model. |
FIGURE 7d The map server recalculates the predicted
route (new blue line) based on the vehicle’s actual behavior (red point). |
FIGURE 7e Now the real vehicle (red point) is
stopped in traffic, but its predicted location (blue point) surges ahead. |
FIGURE 7f The prediction (blue point) gets out of
synch with reality (red point) again, so... |
FIGURE 7g ...the prediction recalibrates the
virtual vehicle location (blue point) with the real one (red point), but leaves
the route (blue line) as is. |
|