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 T1, came as close as pos- a result, large amounts of spatiotemporal data is produced sible to point B at a later time T2 and then stopped inside daily, typically in the form of trajectories. The need to effi- circle C some time during interval (T3, T4)". 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 T1 and then, as close as the query sequence. An alternative query expression mech- possible from point B at a later time T2". 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 (q1), t1), (NN(q2), t2), (R(r), [t3, t4))}, (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 q1, q2 at times t1, t2, respectively, ordering (STP queries With Order). (2) We propose spe- and crosses region r anytime between [t3, t4).
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, T1), (Q2, T2), . . , (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 P1 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, P1) = 5.5. Trajectory P3 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 P1 cover the query, while those of P2 do not cover points 4 and 5. Given D(Q, P1) = 5.5 and LBD(Q, P2) ≥ 3.1.1 Range Predicate Evaluation 5.7, trajectory P2 can be pruned (any missing MBRs for points 4and 5 should be at least as far as D(q4,5, P1) = 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 trajectoryP (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 P1 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 (q1), t1), . . , (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 Q1,.,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, P2) ≥ i, P2) + D(q4, P1) + D(q5, P1).
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 elseS.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 = {Q1, Q2, . . , 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(r1), . . , 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 L1[i].id 6∈ Lj then break 1), R(r2), . . , 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 L1[i].id in Lj icates. Using this structure the correct answers are retrieved while L1[i].id = Lj[k].id in sorted trajectory identifier order.
if L1[i].id 6= Lj[k].id then break There are two cases where entries from the lists can be U = U ∪ L1[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 P3 crossed cell B at time-instant 3. At the given grid granularity. At the same time, it discretizes time-instant 4 trajectory P1 entered the cell. Trajectory P2 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 {(P1, 4), (P2, 9), (P2, 13), (P3, 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 q1, q2 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 q1 consists only of the entries in cell H, which ever, instead of using the best first search strategy per query contains element Sq (P2, 8). Similarly, the list of q2 con- predicate, the algorithm iteratively en-queues and examines tains entry Sq (P3, 7). The partial distance of P2 from q1 all the cells adjacent to the cell containing the query. For is set to 0, while the pessimistic distance from q2 is equal every query predicate qm a sorted queue of satisfiability to the minimum distance of q2 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 , Dq1,.,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, P2) from the query is thus ready available. Given the above and the expensive nature equal to 0 + M inDist(q2, R) (similarly LBD(Q, P3) = of this distance function, it should be clear now that our 0 + M inDist(q1, H)). In the next phase the algorithm technique will offer substantial improvement over the ex- evaluates all cells adjacent to q1 and q2. Starting with q1 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 q1), with the list of q1 (cell H). Be- fore the merging operation, each cell is joined with q2, 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 (P2, 9). First, we join B with q2 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 (P3, 2) is probed into list q2, 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 q1 becomes (P1, 3 − 8), (P2, 6 − 9), (P3, 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 q2, we join ele- ment SX(P2, 1) with the list of q1, where four entries forP2 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 q2 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 P3 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 P1 and P2 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. InSIGMOD, 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. InSSDBM, 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