## Hadjieleftheriou.com

Complex Spatio-Temporal Pattern Queries
Marios Hadjieleftheriou, George Kollios
Petko Bakalov, Vassilis J. Tsotras
Computer Science Department
Computer Science Department
Boston University
University of California, Riverside
patterns and periodicities from spatiotemporal trajectories[17, 11]. This paper introduces a novel problem, what we
This paper introduces a novel type of query, what
term

*Spatio-temporal Pattern Queries *(STP). Given a large
we name

*Spatio-temporal Pattern Queries *(STP).

collection of spatiotemporal trajectories, an STP query re-
Such a query specifies a spatio-temporal pattern
trieves all trajectories that follow user defined movement
as a sequence of distinct spatial predicates where
patterns in space and time.

the predicate temporal ordering (exact or relative)
There are many practical applications where STP
matters. STP queries can use various types of
queries appear. For example, "Identify all vehicles that
spatial predicates (range search, nearest neighbor,
were very close to all three sniper attacks in Maryland (the
etc.) where each such predicate is associated (1)
locations and times of the attacks are known)" or "Locate
with an exact temporal constraint (a time-instant
products that left the factory a month ago, were stored in
or a time-interval), or (2) more generally, with a
one of the warehouses near the dock, and loaded on a ship
relative order among the other query predicates.

(locations can be tracked by using RFIDs)". While there
Using traditional spatio-temporal index structures
have been various previous works addressing the problem
for these types of queries would be either inef-
of pattern discovery [17, 11], to the best of our knowledge,
ficient or not an applicable solution. Alterna-
there has been no previous work on the orthogonal prob-
tively, we propose specialized query evaluation
lem, the STP queries.

algorithms for STP queries With Time. We also
We represent a spatio-temporal pattern as a sequence of
present a novel index structure, suitable for STP
distinct spatio-temporal predicates, where the temporal or-
queries With Order. Finally, we conduct a com-
dering (exact or relative) of the predicates matters. STP
prehensive experimental evaluation to show the
queries can have arbitrary types of spatial predicates (e.g.,
merits of our techniques.

range search, nearest neighbor, etc.), where each predicatemay be associated (1) with an exact temporal constraint that
is either a time-instant or a time-interval (STP Queries With
Spatio-temporal data management has received a lot of at-
Time), or (2) more generally, with a relative order (STP
tention recently, mainly due to the emergence of location
Queries With Order).

based services and advances in telecommunications (cheap
An STP query With Time example is: "Find objects that
GPS devices, ubiquitous cellular networks, RFIDs, etc.) As
crossed through region A at time

*T*1, came as close as pos-
a result, large amounts of spatiotemporal data is produced
sible to point B at a later time

*T*2 and then stopped inside
daily, typically in the form of trajectories. The need to effi-
circle C some time during interval (

*T*3

*, T*4)". An STP query
ciently analyze and query this data requires the develop-
With Order is: "Find objects that first crossed through re-
ment of sophisticated techniques. Previous research has
gion A, then passed as close as possible from point B and
concentrated on various spatio-temporal queries, mainly
finally stopped inside circle C". Here only the

*relative or-*
focusing on range searches and nearest neighbor varia-

*der *of the spatial predicates is important, independently of
tions [18, 19, 9, 16, 14], or mining tasks like extracting
when exactly they occur in time.

The straightforward approach for answering STP
queries is to evaluate the query pattern on all trajectories

*Permission to copy without fee all or part of this material is granted pro-vided that the copies are not made or distributed for direct commercial*
one by one using a linear scan on a sequentially stored

*advantage, the VLDB copyright notice and the title of the publication and*
archive. Clearly, this approach has prohibitive cost and in

*its date appear, and notice is given that copying is by permission of the*
some cases might be infeasible due to very large database

*Very Large Data Base Endowment. To copy otherwise, or to republish,*
sizes and due to the expensive nature of the distance func-

*requires a fee and/or special permission from the Endowment.*

Proceedings of the 31st VLDB Conference,
This work has been supportd by NSF grants IIS-0133825, IIS-
Trondheim, Norway, 2005
0308213, and IIS-0330481.

tion used for STP queries With Order (as will be seen
later on). When considering STP queries With Time, an-
other straightforward approach would be to use a tradi-
tional spatio-temporal index structure [18, 19, 21, 9] to
index the trajectories and utilize the index to evaluate the
query predicates individually; respective answers can be
combined in the end. When these STP queries consist only
of range spatial predicates such a solution might work well
Figure 1: An example STP query With Time.

in various practical cases. Nevertheless, this approach doesnot work for spatial predicates that need to be evaluated
straints impose a strict ordering on the spatial predicates.

conjointly, like nearest neighbors. Consider the following
When a temporal constraint is empty, ordering will be im-
example: "Find the object trajectory that crossed as close
plied by the actual position of the associated predicate in
as possible from point A at time

*T*1 and then, as close as
the query sequence. An alternative query expression mech-
possible from point B at a later time

*T*2". Individually
anism appeared in [3], where regular expressions were used
evaluating each predicate cannot provide the trajectory that
to represent mobility patterns. More details and limitations
minimizes the distance from both points. Alternatively, we
of this approach appear in the related work.

show how to adapt the traditional best first search approach
We say that a trajectory satisfies an STP query if it sat-
with a combined distance function (e.g., the sum of dis-
isfies all spatio-temporal predicates at once:
tances of each trajectory from the query points) to answerSTP queries With Time. With careful evaluation strategies

*• *A range predicate is trivially, and individually, satis-
we can guarantee that each needed page from the index is
fied by a trajectory if the object is contained inside
loaded only once, during the evaluation of all predicates.

the given range anytime during the specified temporal
Nevertheless, traditional spatio-temporal index struc-
tures would be a very inefficient solution for answering

*• *A nearest neighbor predicate is satisfied only with re-
STP queries With Order. Since only the relative order of
spect to all other NN searches as well. We say that a
the predicates is significant, the spatio-temporal index will
trajectory satisfies the NN predicates if it minimizes
have to retrieve the whole temporal evolution of each ob-
the sum of the distances from those predicates during
ject. For such queries, we propose a novel indexing tech-
the given temporal constraints.

nique that enables efficient evaluation by storing ‘order' in-formation inside the index.

An example STP query With Time is shown
To summarize, the contributions of this paper are the fol-
in Figure 1.

The query depicted is

*Q*
lowing: (1) We introduce and formalize a novel query type

*{*(

*N N *(

*q*1)

*, t*1)

*, *(

*NN*(

*q*2)

*, t*2)

*, *(

*R*(

*r*)

*, *[

*t*3

*, t*4))

*}*,
(STP) that combines general spatial predicates with tem-
satisfied by the trajectory that minimizes the sum of
poral constraints (STP queries With Time) and/or relative
distances from points

*q*1

*, q*2 at times

*t*1

*, t*2, respectively,
ordering (STP queries With Order). (2) We propose spe-
and crosses region

*r *anytime between [

*t*3

*, t*4).

cialized query evaluation algorithms for these two types ofSTP queries, as well as a novel index structure, suitable for
3 STP Query Algorithms
STP queries With Order. (3) Finally, we present an exten-
For ease of exposition we first present our solutions for
sive experimental evaluation of the proposed techniques.

STP Queries With Time, i.e., STP queries that contain spa-tial predicates with non-empty temporal constraints. Sub-
2 Problem Definition
sequently, we discuss solutions for the more general STP
Consider a large archive of object trajectories and a well-
Queries With Order, i.e., queries that are ordered sequences
defined trajectory representation such that the location of
of spatial predicates without temporal constraints.

the objects can be computed for any given time (the frame-
3.1 STP Queries With Time
work that will be presented is independent of the underly-ing trajectory representations). An STP query is expressed
Given that these queries contain both spatial and temporal
as a sequence

*Q *of arbitrary length

*m *of ordered spatio-
constraints, they can be answered using specialized evalua-
temporal predicates of the form
tion strategies on existing spatio-temporal index structures.

The spatio-temporal index can serve as a filtering step that

*Q *=

*{*(

*Q*
will reduce the number of accesses to raw trajectory data by
1

*, T*1)

*, *(

*Q*2

*, T*2)

*, . . , *(

*Qm, Tm*)

*}*
pruning trajectories that do not satisfy the pattern and im-
where in each pair (

*Q, T *),

*Q *represents a spatial predicate
proving query performance (against the linear search) by
and

*T *a temporal constraint. For simplicity but without loss
orders of magnitude.

of generality, in the rest,

*Q *will express either a

*range *(

*R*)
For simplicity we adopt a general trajectory indexing
or a

*nearest neighbor *(

*N N *) query. As will become clear,
scheme. Nevertheless, the algorithms that will be presented
our framework can be adapted easily to handle other spa-

*do not make any assumptions about the underlying index*,
tial predicates as well.

*T *is either a

*time-instant *(

*t*), a

*time-*
as long as it can answer efficiently nearest neighbor and

*interval *(∆

*t*) or

*empty *(

*∅*). Inherently the temporal con-
range queries . Without loss of generality, we assume that
a trajectory from a given predicate, as shown in Figure 2.

By combining approximate distances for all query predi-cates we will be able to prune trajectories that have lower-
bounding distances larger than any known upper-bound.

A simple 1-dimensional example is shown in Fig-
Figure 2: Approximating a trajectory with multiple MBRs.

This STP query is expressed as

*Q*
*{*(

*N N *(0)

*, *1)

*, . . , *(

*N N *(0)

*, *5)

*}*. Conceptually, it can be
the trajectories are approximated using a large number of
thought of as a time-interval nearest neighbor pattern: "Lo-
Minimum Bounding Rectangles [19, 9], which are then in-
cate the object that stays closer to the origin during time-
dexed using a spatio-temporal index structure like the R-
interval [1

*, *5]". Trajectory

*P*1 is the answer to this query
tree [8, 18] or the MVR-tree [21, 9]. With minor modifi-
since it minimizes the sum of distances from all five points,
cations to our framework, other approximation techniques
with distance

*D*(

*Q, P*1) = 5

*.*5. Trajectory

*P*3 does not
are applicable as well. Every MBR inserted in a leaf level
qualify since it partially intersects the query lifetime and
of the tree is associated with the identifier of the trajectory
has infinite distance for some time-instants. Using this sim-
that it belongs to, and bounds a small time-interval of the
ple example, we will illustrate two evaluation strategies,
object's movement history. An example of this indexing
called

*lazy *and

*eager*, and will discuss their advantages.

scheme is shown in Figure 2, where a trajectory has been
approximated using a total of three MBRs.

For the rest of this section we assume that the MBRs are
indexed using a

*secondary *spatio-temporal index structure,
with data entries pointing to the raw trajectory data on disk.

Raw data is stored on sequential data pages per trajectory.

Among STP queries with time, we first discuss queries
that contain multiple range predicates, since they can be
evaluated in a straightforward way.

queries with multiple NN predicates and present various
Figure 3: (a) Three trajectories and an STP query. For each
algorithmic approaches to evaluate them. Finally we dis-
query point the 1-NN MBRs (solid gray) are retrieved. (b) The
cuss queries that consist of combinations of range and NN
MBRs belonging to

*P*1 cover the query, while those of

*P*2 do not
cover points 4 and 5. Given

*D*(

*Q, P*1) = 5

*.*5 and

*LBD*(

*Q, P*2)

*≥*
3.1.1 Range Predicate Evaluation
5

*.*7, trajectory

*P*2 can be pruned (any missing MBRs for points 4and 5 should be at least as far as

*D*(

*q*4

*,*5

*, P*1) = 1 unit from the
Assuming a pattern query that contains only range spatio-
temporal predicates, there are two obvious evaluationstrategies to consider. The first approach produces the can-
Let

*D*(

*Q, P *) denote the actual distance of trajectory
didate results of all predicates concurrently using the index,

*P *from

*Q*. Also, let

*LBD*(

*Q, P *) (

*UBD*(

*Q, P *)) denote
and then loads from storage only the trajectories that be-
a lower-bound (upper-bound) distance of

*P *from

*Q *com-
long to the intersection of the partial answer sets. The sec-
puted by using the distances of the MBR approximations
ond strategy evaluates the most selective predicate first (as-
of

*P *from the query predicates. A threshold Λ needs to
suming selectivity information is available), then the raw
be computed so that all trajectories with

*LBD*(

*Q, P *)

*> *Λ
trajectory data is loaded from storage and the rest of the
can be pruned. In order to achieve this we incrementally
range predicates are answered in main memory, using the
locate the 1-NN, 2-NN, etc. MBRs individually for each
retrieved data. Which approach is better depends on the
query predicate. These MBRs should also contain the pred-
actual selectivities of the queries and the size of the trajec-
icate in the temporal dimension. After a number of MBRs
have been reported per

*qi*, for every discovered trajectory

*P *(i.e., a trajectory for which at least one MBR has been
3.1.2 Nearest Neighbor Predicate Evaluation
reported) there are two cases: (1) the union of

*P *'s MBRs
Consider an STP query that contains only nearest neigh-
contain all query points in the time dimension and we say
bor predicates. The basic idea behind our approach is to
that

*P covers *the lifespan of

*Q*, or (2) some points of

*Q *are
use the index structure and the trajectory MBRs to compute
not covered. For example, in Figure 3(a) the 1-NN MBRs
approximate object distances that will enable fast pruning
for each point are reported first (solid gray rectangles). At
of many trajectories, without having to load the raw trajec-
this step, no discovered trajectory MBRs cover all query
tory data. Our technique runs one best-first-search algo-
points. In Figure 3(b) the 2-NN MBRs are retrieved. This
rithm per query predicate that returns, successively, the ob-
time, the MBRs belonging to trajectory

*P*1 cover all query
ject with the smaller distance from that predicate. The total
distance of a single trajectory from the query can be com-
In the first case both

*LBD*(

*Q, P *) and

*UBD*(

*Q, P *) can
puted as the sum of individual distances from all predicates.

be computed without having to access the raw trajectory
Intuitively, by utilizing the trajectory MBRs we can com-
data. The upper-bound can be used as a pruning thresh-
pute both upper and lower-bounds of the actual distance of
old Λ. The lower-bound can be used to prune the tra-
jectory according to an already computed Λ. In the sec-
Algorithm 1 Lazy Nearest Neighbor STP queries With
ond case, a pessimistic approximation of

*LBD*(

*Q, P *) can
be computed. For each query predicate

*qi *that is cov-
Input: Query

*Q *=

*{*(

*N N *(

*q*1)

*, t*1)

*, . . , *(

*NN*(

*qn*)

*, tn*)

*}*
ered by

*P *the partial lower-bounding distance is equal to
Output: Nearest neighbor

*PB*
*D*(

*qi, P *). For the query points that are not covered by

*P*
1: Structure

*S ← ∅ *, Set

*U ← ∅*,

*P Q*1

*,.,n ← ∅*
the maximum such distance

*D*(

*qi, P 0*) is used, regardless
= 0, Λ =

*∞*,

*k *= 1,

*P*
*B *=

*∅*
of which trajectory it corresponds to. Referring back to
3: Initialize priority queues

*P Qi*
Figure 3(b), points 4 and 5 are not covered by

*P*
ConcurrentBestFirstSearch(

*k, Q, P Qi, U, S, Dq *)

*D*(

*Q, P*2)

*≥*
*i, P*2) +

*D*(

*q*4

*, P*1) +

*D*(

*q*5

*, P*1).

Due to the incremental discovery of trajectory MBRs, the
for

*P *in

*S *do
computed approximation is still a lower-bound of the ac-
if

*LBD*(

*Q, P *)
Λ then

*S*.remove(

*P *),
tual distance. By discovering trajectory MBRs incremen-

*U *.enqueue(

*P *)
tally and continuously improving the computed bounds, the
else if

*Q *Covers

*P *then
number of raw trajectory data that need to be loaded from

*PD *= GetTrajectoryData(

*P *)
if

*D*(

*Q, P*
storage is reduced substantially.

*D *)

*< *Λ then Λ =

*D*(

*Q, PD *)

*, PB *=
else

*S*.remove(

*P *),

*U *.enqueue(

*P *)
for

*P *in

*S *do
if

*LBD*(

*Q, P *)

*< *Λ then

*stop *= false
else

*S*.remove(

*P *),

*U *.enqueue(

*P *)
if

*stop *then break
Figure 4: Evaluating time-interval predicates.

18: Return

*PB*
In order to evaluate time-interval temporal predicates,
Algorithm 2 Concurrent Best First Search
for every query predicate

*qi *we need to locate the near-
Input:

*k, Q, P Qn, U, S, Dq*
est MBRs considering all time-instants contained in the
1: for

*i *= 1 to

*n *do
given interval. An example is shown in Figure 4, for
while

*P Qi *not empty do

*δt *=

*±*1. In order to perform correct pruning, the value
Entry

*N *=

*P Qi*.top
of

*D*(

*q, P *) should be set to the closest MBR to

*qi *in ∆

*t*.

if

*N *is a node then
This MBR is the one that minimizes the distance from the
for

*j *such that

*P Qj*.contains(

*N*) do
multi-dimensional region outlined by the query predicate
when conceptually sweeping time-interval ∆

*t *(e.g., the 2-
for

*C *in

*N *do
dimensional line

*AB *shown in Figure 4) and, thus, the
if

*C *not in

*U *and

*C *covers

*qj *then
search can be performed as a traditional NN search with

*P Qj*.enqueue(

*C*,

*D*(

*Q, C*))
an MBR query predicate.

else if

*N *is a data entry then
Given the secondary index assumption, the cost of ac-
S.insert(

*N *)
cessing the raw data is equivalent to one random disk ac-
Update

*Dqi*
cess per trajectory.

*∗ *In that case it is reasonable to post-
if

*k*-NN is discovered, continue from step 1
pone the data reads as much as possible and utilize lower-
bounds instead, such that a smaller candidate trajectory setcan be populated first. That way, we reduce the total num-
The lazy algorithm is shown in Algorithm 1.

*† *All re-
ber of accesses to the raw data storage, which means that
ported MBRs are probed into structure

*S *after being re-
query performance will depend mostly on the index access
moved from the priority queues during the NN searches.

cost (depending on the size of the final candidate set). We
The structure is responsible for keeping updated the cur-
call this the

*Lazy *strategy. On the other hand, an alter-
rent lower-bounds of each trajectory and the query predi-
native strategy is to eagerly load the raw trajectory infor-
cate coverage information. For that purpose a hash table
mation when evaluating each individual predicate, and di-
indexed by trajectory identifiers is constructed. The hash
rectly compute the actual distance of each trajectory from
table contains one entry per trajectory. Each entry stores
the STP query. We can use the actual distances as tighter
the current lower-bound distance and a bit vector, one bit
pruning thresholds that will help prune other trajectories
per query predicate, indicating which predicates have not
using lower-bounds, very efficiently. We call this the

*Ea-*
been covered yet by the trajectory MBRs. Every time a

*ger *strategy. The best strategy to use depends on the char-
new MBR is discovered, the corresponding trajectory entry
acteristics of the dataset (how many pages are occupied per
is retrieved, the appropriate bits are set and the lower-bound
trajectory) and the query properties.

distance is updated. Examining if a trajectory covers the

*∗*We assume that individual trajectories are stored sequentially on disk

*†*The algorithm for the eager strategy needs only simple modifications
if they occupy more than one page.

and is thus omitted.

query is a binary AND operation on the bit vector. For tra-
the queues and speeding up the searches. The second ap-
jectories that cover the query, the actual distance

*D*(

*Q, P *)
proach, that postpones range evaluation until a trajectory is
is computed and stored as the lower-bound. For other tra-
loaded from storage during nearest neighbor evaluation, is
jectories, the appropriate

*D*(

*qi, P *) values are used.

expected to work well in practice if the selectivity of the
The function ConcurrentBestFirstSearch (Al-
range searches is low, since they will never have to be eval-
gorithm 2) utilizes the best first search nearest neighbor al-
uated in full. It also fits nicely with the incremental flavor
gorithm to find the

*k*-NN of every query point. The search
of our algorithm, by essentially providing a unified tech-
is incremental so that the priority queues can be preserved
nique for answering all types of queries. In addition, it
and reused between subsequent executions. Array

*D*(

*qi*)
does not make the assumption that the selectivity of the
is maintained by storing for each query point the distance
predicates can be estimated.

from the last entry removed from the top of the correspond-
3.2 STP Queries With Order
ing priority queue. Both functions can be straightforwardlymodified to support time-interval predicates as well as top-
Assume now that the user is not interested in the exact

*k *searches, where more than one trajectories are retrieved.

times that the spatial predicates were satisfied, but only
For completeness, we use the extended algorithm for our
in the order in which they did. Hence these STP queries
experimental evaluation, but present the simpler versions
can be expressed as ordered sequences of spatial predicates
here for ease of exposition.

of the form

*Q *=

*{Q*1

*, Q*2

*, . . , Qn}*. Let

*SQ *(

*P, t*
Since the algorithm runs a number of concurrent NN
note the fact that trajectory

*P *, during its lifetime, satisfied
searches, it is unavoidable that some tree nodes will be
predicate

*Qm *at time-instant

*tk*. A single trajectory may
retrieved more than once for a number of different pred-
satisfy any given predicate for multiple time-instants. For-
icates, even though each best first search will access the
mally, we say that trajectory

*P *satisfies query

*Q *if there ex-
minimum required number of nodes individually [10]. In
ists an

*n*-length sequence

*SQ *(

*P, t*
1)

*, . . , SQn*
cases where there are no memory constraints LRU buffer-
that

*ti ≤ tj*, for all 1

*≤ i < j ≤ n*. Note that the time-
ing can be used. Since many NN searches will have similar
interval between any two consecutive

*ti, tj *can be arbitrary.

priority queues that share many common entries, especially
A solution that utilizes existing spatio-temporal index
for query predicates that lie close in space and time, local-
structures (as in the previous section) will certainly be in-
ity of reference ensures that LRU buffering techniques will
efficient for STP queries with order, since no temporal con-
have a high hit ratio after the buffer becomes hot. Alterna-
straints are specified. In order to evaluate a single predicate,
tively, the NN searches can be performed in a round robin
the complete evolution of the index on the temporal dimen-
fashion, and every time a node is retrieved from the top of
sion will have to be examined. That is, a range query will
one priority queue, the rest of the queues are scanned and
need to encompass the whole lifespan of the dataset on its
if the node is already contained in any of them, then it is
temporal dimension (which for large trajectory archives be-
directly replaced with its children. It can be shown eas-
comes prohibitively expensive). Instead, we propose effi-
ily that due to the sequence of insertions in the queues, this
cient solutions to STP queries With Order by using special-
strategy will guarantee that every node that is ever accessed
ized index structures. First, we consider queries with range
by any predicate, will need to be accessed only once for all
predicates only. Then, we proceed by discussing queries
with multiple NN predicates, and we conclude the sectionby considering their combinations.

3.1.3 Combinations
3.2.1 Range Predicate Evaluation
For STP Queries With Time that contain combinations ofrange and NN searches, the evaluation order of the pred-
Instead of using a (3-dimensional) spatio-temporal in-
icates is restricted, by construction, since the satisfiability
dex one could project out the temporal dimension from
of the NN predicates depends on the satisfiability of all the
each trajectory and index the resulting objects with a 2-
range searches. There are two alternatives: (1) Evaluate
dimensional spatial index. A spatial range query can then
some or all of the range predicates first and then proceed
easily retrieve all trajectories that satisfy it, irrespective of
with nearest neighbors evaluation and (2) evaluate all near-
the time that they did so. Intuitively, to find if a trajec-
est neighbors first, by taking into account the satisfiabil-
tory satisfies the STP query, all range predicates would be
ity of the range searches whenever a candidate for updat-
evaluated first, the intersection of the individual result sets
ing threshold Λ is retrieved. If the selectivity of any range
would be computed, and the remaining trajectories would
predicate is known to be very small then, after evaluating
be retrieved in order to check if they really do satisfy the
this predicate, all qualifying trajectories can be loaded from
predicates in the correct order.

storage and the rest of the queries can be processed in main
There are however clear disadvantages with this solu-
memory. Otherwise, all range predicates can be evaluated
tion. First, this structure does not inherently preserve or-
in advance and the disqualified trajectories can be pinned
der. Moreover, the quality of the 2-dimensional index is ex-
in set

*U *. If the number of candidate trajectories is still
pected to be worse than the 3-dimensional spatio-temporal
too large for main memory evaluation, the nearest neighbor
one. This is because, in the 3-dimensional structure, indi-
ranking process will benefit substantially after eliminating
vidual trajectory MBRs are consecutive in time and node
all trajectories contained in

*U *, by decreasing the size of
overlapping is introduced only because of different trajec-
tories overlapping each other is space and time. On the
contrary, in the 2-dimensional projected environment the
A:( P ,3),( P ,5),( P ,8)
MBRs of a single trajectory could actually be projected on
top of each other, even containing each other in the worst
B:( P ,4),( P ,9),( P ,13),( P ,3)
case (see Figure 2). This will lead to further node overlap-
C:( P ,4),( P ,10),( P ,2)
ping, affecting the index quality substantially.

Ideally, we would like to have an index structure that
maintains the order with which each trajectory satisfies an
A uniform partitioning and the representation of cells
as lists of sorted trajectory identifiers.

arbitrary sequence of range predicates. One way to ac-complish this would be to create a ‘predicate index', thatis, an index on the range predicate themselves, instead of
Algorithm 3 Range STP queries With Order
the object trajectories. For each range predicate

*rm*, the
Input: Query

*Q *=

*{R*(

*r*1)

*, . . , R*(

*rn*)

*}*
structure associates an ordered list of

*Sr *(

*P*
Output: Trajectories satisfying the predicates

*l, tk*) entries
that contains all trajectories that satisfy the predicate. En-
1: for

*i *= 1 to

*n *do
tries in such list are ordered by trajectory identifier (

*P*
*i *= combined list of cells intersected by

*ri*
Since a trajectory can satisfy predicate

*r*
3: Candidate set

*U ← ∅*
*m *many times
throughout its duration, the entries of the same trajectory
4: for

*i *= 1 to

*n *do
are further ordered by time (

*t*
for

*j *= 1 to

*n *do

*k*). Then, given an STP query

*Q *=

*{R*(

*r*
if

*L*1[

*i*]

*.id 6∈ Lj *then break
1)

*, R*(

*r*2)

*, . . , R*(

*rn*)

*}*, all range predicates can
be evaluated concurrently using an operation similar to a
"merge-join" among the

*n *lists associated with these pred-
Let

*k *be the first entry for

*L*1[

*i*]

*.id *in

*Lj*
icates. Using this structure the correct answers are retrieved
while

*L*1[

*i*]

*.id *=

*Lj*[

*k*]

*.id*
in

*sorted trajectory identifier order*.

if

*L*1[

*i*]

*.id 6*=

*Lj*[

*k*]

*.id *then break
There are two cases where entries from the lists can be

*U *=

*U ∪ L*1[

*i*]

*.id*
skipped (thus resulting in faster processing of the merge-
join). First, whenever in a given predicate list

*rm *a tra-
13: Retrieve trajectories in

*U *and verify the results
jectory identifier (say

*Ps*) is encountered that is larger thanall the trajectory identifiers currently at the top of the other
icate is larger than the cell size, we approximate it by the
lists, entries from these lists corresponding to trajectories
smallest enclosing range of cells. In order to use the above

*Pr *(

*r < s*) can be effectively skipped. Essentially, predi-
join algorithm a sorted list needs to be materialized first
cate

*rm *cannot be satisfied by any of the trajectories with
for the combined cells. Since the individual cell lists are
smaller identifiers (simply because such identifiers did not
already ordered by trajectory identifier, this list can easily
appear in the list of

*rm*). Second, the time-instant at which
be created with cost linear to the number of total entries
a trajectory satisfied a corresponding predicate, would as-
in all the lists. After all predicate lists are materialized, the
sist in skipping list entries whenever the ordering of the
search can proceed as before. At the end, a verification step
query predicates was not obeyed.

is needed, since some trajectories that might be contained
The above observations lead to an interesting intuition.

in a cell, might not actually be contained in the query range
Clearly not all possible (ad hoc) spatial range predicates
predicate. A fine grid granularity will clearly lead to small
can be indexed. Instead however, we can use a space par-
number of such false positives. Using a grid resolves the
titioning grid. With a fine grid granularity we can repre-
overlapping issues of the traditional MBR indices while it
sent any arbitrary range query with reasonable accuracy
also prunes many object trajectories from the search by pre-
as a combination of grid cells. Intuitively, each cell acts
serving temporal ordering. Moreover, the elimination of
as a small range predicate; thus a predicate list is created
trajectories that do not satisfy some of the predicates can
for each cell storing the trajectories that passed through the
happen without having to access the raw data from storage,
contrary to the available alternatives for spatio-temporal in-
For ease of exposition assume that a regular grid is used
dex structures. Furthermore, it achieves substantial space
to partition the space. Each cell is represented with a
savings since it maintains only symbolic representations of
unique cell identifier. An illustrative example is shown in
trajectories, i.e., trajectories that are approximated within
Figure 5. Trajectory

*P*3 crossed cell

*B *at time-instant 3. At
the given grid granularity. At the same time, it discretizes
time-instant 4 trajectory

*P*1 entered the cell. Trajectory

*P*2
the space, keeping only a fixed number of lists. The cell
followed at time-instant 9 and returned at time-instant 13.

lists can be stored on secondary storage. For static environ-
For simplicity, in this example we assumed that each trajec-
ments, they are stored in sequential disk pages. For appli-
tory remained in the cell for a single time-instant. Then the
cations where inserts, deletions and updates are allowed to
list for cell

*B *becomes

*{*(

*P*1

*, *4)

*, *(

*P*2

*, *9)

*, *(

*P*2

*, *13)

*, *(

*P*3

*, *3)

*}*.

the historical trajectories the lists can be stored as B-trees.

The proposed approach is shown in Algorithm 3. If a
Even though in the preceding analysis we use uniform
range predicate is contained within a cell, we overestimate
grids for simplicity, in practice, we do not need to main-
the result by using the cell's list instead. If a range pred-
tain a simple regular grid over the data. Alternatively, we
may use any dynamic space partitioning structure like the
examined by moving one cell further away from the query
adaptive grid files, kdb-trees, etc. [6]. The goal in this case
in every direction (hence, in the beginning it examines the
would be to guarantee that all nodes (equivalent to cells)
cell containing the query, then the eight cells adjacent to
of the structure, contain approximately the same number of
the query, and so on). For all new entries

*Sq *(

*P, t*
data, such that the corresponding lists have similar sizes,
are added in the queue at each step, the lower-bound dis-
which depends on the spatial density of the dataset. That
tance

*LBD*(

*qi, P *) is computed pessimistically; i.e., assum-
way, the grid granularity is adaptive.

ing that the actual trajectory would be as close as possibleto the query.

3.2.2 Nearest Neighbor Predicate Evaluation
Then, all the predicates are evaluated in a round robin
We now consider STP queries With Order that contain only
fashion. Simultaneously, for every new cell added in the
nearest neighbor predicates. An object trajectory satisfies
queue of a query predicate, the algorithm first joins it with
the query if it minimizes the sum of the distances from the
the queues of all other predicates. Trajectories that visit
query predicates and in the correct order. One straightfor-
the predicates in the correct order are loaded from storage
ward approach is to use the incremental ranking nearest
as soon as they have appeared in all queues, and the exact
neighbor algorithm introduced for STP queries With Time
distances are computed. The pruning threshold Λ is up-
with two needed modifications: (1) The pruning threshold
dated accordingly. For trajectories with incorrect order the
Λ needs to be updated only if a candidate trajectory truly
exact distance computation is postponed. Next, the lower
minimizes the distance in the correct order and not arbitrar-
bound distance from the query needs to be computed for
ily; and (2) the best first search queues should be populated
all candidate trajectories that appear in at least one of the
even with entries that do not contain the predicates in the
queues. Assume that a trajectory entry

*Sq *(

*P, t*) exists in
temporal dimension. However, this solution is expected to
the queue for

*qm*. The minimum partial distance of

*P *from
yield poor query performance since it does not inherently

*qm *is equal to

*MinDist*(

*qm, C*), where

*C *is the cell that
prune using predicate ordering but needs to postpone order-
contains

*P *at time-instant

*t*.

*‡ *Assume that no entries for
ing verifications until a trajectory is loaded from storage.

trajectory

*P *are contained in the queue of predicate

*qm*.

Also, the increased number of nodes that will be inserted in
Then,

*P *has not been discovered yet for

*qm*, thus it has to
the queues will slow down execution, intensify the search
lie at least as far as the farthest explored point for

*qm *in
cost, and increase the memory requirements. Moreover,
every direction. This distance is equal to the minimum of
similar with the case of range predicates, an approach that
the distances of

*qm *from the sides of the rectangle defined
first uses a 2-dimensional projection to eliminate the tem-
by the perimeter of the explored cells (this will be clarified
poral dimension is expected to make matters even worse.

with an example next). Given the total lower bounding dis-
Finally, since there is no way of evaluating if an MBR at the
tance of each trajectory from the query and Λ, trajectories
top of a queue is a possible candidate in a satisfiability list
can be safely pruned in every step.

for the query

*Q*, such MBRs cannot be pruned or replacedby subsequently discovered MBRs. Instead, all MBRs need
to be retained, while the lower-bounding distances of each
discovered trajectory needs to be computed according to
the nearest MBR to every query predicate. This in itself
means that the lower-bounds cannot be improved during
evaluation, thus, no trajectories can be pruned unless a truly
small Λ is computed. Hence, it is expected that this tech-
Figure 6: An example of the incremental nearest neighbor algo-
nique will need to load an excessive number of trajectories
from storage, in order to prune all candidates and terminate
The actual algorithm is omitted since the modifications
the search. To conclude, it is reasonable to say that a tradi-
can be straightforwardly applied in Algorithm 1. The en-
tional spatio-temporal index structure cannot be efficiently
queue, join and merge procedure is shown in Algorithm
used to answer these queries, because it will deteriorate to
4. We further illustrate the details of the algorithm using
sequential scan, or even worse. This is corroborated by our
an example. Figure 6 depicts an STP query with two NN
predicates

*q*1

*, q*2 in that order, a 6

*× *4 grid, and three tra-
On the other hand, the space partitioning index structure
jectories. The grid cells have identifiers

*A, B, . . , X, Y*
proposed in the previous section can be used to speed up the
starting from the lower left corner (not all cell identifiers
execution of these queries as well. Once more, we utilize
are depicted). In the first phase of processing, the com-
the incremental ranking algorithm described above. How-
bined list of

*q*1 consists only of the entries in cell

*H*, which
ever, instead of using the best first search strategy per query
contains element

*Sq *(

*P*2

*, *8). Similarly, the list of

*q*2 con-
predicate, the algorithm iteratively en-queues and examines
tains entry

*Sq *(

*P*3

*, *7). The partial distance of

*P*2 from

*q*1
all the cells adjacent to the cell containing the query. For
is set to 0, while the pessimistic distance from

*q*2 is equal
every query predicate

*qm *a sorted queue of satisfiability
to the minimum distance of

*q*2 from the sides of cell

*R*.

predicates

*Sq *(

*P, t*
*i*) is maintained. This queue is popu-
lated with all the entries contained in adjacent cells. In each

*‡*The minimum distance of a point from a rectangle is defined as usual
phase, the process increases the number of adjacent cells
Algorithm 4 En-queue, Join and Merge Operation
Another interesting problem is computing the minimum
Input:

*l, Q, CL*
ordered distance of a trajectory from a given query effi-

*n, S , Dq*1

*,.,qn*
1: for

*i *= 1 to

*n *do
ciently. Assuming discrete time or approximate trajectory
Locate next level of cells

*l*
representations, one way is to exhaustively check all pos-
for each new cell list

*L *do
sible sequences of locations. A better way is to use the
for

*T ∈ L *do
Threshold Algorithm (TA) [4]. Given a query

*Q *and a
S.insert(

*T *)
trajectory

*P *, the

*n*-length sequence of locations that mini-
Join with lists

*CLj, j 6*=

*i *to see if T satisfies
mizes the distance from all predicates and also satisfies the
the order (similarly to the range query algo-
query order can be found by using the incremental top-

*k*
rithm), and if yes tag it in

*S *for subsequent
ranking concept of TA. Our algorithm will perform even
better, since whenever the actual query to trajectory dis-
Insert

*T *in list

*CLi*
tance needs to be evaluated, the following information is
Update

*Dqi*
already computed: (1) That the trajectory definitely satis-
fies the predicate order, and (2) that all the trajectory pointsthat are candidates for minimizing the total distance are al-
The total lower bound

*LBD*(

*Q, P*2) from the query is thus
ready available. Given the above and the expensive nature
equal to 0 +

*M inDist*(

*q*2

*, R*) (similarly

*LBD*(

*Q, P*3) =
of this distance function, it should be clear now that our
0 +

*M inDist*(

*q*1

*, H*)). In the next phase the algorithm
technique will offer substantial improvement over the ex-
evaluates all cells adjacent to

*q*1 and

*q*2. Starting with

*q*1
haustive search or any other technique that needs to evalu-
the process merges the lists of cells

*A, B, . . , N, O *(the
ate this distance from scratch.

shaded region around

*q*1), with the list of

*q*1 (cell

*H*). Be-
fore the merging operation, each cell is joined with

*q*2, and
3.2.3 Combinations
entries that follow the query ordering are loaded from stor-age for verification. For example, consider cell

*B *being
Using our proposed grid structure combinations of range
merged with query list

*q*
and nearest neighbor STP queries can be answered as well.

1. The list of

*B *contains element
The same approach as with STP queries With Time can be

*B *(

*P*2

*, *9). First, we join

*B *with

*q*2 and deduce that there
is no entry in

*q*
utilized. The incremental algorithm can be modified to take
2 with the same identifier yet, so no action
needs to be taken. Likewise, when merging cell

*N *, ele-
into account the range predicates during the joining phase
of the lists. More specifically, in the beginning, for every

*N *(

*P*3

*, *2) is probed into list

*q*2, where it is already
contained with a satisfiability predicate corresponding to
range predicate we create a combined list of the entries of
time-instant 7. Thus,

*P*
the constituent cells which remain fixed throughout execu-
3 satisfies the order and, in addition,
it has appeared in the lists of all predicates, so it is loaded
tion. Then, while evaluating the NN predicates in round
from storage for an exact distance computation and Λ is
robin fashion, every time a new cell is added in the list of a
specific predicate, we join the sorted list of the cell with allother lists of nearest neighbor and range predicates, and in-
Trajectories for which the computed lower bounds are
stantly prune the entries that do not satisfy any of the range
larger than Λ can be safely pruned (none in this case yet).

predicates with the correct order. The added benefit of the
The rest of the cells are merged in the same way. The
algorithm is that, depending on the selectivity of the range
list for

*q*1 becomes (

*P*1

*, *3

*− *8)

*, *(

*P*2

*, *6

*− *9)

*, *(

*P*3

*, *2

*− *4)
queries, it is expected that the candidate entries for inclu-
(consecutive entries have been concatenated). In the same
sion in the lists will decrease substantially during evalua-
phase, when merging cell

*X *with query

*q*2, we join ele-
ment

*SX*(

*P*2

*, *1) with the list of

*q*1, where four entries for

*P*2 are already present. Since all entries are associated with
4 Experimental Evaluation
time-instants larger than 1, we deduce that no sequence ofsatisfaction predicates follows the order of the query, so no
We proceed with a comprehensive experimental evaluation
action needs to be taken. After all cells around

*q*2 have been
of the proposed algorithms. We run various experiments
merged, the new partial distances of all trajectories can be
with synthetic datasets to test the behavior of each tech-
computed. For trajectory

*P*3 the exact distance is known.

nique under different settings. All experiments were run
For the rest of the trajectories, since they did not satisfy the
on an Intel Pentium-4 2.4 GHz processor running Linux,
order, the partial distance is equal to the minimum distance
with 512 MBytes main memory. We generated synthetic
of the query point from the sides of the rectangle corre-
datasets of moving object trajectories. The dataset repre-
sponding to the perimeter of the newly added cells (the far
sents the freeway network of Indiana and Illinois. The 2-
side of cell

*K *in this case as shown with the arrow). The
dimensional spatial universe is 1,000 miles long in each
intuition is that since the points found so far do not satisfy
direction and contains up to 500,000 objects. Object ve-
the ordering yet, any point that does must be at least as far
locities follow a Gaussian distribution with mean 60 mph,
as this distance from the query (i.e., contained in the next
and standard deviation 15 mph. We run simulations for 400
level of cells in the best case). After computing the new
minutes (time-instants). To illustrate the generality of our
lower bounds it can be deduced that trajectories

*P*1 and

*P*2
framework, we index the data using two different indexing
can be pruned given the current Λ, and the algorithm stops.

techniques, the R-tree and the MVR-tree.

4.1 STP Queries With Time
unaffected, since a nearest neighbor is discovered fast andthe searches terminate faster.

For this type of queries trajectories were split into multiple
In terms of average trajectory loads (LR-T and ER-T),
MBRs and then indexed using an R-tree and an MVR-tree.

for RANDOMPATTERNS all algorithms need to load an in-
For our experiments we approximated the datasets using
creasing number of trajectories, as the number of predicates
on average 20 MBRs per trajectory (for a total of approxi-
increases. In order to find the top-20 results the probability
mately 6,000,000 MBRs) [9]. We set the page size for all
that many trajectories satisfy the query decreases propor-
indices to 4 KBytes, and used a 256 pages LRU buffer (e.g.,
tionately and the searches start expanding correspondingly,
in comparison to a total of 61,477 pages present in an R-
thus many trajectories are being discovered. The eager al-
tree indexing 300,000 trajectories). For clarity we present
gorithm loads a larger number of trajectories in all cases.

the results only for the R-tree in the graphs, but very similar
Assuming one random I/O per trajectory access, the ea-
conclusions were drawn for the MVR-tree as well.

ger achieves the best performance overall, balancing the
We use four query sets: RANDOMPATTERN, RELE-
trajectory accesses and the index overhead, especially for
VANTPATTERN, COMBINEDPATTERN and INTERVALPAT-
large numbers of predicates, where the searches become
TERN. All query sets contain sets of NN predicates only,
expensive. For RELEVANTPATTERNS all algorithms load
except from the COMBINEDPATTERN that contains com-
the same number of candidate trajectories. Since there ex-
binations of NN and range predicates. All sets have 100
ist many trajectories similar to the given query, the top-20
queries and each query consists of a number of predicates
candidates are found very fast, and only few extra trajecto-
at increasing time instants. For all queries we provide the
ries cannot be pruned using the lower bounds.

top-20 results. Queries in the RANDOMPATTERN set have
predicates that lie on consecutive nodes of the network,
reachable from each other given the maximum velocity of
objects and the temporal constraints of the query. The R
EVANTPATTERN set contains queries that are formed from
partial segments of object trajectories already contained in
the dataset, slightly skewed in time and space from the

**Number of predicates**
**Number of predicates**
original, with random location/time-instant tuples dropped
Figure 7: RANDOMPATTERN: Number of predicates.

in-between. With the COMBINEDPATTERN set, we evalu-ate the algorithms using query sets that are a mix of NNand range predicates. In particular, we randomly replace
a number of NN predicates with range searches centered
at the same positions. Finally, the I
NTERVALPATTERN set
is generated similarly to the R
ELEVANTPATTERN, and in-
cludes only NN predicates but with time-interval temporal

**Number of predicates**
**Number of predicates**
Comparison vs. Linear Scan. Since our query sets
Figure 8: RELEVANTPATTERN: Number of predicates.

contain NN predicates, we can only compare against a lin-ear trajectory scan (since the traditional search algorithms
Performance vs. Dataset Size. Next, we run scale-up
for spatial index structures cannot be applied). We com-
experiments with increasing numbers of trajectories. Fig-
pared the linear scan against our techniques for all subse-
ures 9 and 10 summarize the results. We used both RAN-
quent experiments. Although, since the total I/O of this
DOMPATTERN and RELEVANTPATTERN query sets with
straightforward approach was, on average, three orders of
10 predicates per query. As expected, we observe that for
magnitude higher than the other algorithms, we exclude it
all index structures the average number of node accesses
from the graphs in order to preserve detail. Hence in the
per query increases, since the total number of nodes in the
rest we concentrate on the relative performance of the lazy
structures increases as well, and the trees become deeper.

and eager algorithms.

The total number of trajectory accesses remains stable for
Performance vs. Number of Predicates. We test our
RELEVANTPATTERNS, since the top-20 results per query
algorithms for queries with increasing number of predi-
are discovered very fast, irrespective of the total number
cates. The results are shown in Figure 7 for the RANDOM-
of objects in the dataset. On the contrary, for RANDOM-
PATTERNS and Figure 8 for the RELEVANTPATTERNS,
PATTERNS there is a linear increase in the number of tra-
where we plot the index I/O, the trajectory I/O and the
jectory access, since with a larger dataset size and looser
total I/O for each technique. Clearly, for RANDOMPAT-
thresholds, more trajectories are discovered during the NN
TERNS and numerous predicates the lazy algorithm dete-
searches. In terms of total I/O the eager algorithm is once
riorates substantially. Many index nodes need to be ac-
more the best choice overall, providing better results for the
cessed before a tight threshold can be computed, hence,
the NN searches become very expensive. On the contrary,
Query Runtime vs. Number of Predicates. Figure 11
for RELEVANTPATTERNS all algorithms remain practically
reports the average computational cost (as the total wall-

**l I/O **1000

**Number of trajectories**
**Number of trajectories**
Figure 9: RANDOMPATTERN: Number of trajectories.

Figure 13: RELEVANTPATTERN: Increasing top-

*K*.

same time. Larger buffer sizes help alleviate the problem
of loading these nodes multiple times. We can see from the
graph that an 1 Mbyte buffer is adequate for eliminating
most superfluous node accesses. As expected, the lazy al-
gorithm benefits the most, since it is the one with the heav-
iest index access cost.

**Number of trajectories**
**Number of trajectories**
ELEVANTPATTERN: Number of trajectories.

clock time, averaged over a number of executions) for top-
20 queries of various numbers of predicates. Doubling the
number of predicates doubles the amount of time required
to answer the RANDOMPATTERN queries, as expected due

**Buffer size (Kbytes)**
**Buffer size (Kbytes)**
to lack of good candidates. In contrast, the number of pred-
Figure 14: Buffer size.

icates does not affect RELEVANTPATTERN queries, whichare easier to answer.

Interval Queries. We performed experiments using the
INTERVALPATTERN queries. We used a fixed time-interval
∆

*t *equal to ten time-instants for all query predicates. For
comparison purposes Figure 15 shows the results of the ea-
ger algorithm for queries with time-instant predicates and
interval predicates (IER) (the same set of queries was used,
where each time-interval constraint was replaced with a

**Number of predicates**
**Number of predicates**
time-instant). As expected, interval queries have the larger
Figure 11: Query runtime.

index access cost in comparison with time-instant queries,due to the larger number of nodes that intersect with the
Performance vs. Increasing Top-

*K*. Next we test
temporal constraints of the predicates. A surprising result
the algorithms for increasing numbers of reported nearest
is that interval queries load much fewer candidate trajecto-
neighbors. Figures 12 and 13 plot the results from 2 up
ries from storage. Intuitively, the time-interval algorithm
to 100 reported objects per query. The eager algorithm re-
locates very similar trajectories to the query a lot faster, by
mains unaffected from increasing top-

*K*. All techniques
performing a more robust searching on the time dimension,
scale up well since most of the nearest neighbors have al-
thus a very tight threshold is computed earlier during the
ready been discovered in earlier stages of the algorithms,
evaluation process.

thus increasing the number of reported neighbors does notaffect the total number of nodes or trajectories that have to
be retrieved.

** I/O**

x

e 200

**Number of predicates**
**Number of predicates**
Figure 15: INTERVALPATTERN: Number of predicates.

Combined Queries. Finally, we tested our algorithms
Figure 12: RANDOMPATTERN: Increasing top-

*K*.

for COMBINEDPATTERN queries that contain both NN andrange predicates. Figure 16 shows the effect of increas-
Performance vs. Buffer Size. Figure 14 plots the ef-
ing the range query selectivity to the index and trajectory
fect of the buffer size on query performance. We use 10
access cost, when using top-20 queries. Line ER-I corre-
predicates per query and top-20 nearest neighbors. Since
sponds to the cost of answering a query that contains only
we run multiple NN searches concurrently we expect some
NN predicates. RER-1 and RER-2 correspond to answer-
searches to access the same nodes at approximately the
ing the same query, where one NN predicate has been re-
placed with a range predicate. Clearly, for very small range
significantly reduced index I/O, due to more efficient prun-
queries that do not contain the actual nearest neighbors of
ing during the list join step. Moreover, the biggest benefit
the original query, the remaining NN searches need to ex-
of our approach is the reduced number of raw trajectory
pand the search substantially in order to retrieve their clos-
data that need to be retrieved. Our approach yields from
est candidates that also satisfy the range predicate. Here,
two up to three orders of magnitude less trajectory accesses
the cost for range query side 2.5 has being clipped in order
than the R-tree (the graph shows the results in a logarith-
to preserve the detail in the graph. The actual cost is 3,000
mic scale). This is expected, since the R-tree has no way of
index I/Os on average. The problem is exacerbated since
pruning trajectories due to predicate ordering constraints;
a large number of nearest neighbors (twenty in this case)
it does not store such information in the index.

is requested. As the range query increases in size, since
the original twenty nearest neighbor trajectories are all con-
tained in the range, the rest of the searches discover them
very fast. In this case, the index cost for RER-1 increases
due to the extra cost for answering the range query in the
beginning. On the contrary, the trajectory access cost de-
creases since many new trajectories discovered during the

**Number of predicates**
**Number of predicates**
NN searches can be pruned, given the answer of the range
Figure 17: RELEVANTPATTERN: Number of predicates.

query. Alternative RER-2 gave similar results to the orig-inal query, as expected, since the range predicate has no
Performance vs. Range Selectivity. The next experi-
effect on the execution of the ranking algorithm, pruning
ment evaluates the performance with respect to increasing
entries only after they have been loaded from storage.

range predicate selectivity. Figure 18 presents the results.

As expected, when the size of the range increases the index
I/O rises proportionately, since a larger number of candi-
dates are retrieved. Similar observations hold for trajec-
tory accesses as well. Clearly, the CellList can answer STP
queries With Order, by far more efficiently than the R-tree,
and with a structure that is smaller in size

**Range side length**
**Range side length**
OMBINEDPATTERN: Range selectivity.

Conclusion. In general our algorithms yielded very effi-
cient pruning for STP queries, especially when considering
that the only available alternative is the linear scan. The
eager strategy performed the best overall, in all cases, bal-

**Range side length**
**Range side length**
ancing the trajectory access cost and the index overhead.

Figure 18: RELEVANTPATTERN: Range selectivity .

4.2 STP Queries With Order
4.2.2 Nearest Neighbor Queries
For this type of queries we selected a 100

*× *100 uniform
For these queries we used the

*RelevantPatterns *to evalu-
grid and created the corresponding sorted lists per cell,
ate the CellList both using the lazy and the eager strategies.

as described in Section 3.2. We compare our grid based
We also run a simple eager algorithm on a 2-dimensional R-
index against the straightforward approach of using a 2-
tree, with the ranking algorithm described in Section 3.2.2.

dimensional R-tree.

We compared each technique for an increasing number ofpredicates. The results are reported in Figure 19. The lazy
4.2.1 Range Queries
strategy worked the best in this case, requiring a small num-
For this experiment we created a query set that contains
ber of index accesses as well as a very small number of
only range predicates. The queries were created similarly
trajectory accesses. Naturally, delaying trajectory retrieval
to the RELEVANTPATTERNS set, by replacing the NN pred-
in this case is beneficial due to the double pruning based
icates with range predicates. For the R-tree index, assum-
both on lower-bounds and the predicate ordering. It is ev-
ing that the selectivity of the predicates is not known, all
ident that, contrariwise, the eager strategy has three orders
predicates were evaluated in sequence and the intersection
of magnitude more trajectory accesses, since it unnecessar-
of the individual result sets was returned.

ily retrieves trajectories that do not satisfy the order. The R-
Performance vs. Number of Predicates. First, we
tree approach, as predicted in Section 3.2.2, deteriorated to
evaluate the techniques using varying numbers of range
almost a sequential scan of both the index structure and the
predicates, given a fixed range query side length equal to 15
trajectory storage, especially for larger numbers of predi-
miles (with the universe size being 1

*, *000

*× *1

*, *000 miles).

The results are shown in Figure 17. The

*CellList *in the
Conclusion. To conclude, the CellList is a robust solu-
graph corresponds to our proposed technique, and the

*R-*
tion with excellent performance, both for range and near-

*tree *to the 2-dimensional R-tree approach. The CellList has
est neighbor predicates. In particular, the lazy strategy for
effectively reduce the computation and I/O operations per
query, when compared with existing approaches. Finally,
we presented a thorough experimental evaluation. For fu-
ture work we plan to extend the techniques for answering
pattern queries that impose constraints between groups of
predicates, and for including relative temporal constraints

**Number of predicates**
**Number of predicates**
(e.g., 10 minutes before or after, etc.) We will also inves-
Figure 19: RELEVANTPATTERN: Number of predicates.

tigate solutions for environemnts were there is an inherentuncertainty in moving object trajectories [23].

these queries works the best, in contrast to STP queriesWith Time, where the eager strategy was the best alterna-
[1] R. Benetis, C. Jensen, G. Karciauskas, and S. Saltenis. Nearest
neighbor and reverse nearest neighbor queries for moving objects.

In

*IDEAS*, pages 44–53, 2002.

Modelling and expressing complex spatio-temporal queries
[2] V. P. Chakka, A. Everspaugh, and J. M. Patel. Indexing large trajec-
tory data sets with seti. In

*CIDR*, 2003.

has been investigated in [7]. In this paper we use a very
[3] C. du Mouza and P. Rigaux. Mobility patterns. In

*STDBM*, pages
general expression mechanism, that can utilize any previ-
1–8, 2004.

ous definition of spatio-temporal predicates. Applying the
[4] R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms
for middleware. In

*PODS*, pages 102–113, 2001.

incremental ranking algorithms for answering STP queries
[5] H. Ferhatosmanoglu, I. Stanoi, D. Agrawal, and A. El Abbadi. Con-
with

*N N *predicates has been inspired by the Threshold Al-
strained nearest neighbor queries. In

*SSTD*, pages 257–278, 2001.

gorithm (TA) proposed in [4]. The TA algorithm is used for
[6] V. Gaede and O. G¨unther. Multidimensional access methods.

*ACM*
ranking objects with multiple features given any monotonic

*Computing Surveys*, 30(2):170–231, 1998.

[7] R. H. G¨uting, M. H. Bhlen, M. Erwig, C. S. Jensen, N. A. Lorentzos,
preference function. Here, we show how this algorithm can
M. Schneider, and M. Vazirgiannis. A foundation for representing
be applied in the case of spatio-temporal data using index
and querying moving objects.

*TODS*, 25(1):1–42, 2000.

structures instead of materialized sorted lists. Traditional
[8] A. Guttman. R-trees: A dynamic index structure for spatial search-
nearest neighbor queries have been addressed in previous
ing. In

*SIGMOD*, pages 47–57, 1984.

[9] M. Hadjieleftheriou, G. Kollios, V. J. Tsotras, and D. Gunopulos.

work including [1, 5, 10, 20]. None of these approaches
Efficient indexing of spatiotemporal objects. In

*EDBT*, pages 251–
has focused on efficient evaluation of combinations of

*N N*
predicates (with the exception of GNN queries [16]). To
[10] G. R. Hjaltason and H. Samet.

Distance browsing in spatial
the best of our knowledge, no work has appeared for an-
databases.

*TODS*, 24(2):265–318, 1999.

[11] N. Mamoulis, H. Cao, G. Kollios, M. Hadjieleftheriou, Y. Tao, and
swering combinations of spatial predicates with order and
D. W. Cheung. Mining, indexing, and querying historical spatiotem-
without temporal constraints.

poral data. In

*SIGKDD*, pages 236–245, 2004.

Related to the STP range queries with order (after the
[12] N. Mamoulis and M.L. Yiu.

Non-contiguous sequence pattern
queries. In

*EDBT*, pages 783–800, 2004.

grid reduction) is the work in [12] which considers non-
[13] M. F. Mokbel, T. M. Ghanem, and W. G. Aref. Spatio-temporal ac-
contiguous pattern queries on string sequences. However,
cess methods.

*IEEE Data Engineering Bulletin*, 26(2):40–49, 2003.

our structures are more suitable for spatio-temporal data
[14] M. F. Mokbel, X. Xiong, and W. G. Aref. SINA: Scalable incremen-
and can answer more general queries. Mouza and Rigaux
tal processing of continuous queries in spatiotemporal databases. In

*SIGMOD*, 2004.

[3] introduced mobility pattern queries, where patterns are
[15] M. Nascimento, J. Silva, and Y. Theodoridis. Evaluation of access
expressed using regular expressions. This work is a special
structures for discretely moving points.

*Spatio-Temporal Database*
case of STP queries, concentrating on STP queries With

*Management*, pages 171–188, 1999.

Order and Range predicates. The techniques introduced
[16] D. Papadias, Q. Shen, Y. Tao, and K. Mouratidis. Group nearest
neighbor queries. In

*ICDE*, pages 301–312, 2004.

therein cannot handle distance based predicates, neither ex-
[17] W.-C. Peng and M.-S. Chen. Developing data allocation schemes by
plicit temporal constraints. Furthermore, the patterns are
incremental mining of user moving patterns in a mobile computing
limited to predefined ranges, which have been determined
system.

*TKDE*, 15(1):70–85, 2003.

in advance by partitioning the space into areas of interest.

[18] D. Pfoser, C. S. Jensen, and Y. Theodoridis. Novel approaches in
query processing for moving object trajectories. In

*VLDB*, pages
In contrast, here we present more general techniques that
395–406, 2000.

can handle arbitrary query ranges, distance based predi-
[19] K. Porkaew, I. Lazaridis, and S. Mehrotra. Querying mobile objects
cates, and temporal constraints.

in spatio-temporal databases. In

*SSTD*, pages 59–78, 2001.

[20] N. Roussopoulos, S. Kelley, and F. Vincent.

Any trajectory indexing scheme that can answer nearest
queries. In

*SIGMOD*, pages 71–79, 1995.

neighbor, range queries, and other spatial predicates can
[21] Y. Tao and D. Papadias. MV3R-Tree: A spatio-temporal access
be used with the STP query algorithm described here [22,
method for timestamp and interval queries. In

*VLDB*, pages 431–
15, 2, 13, 18, 21]. were there is an inherent uncertainty in
[22] Y. Theodoridis, T. Sellis, A. Papadopoulos, and Y. Manolopoulos.

moving object trajectories [23].

Specifications for efficient indexing in spatiotemporal databases. In

*SSDBM*, pages 123–132, 1998.

[23] G. Trajcevski, O. Wolfson, K. Hinrichs, and S. Chamberlain. Man-
aging uncertainty in moving objects databases.

*TODS*, 29(3):463–
We introduced and formalized a novel type of spatio-
temporal pattern query for trajectories. We designed spe-cialized spatio-temporal index structures and algorithms to

Source: http://hadjieleftheriou.com/papers/vldb05-stp.pdf

FOODDRINKEUROPE GUIDELINES ON REGULATION (EC) NO 1334/2008 ON FLAVOURINGS AND CERTAIN FOOD INGREDIENTS WITH FLAVOURING PROPERTIES FOR USE IN AND ON FOODS Table of Contents Executive SummaryThe present Industry Guidelines on the "Regulation (EC) No 1334/2008 on flavourings and certain food ingredients with flavouring properties for use in and on foods" are intended to provide a common understanding of the major issues to be taken into account by food business operators, flavourings producers and other stakeholders.

Pharmacological Reports Copyright © 2012 2012, 64, 205211 by Institute of Pharmacology Polish Academy of Sciences Influence of the phosphodiesterase type 5inhibitor, sildenafil, on antidepressant-likeactivity of magnesium in the forced swim testin mice Katarzyna Soca³a1, Dorota Nieoczym1, Ewa Poleszak2, Piotr WlaŸ1 1Department of Animal Physiology, Institute of Biology and Biochemistry, Maria Curie-Sk³odowska University,Akademicka 19,PL 20-033 Lublin, Poland