=Paper=
{{Paper
|id=None
|storemode=property
|title=TrIMPI: A Data Structure for Efficient Pattern Matching on Moving Objects
|pdfUrl=https://ceur-ws.org/Vol-1020/paper_11.pdf
|volume=Vol-1020
|dblpUrl=https://dblp.org/rec/conf/gvd/PolomskiK13
}}
==TrIMPI: A Data Structure for Efficient Pattern Matching on Moving Objects==
https://ceur-ws.org/Vol-1020/paper_11.pdf
TrIMPI: A Data Structure for Efficient Pattern Matching on
Moving Objects
Tsvetelin Polomski Hans-Joachim Klein
Christian-Albrechts-University at Kiel Christian-Albrechts-University at Kiel
Hermann-Rodewald-Straße 3 Hermann-Rodewald-Straße 3
24118 Kiel 24118 Kiel
tpo@is.informatik.uni-kiel.de hjk@is.informatik.uni-kiel.de
ABSTRACT qualitative description, e.g. return all trajectories where the under-
Managing movement data efficiently often requires the exploita- lying object slowed down (during any time interval) and after that
tion of some indexing scheme. Taking into account the kind of it changed its course. Obviously, the motion properties slowdown
queries issued to the given data, several indexing structures have and course alteration as well as their temporal adjustment can be
been proposed which focus on spatial, temporal or spatio-temporal computed using formal methods. The crucial point is that, even if
data. Since all these approaches consider only raw data of moving an indexing structure is used, the stated properties must be com-
objects, they may be well-suited if the queries of interest contain puted for each trajectory and this results in sequential scan(s) on
concrete trajectories or spatial regions. However, if the query con- the whole trajectory data. Time consuming processing of queries
sists only of a qualitative description of a trajectory, e.g. by stating is not acceptable, however, in a scenario where fast reaction on in-
some properties of the underlying object, sequential scans on the coming data streams is needed. An example of such a situation with
whole trajectory data are necessary to compute the property, even so-called tracks computed from radar and sonar data as input is the
if an indexing structure is available. detection of patterns of skiff movements typical for many piracy
The present paper presents some results of an ongoing work on a attacks [14]. A track comprises the position of an object at a time
data structure for Trajectory Indexing using Motion Property In- moment and can hold additional information e.g. about its current
formation (TrIMPI). The proposed approach is flexible since it al- course and velocity. Gathering the tracks of a single object over a
lows the user to define application-specific properties of trajecto- time interval yields its trajectory over this interval.
ries which have to be used for indexing. Thereby, we show how To address the efficiency problem, we propose an indexing scheme
to efficiently answer queries given in terms of such qualitative de- which is not primarily focused on the “time-position data” of tra-
scriptions. Since the index structure is built on top of ordinary data jectories but uses meta information about them instead.
structures, it can be implemented in arbitrary database management We start with a discussion of related work in Section 2. Section 3
systems. provides some formal definitions on trajectories and their motion
properties. In section 4 we introduce the indexing scheme itself
and illustrate algorithms for querying it. Section 5 summarizes the
Keywords present work and outlines our future work.
Moving object databases, motion patterns, indexing structures
2. RELATED WORK
1. INTRODUCTION AND MOTIVATION In this section we provide a short overview on previous contri-
butions which are related to our approach. We start the section
Most index structures for trajectories considered in the literature
(e.g. [8]) concentrate on (time dependent) positional data, e.g. R- by reviewing classical indexing structures for moving objects data.
Tree [9] or TPR*-Tree [17]. There are different approaches (e.g. Next to this, we show an approach which is similar in general terms
[1], [12]) exploiting transformation functions on the original data to the proposed one and finally we review literature related to se-
mantical aspects of moving objects.
and thereby reducing the indexing overhead through “light ver-
sions” of the trajectories to be indexed. In these approaches only 2.1 Indexing of Spatial, Temporal and Spatio-
stationary data is being handled. In cases where the queries of in-
terest consist of concrete trajectories or polygons covering them,
Temporal Data
such indexing schemata as well as trajectory compression tech- The moving object databases community has developed several
niques (e.g. [1], [6], [10], [12], [13]) may be well-suited. However, data structures for indexing movement data. According to [8], these
there are applications [14] where a query may consist only of a structures can be roughly categorized as structures indexing only
spatial data, also known as spatial access methods (SAM); index-
ing approaches for temporal data, also known as temporal index
structures; and those which manage both - spatial and temporal
data, also known as spatio-temporal index structures. One of the
first structures developed for SAMs is the well-known R-Tree [9].
Several extensions of R-Trees have been provided over the years,
thus yielding a variety of spatio-temporal index structures. An in-
formal schematic overview on these extensions, including also new
25th GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 28.05.2013 - 31.05.2013, Illmenau, Germany. developments as the HTPR*-Tree [7] can be found in [11]. Since
Copyright is held by the author/owner(s). all of the proposed access methods focus mainly on the raw spatio-
temporal data, they are well-suited for queries on history of move- “real time” and use any time domain instead. A time domain is any
ment and predicting new positions of moving objects, or for re- set which is interval scaled and countably infinite. The first re-
turning most similar trajectories to a given one. If a query consists quirement ensures that timestamps can be used for ordering and,
only of a qualitative description, however, all the proposed index- furthermore, that the “delay” between two time assignments can
ing structures are of no use. be determined. The second requirement ensures that we have an
infinite number of “time moments” which can be unambiguously
2.2 Applying Dimensionality Reduction upon indexed by elements of N. In the following we denote a time do-
Indexing - the GEMINI Approach main by T.
The overall approach we consider in this work is similar to the Since objects move in a space, we also need a notion for a spa-
GEMINI (GEneric Multimedia INdexIng method) indexing scheme tial domain. In the following, let S denote the spatial domain. We
presented in [6]. This approach was originally proposed for time require that S is equipped with an adequate metric, such as the Eu-
series and has been applied later for other types of data, e.g. for clidean distance (e.g. for S = R × R), which allows us to measure
motion data in [16]. The main idea behind GEMINI is to reduce the the spatial distance between objects.
dimensionality of the original data before indexing. Therefor, rep- Having the notions of time and space we can define formally the
resentatives of much lower dimensionality are created for the data term trajectory.
(trajectory or time series) to be indexed by using an appropriate
transform and used for indexing. A crucial result in [6] is that the Definition 1. Let T, S and O denote a time domain, a space do-
authors proved that in order to guarantee no false dismissals [12], main and a set of distinct objects, respectively. Then, the trajectory
the exploited transform must retain the distance (or similarity) of τo of an object o ∈ O is a function τo : T → S.
the data to be indexed, that is, the distance between representatives
should not exceed the distance of the original time series. For brevity, we can also write the trajectory of an object o ∈ O
In the mentioned approaches, the authors achieve encouraging re- in the form (o, t0 , s0 ), (o, t1 , s1 ) . . . for those t ∈ T where τo (t) = s is
sults on querying most similar trajectories (or time series) to a given defined. A single element (o, ti , si ) is called the track of object o at
one. However, since the representatives of the original data are tra- time ti .
jectories or time series, respectively, evaluating a query which only
describes a motion behavior would result in the inspection of all 3.2 Motion Patterns
representatives. We consider a motion pattern as a sequence of properties of
trajectories which reveal some characteristics of the behavior of
2.3 Semantical Properties of Movement the underlying moving objects. Such properties may be expressed
Semantical properties of movement data have been considered in through any predicates which are important for the particular anal-
various works, e.g. in [2], [5], and [15]. ysis, such as start, stop, turn, or speedup.
The authors of [2] propose a spatio-temporal representation scheme
for moving objects in the area of video data. The considered rep- Definition 2. Let T be a time domain, T be the set of trajectories
resentation scheme distinguishes between spatio-temporal data of of an object set O over T, and IT be the set of all closed inter-
trajectories and their topological information, and also utilizes in- vals over T. A motion property on T is a function p : 2T × IT →
formation about distances between pairs of objects. The topolog- {true, f alse}.
ical information itself is defined through a set of topological re-
lations operators expressing spatial relations between objects over That is, a motion property is fulfilled for a set of trajectories and
some time interval, including faraway, disjoint, meet, overlap, is- a certain time interval if the appropriate predicate is satisfied. To
included-by/includes and same. illustrate this definition, some examples of motion properties are
In [5], a comprehensive study on the research that has been carried provided below:
out on data mining and visual analysis of movement patterns has
been provided. The authors propose a conceptual framework for • Appearance: Let t ∈ T. Then we define appear(·, ·) as
movement behavior of different moving objects. The extracted be- follows: appear({τo }, [t, t]) = true ⇔ ∀t′ ∈ T : τo (t′ ) ,
havior patterns are classified according to a taxonomy. undefined → t ≤ t′ . That is, an object “appears” only in the
In [15], the authors provide some aspects related to a semantic view “first” moment it is being observed.
of trajectories. They show a conceptual approach for how trajectory
behaviors can be described by predicates that involve movement • Speedup: Let t1 , t2 ∈ T and t1 < t2 . Then speedup(·, ·) is de-
attributes and/or semantic annotations. The provided approach is fined as follows: speedup({τo }, [t1 , t2 ]) = true ⇔ v(τo , t1 ) <
rather informal and considers behavior analysis of moving objects v(τo , t2 ) ∧ ∀t ∈ T : t1 ≤ t ≤ t2 → v(τo , t1 ) ≤ v(τo , t) ≤ v(τo , t2 )
on a general level. where v(τo , t) denotes the velocity of the underlying moving
object o at time t. That is, the predicate speedup is satisfied
for a trajectory and a time interval if and only if the velocity
3. FORMAL BACKGROUND of the underlying object is increasing in the considered time
This section provides the formal notions as well as the definitions interval. Note that the increase may not be strictly mono-
needed throughout the rest of the paper. We start with the term tonic.
trajectory and then direct later our attention to motion properties
and patterns. • Move away: Let t1 , t2 ∈ T and t1 < t2 . Then we define:
moveaway({τo1 , τo2 }, [t1 , t2 ]) = true ⇔ ∀t, t′ ∈ T : t1 ≤ t <
3.1 Trajectories t′ ≤ t2 → dist(τo1 , τo2 , t) < dist(τo1 , τo2 , t′ ) where the term
In our approach we consider the trajectory τo of an object o sim- dist(τo1 , τo2 , t) denotes the distance between the underlying
ply as a function of time which assigns a position to o at any point moving objects o1 and o2 at time t. That is, two objects are
in time. Since time plays only a role for the determination of tem- moving away from each other for a time interval, if their dis-
poral causality between the positions of an object, we abstract from tance is increasing during the considered time interval.
the trajectory data in blocks. This has the advantage that extract-
ing the complete trajectory requires only loading as much blocks as
needed for storing a trajectory.
4.2 Indexing Motion Patterns
For the maintenance of motion patterns we consider two cases -
single motion properties and sequences of motion properties. Stor-
ing single motion properties allows the efficient finding of trajec-
tories which contain the considered motion property. This is ad-
vantageous if the searched property is not often satisfied. Thus, for
each motion property p a “list” DBT p holding all trajectories sat-
isfying this property is maintained. As we shall see in Algorithm
Figure 1: Overview of the index structure 4.3, we have to combine such lists and, thus, a simple unsorted list
would not be very favourable. Therefore, we implement these lists
through B+ -Trees (ordered by the trajectory/object identifiers). An
Using motion properties, a motion pattern of a single trajectory
evaluation of union and intersection of two B+ -Trees with m and n
or a set of trajectories is defined as a sequence of motion properties
leaves can be performed in O(m log m+n m
)[4].
ordered by the time intervals in which they are fulfilled. It is impor-
The search for motion patterns with more than one motion property
tant to note, that this common definition of a motion pattern allows
can be conducted through the single DBT p structures. However, if
multiple occurrences of the same motion property in the sequence.
the query motion pattern is too long, too many intersections of the
In order to get a well-defined notion it has to be required that the
DBT p structures will happen and the resulting trajectories will have
time intervals in which the motion properties are fulfilled are dis-
to be checked for containing properties that match the given order,
joint or that meaningful preferences on the motion properties are
as well. To overcome this problem, sequences of motion properties
specified in order to allow ordering in case the time intervals over-
are stored in an additional B+ -Tree structure DBT . The elements of
lap.
DBT have the form (p, τo ) where p is a motion pattern, and o ∈ O.
To sort the elements of DBT , we apply lexicographical ordering.
4. TRAJECTORY INDEXING USING MO- As a result, sequences with the same prefix are stored consecu-
TION PROPERTIES tively. Thus, storing of motion patterns that are prefixes of other
In this section we explain how the proposed index is being cre- motion patterns can be omitted.
ated and used. Index creation starts with the determination of the 4.3 Building the Index
motion pattern of each trajectory to be indexed. For this purpose,
the motion predicates specified by the user are computed. The re- The algorithm for the index creation is quite simple. It consists
sulting motion patterns are indexed with references to the original primarily of the following steps:
trajectories. • Determine the motion properties for each trajectory τo . Con-
The resulting index is schematically depicted in Figure 1. TrIMPI sider, if needed, a sliding window or some reduction or seg-
consists mainly of a data structure holding the raw trajectory data, menting technique as proposed in [1], [6], [10], [12], [13],
and secondary index structures for maintaining motion patterns. for example. Generate a list f of the motion properties of τo ,
Thereby, we differentiate between indexing single motion proper- ordered by their appearance in τo .
ties and indexing motion patterns.
A query to the index can be stated either through a motion pattern or • Store τo into the trajectory record file.
through a concrete trajectory. The index is searched for motion pat-
terns containing the given one or the computed one, respectively. In • Apply Algorithm 4.1 to f to generate access keys relevant
both cases, the associated trajectories are returned. The following for indexing.
subsections consider the outlined procedures more precisely. • For each generated access key, check whether it is already
4.1 Indexing Trajectory Raw Data contained in the index. If this is not the case, store it in the
index. Link the trajectory record file entry of τo to the access
Since the focus of TrIMPI is not on querying trajectories by ex-
key.
ample, the index structure for the raw trajectory data can be rather
simple. For our implementation, we considered a trajectory record Algorithm 4.1 is used to generate index keys of a pattern. An index
file as proposed by [3]. This structure (Figure 1) stores trajectories key is any subpattern p′ = (p′j )m−1 n−1
j=0 of a pattern p = (pi )i=0 which is
in records of fixed length. The overall structure of the records is as defined as follows:
follows
• For each j ≤ m − 1 exists i ≤ n − 1 such that p′j = pi
IDo next_ptr prev_ptr {track0 , . . . , tracknum−1 } .
• For each j, k such that 0 ≤ j < k ≤ m − 1 exist i, l such that
IDo denotes the identifier of the underlying moving object, next_ptr 0 ≤ i < l ≤ n − 1 and p′j = pi and p′k = pl .
and prev_ptr are references to the appropriate records holding fur-
ther parts of the trajectory, and {track0 , . . . , tracknum−1 } is a list of To generate the list of index keys, algorithm 4.1 proceeds itera-
tracks of a predefined fixed length num. If a record ri for a tra- tively. At each iteration of the outer loop (lines 3 to 16) the algo-
jectory τo gets filled, a new record r j is created for τo holding its rithm considers a single element p of the input sequence f . On the
further tracks. In this case, next_ptrri is set up to point to r j , and one hand, p is being added as an index key to the (interim) result
prev_ptrr j is set up to point to ri . (lines 14 and 15) and on the other hand it is being appended as a
Using a trajectory record file, the data is not completely clustered, suffix to each previously generated index key (inner loop - lines 5
but choosing appropriate record size leads to partial clustering of to 13). Algorithm 4.1 utilizes two sets whose elements are lists of
motion properties - supplist and entries. The set supplist that each trajectory of the interim result has to be checked whether
contains at each iteration the complete set of index keys, includ- it matches the queried pattern (lines 9 to 13).
ing those which are prefixes of other patterns. The set entries is The other special case are queries longer than G (lines 16 to 24). As
built in each iteration of the inner loop (lines 5 to 13) by appending we have seen in algorithm 4.1, in such cases the index keys are cut
the current motion property of the input sequence to any element to prefixes of length G. Thus, the extraction in this case considers
of supplist. Thereby, at line 14 entries holds only index keys the prefix of length G of the query sequence (lines 17) and extracts
which are no prefixes of other index keys. Since the resulting lists the appropriate trajectories (line 18). Since these trajectories may
of index keys are stored in a B+ -Tree by applying a lexicographical still not match the query sequence, e.g. by not fulfilling some of the
order, sequences of motion properties which are prefixes of other properties appearing on a position after G − 1 in the input sequence,
sequences can be omitted. Therefore, the set entries is returned an additional check of the trajectories in the interim result is made
as final result (line 17). (lines 19 to 23).
Since the given procedure may result in the computation of up to The last case to consider are query sequences with length between
2k0 different indexing keys for an input sequence with k0 motion α and G. In these cases, the index DBT holding the index keys is
properties, a global constant G is used to limit the maximal length searched through a call to algorithm 4.2 and the result is returned.
of index keys. Using an appropriate value for G leads to no draw- Finally, the function Match (algorithm 4.4) checks whether a tra-
backs for the application. Furthermore, the proposed querying al-
gorithm can handle queries longer than G. Algorithm 4.3 Querying trajectories with a sequence of arbitrary
length
Algorithm 4.1 Building the indexing keys Require: s is a sequence of motion properties
Require: f is a sequence of motion properties Require: G is the maximal length of stored sequences
Require: G is the maximal length of sequences to be indexed Require: DBT p is the index of the property p
1 function createIndexKeys( f ) Require: 1 ≤ α < G maximal query length for searching single property indexes
2 supplist ← empty set of lists 1 function GetEntries(s)
3 for all a ∈ f do 2 result ← empty set
4 entries ← empty set of lists 3 if |s| < α then
5 for all l ∈ supplist do 4 result ← T
6 new ← empty list 5 for all p ∈ s do
7 if |l| ≤ G then 6 suppset ← DBT p
8 new ← l.append(a) 7 result ← result ∩ suppset
9 else 8 end for
10 new ← l 9 for all τo ∈ result do
11 end if 10 if ! match(τo , s) then
12 entries ← entries ∪ {new} 11 result ← result\{τo }
13 end for 12 end if
14 entries ← entries ∪ {[a]} 13 end for
15 supplist ← entries ∪ supplist 14 else if |s| ≤ G then
16 end for 15 result ← GetEntriesFromDBT (s)
17 return entries 16 else
18 end function 17 k ← s[0..G − 1]
18 result ← GetEntriesFromDBT (k)
19 for all τo ∈ result do
20 if ! match(τo , s) then
4.4 Searching for Motion Patterns 21 result ← result\{τo }
22 end if
Since the index is primarily considered to support queries on se- 23 end for
quences of motion properties, the appropriate algorithm for eval- 24 end if
25 return result
uating such queries given in the following is rather simple. In its 26 end function
“basic” version, query processing is just traversing the index and re-
turning all trajectories referenced by index keys which contain the
queried one (as a subpattern). This procedure is illustrated in algo- jectory τo fulfills a pattern s. For this purpose, the list of motion
rithm 4.2. There are, however, some special cases which have to properties of τo is being generated (line 2). Thereafter, s and the
generated pattern of τo are traversed (lines 5 to 14) so that it can be
checked whether the elements of s can be found in the trajectory
Algorithm 4.2 Basic querying of trajectories with a sequence of
pattern of τo in the same order. In this case the function Match
motion properties
returns true, otherwise it returns false.
Require: s is a sequence of motion properties; |s| ≤ G
Require: DBT is the index containing motion patterns
1 function GetEntriesFromDBT(s) 5. CONCLUSIONS AND OUTLOOK
2 result ← {τo | ∃p s.t. s ≤ p ∧ (p, τo ) ∈ DBT }
3 return result In this paper we provided some first results of an ongoing work
4 end function on an indexing structure for trajectories of moving objects called
TrIMPI. The focus of TrIMPI lies not on indexing spatio-temporal
be taken into account. The first of them considers query sequences data but on the exploitation of motion properties of moving objects.
which are “too short”. As stated in Section 4.2, it can be advan- For this purpose, we provided a formal notion of motion proper-
tageous to evaluate queries containing only few motion properties ties and showed how they form a motion pattern. Furthermore, we
by examination of the index structures for single motion proper- showed how these motion patterns can be used to build a meta in-
ties. To be able to define an application specific notion of “short” dex. Algorithms for querying the index were also provided. In
queries, we provide besides G an additional global parameter α for the next steps, we will finalize the implementation of TrIMPI and
which holds 1 ≤ α < G. In algorithm 4.3, which evaluates queries perform tests in the scenario of the automatic detection of piracy at-
of patterns of arbitrary length, each pattern of length shorter than α tacks mentioned in the Introduction. As a conceptual improvement
is being handled in the described way (lines 3 to 8). It is important of the work provided in this paper, we consider a flexibilisation of
Algorithm 4.4 Checks whether a trajectory matches a motion pat- Notes in Computer Science, pages 26–39. Springer Berlin
tern Heidelberg, 2012.
Require: τo is a valid trajectory [8] R. H. Güting and M. Schneider. Moving Object Databases.
Require: s is a sequence of motion properties
1 function match(τo , s) Data Management Systems. Morgan Kaufmann, 2005.
2 motion_properties ← compute the list of motion properties of τo [9] A. Guttman. R-Trees: a dynamic index structure for spatial
3 index_s ← 0
searching. In Proceedings of the 1984 ACM SIGMOD
4 index_props ← 0
5 while index_props < motion_properties.length do international conference on Management of data, SIGMOD
6 if motion_properties[index_props] = s[index_s] then ’84, pages 47–57, New York, NY, USA, 1984. ACM.
7 index_s ← index_s + 1
[10] J. Hershberger and J. Snoeyink. Speeding Up the
8 else
9 index_props ← index_props + 1 Douglas-Peucker Line-Simplification Algorithm. In
10 end if P. Bresnahan, editor, Proceedings of the 5th International
11 if index_s = s.length then
Symposium on Spatial Data Handling, SDH’92, Charleston,
12 return true
13 end if South Carolina, USA, August 3-7, 1992, pages 134–143.
14 end while University of South Carolina. Humanities and Social
15 return false Sciences Computing Lab, August 1992.
16 end function
[11] C. S. Jensen. TPR-Tree Successors 2000–2012.
http://cs.au.dk/~csj/tpr-tree-successors, 2013.
Last accessed 24.03.2013.
the definition of motion patterns including arbitrary temporal rela-
[12] E. J. Keogh, K. Chakrabarti, M. J. Pazzani, and S. Mehrotra.
tions between motion predicates.
Dimensionality reduction for fast similarity search in large
time series databases. Journal Of Knowledge And
6. ACKNOWLEDGMENTS Information Systems, 3(3):263–286, 2001.
The authors would like to give special thanks to their former stu- [13] E. J. Keogh, S. Chu, D. Hart, and M. J. Pazzani. An online
dent Lasse Stehnken for his help in implementing TrIMPI. algorithm for segmenting time series. In N. Cercone, T. Y.
Lin, and X. Wu, editors, Proceedings of the 2001 IEEE
International Conference on Data Mining, ICDM’01, San
7. REFERENCES Jose, California, USA, 29 November - 2 December 2001,
[1] R. Agrawal, C. Faloutsos, and A. N. Swami. Efficient pages 289–296. IEEE Computer Society, 2001.
similarity search in sequence databases. In D. B. Lomet, [14] T. Polomski and H.-J. Klein. How to Improve Maritime
editor, Proceedings of the 4th International Conference on Situational Awareness using Piracy Attack Patterns. 2013.
Foundations of Data Organization and Algorithms, submitted.
FODO’93, Chicago, Illinois, USA, October 13-15, 1993, [15] S. Spaccapietra and C. Parent. Adding meaning to your steps
volume 730 of Lecture Notes in Computer Science, pages (keynote paper). In M. Jeusfeld, L. Delcambre, and T.-W.
69–84. Springer, 1993. Ling, editors, Conceptual Modeling - ER 2011, 30th
[2] J.-W. Chang, H.-J. Lee, J.-H. Um, S.-M. Kim, and T.-W. International Conference, ER 2011, Brussels, Belgium,
Wang. Content-based retrieval using moving objects’ October 31 - November 3, 2011. Proceedings, ER’11, pages
trajectories in video data. In IADIS International Conference 13–31. Springer, 2011.
Applied Computing, pages 11–18, 2007. [16] Y.-S. Tak, J. Kim, and E. Hwang. Hierarchical querying
[3] J.-W. Chang, M.-S. Song, and J.-H. Um. TMN-Tree: New scheme of human motions for smart home environment. Eng.
trajectory index structure for moving objects in spatial Appl. Artif. Intell., 25(7):1301–1312, Oct. 2012.
networks. In Computer and Information Technology (CIT), [17] Y. Tao, D. Papadias, and J. Sun. The TPR*-tree: an
2010 IEEE 10th International Conference on, pages optimized spatio-temporal access method for predictive
1633–1638. IEEE Computer Society, July 2010. queries. In J. C. Freytag, P. C. Lockemann, S. Abiteboul,
[4] E. D. Demaine, A. López-Ortiz, and J. I. Munro. Adaptive M. J. Carey, P. G. Selinger, and A. Heuer, editors,
set intersections, unions, and differences. In Proceedings of Proceedings of the 29th international conference on Very
the eleventh annual ACM-SIAM symposium on Discrete large data bases - Volume 29, VLDB ’03, pages 790–801.
algorithms, SODA ’00, pages 743–752, Philadelphia, PA, VLDB Endowment, 2003.
USA, 2000. Society for Industrial and Applied Mathematics.
[5] S. Dodge, R. Weibel, and A.-K. Lautenschütz. Towards a
taxonomy of movement patterns. Information Visualization,
7(3):240–252, June 2008.
[6] C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast
subsequence matching in time-series databases. In R. T.
Snodgrass and M. Winslett, editors, Proceedings of the 1994
ACM SIGMOD international conference on Management of
data, SIGMOD ’94, pages 419–429, New York, NY, USA,
1994. ACM. 472940.
[7] Y. Fang, J. Cao, J. Wang, Y. Peng, and W. Song.
HTPR*-Tree: An efficient index for moving objects to
support predictive query and partial history query. In
L. Wang, J. Jiang, J. Lu, L. Hong, and B. Liu, editors,
Web-Age Information Management, volume 7142 of Lecture