1 Introduction

Moving objects databases have been extensively studied in the last decade due to their wide applications such as location-based services and transportation networks. Recently, the topic of moving objects with multiple transportation modes receives increasing attention in the literature [33, 35]. Some researchers build an inference model to discover outdoor transportation modes from raw GPS data (inactive for indoor) such as walking, cycling and bus, e.g., Microsoft’s project Geolife [46, 47]. In a transportation system, advanced trip planning [8] is provided so that the user can specify different modes and constraints for the path. For example, find a trip by bus and walk fulfilling the condition: (i) two bus transfers in maximum, and (ii) the walking distance is less than 300m.

In this context, different environments are considered for moving objects such as road network, public transportation system and pavement areas. We target a complete trajectory that contains not only the location data but also motion modes. In the meantime, pieces of movements with different modes are distinguished and precisely represented. Consider two example trips:

  1. (1)

    Bobby moved from his office room to the building exit, then walked to the parking place, and from there he went home by car.

  2. (2)

    Bobby moved from his office room to the building exit, then walked to a fast food shop for lunch, and came back to the office room.

Throughout the paper, we also use the term generic moving objects to refer to those moving objects. Figure 1 depicts the two trips. Different line types are utilized to distinguish movements with different transportation modes. The two generic moving objects can be abstractly described as follows:

  1. (1)

    m o 1: <Indoor, Walk, Car >;

  2. (2)

    m o 2: <Indoor, Walk, Indoor >.

Fig. 1
figure 1

Moving objects with multiple transportation modes

Full size image

Instead of traveling by car, people can also choose the public transportation system and then we can have a trip like <Indoor, Walk, Bus > or <Indoor, Walk, Taxi >. Most prior research concentrated on a single environment such as free space [20, 34], road network [19, 21] and indoor [22], in which different data types and operators are proposed. But in the real world, the trajectories for humans can cover multiple environments. The database system should manage the complete trip instead of a subtrip limited to one environment. Complete movements have to be maintained in a consistent framework in terms of accurate locations and transportation modes in various environments. Fully recognizing motion modes with location data can enrich the mobility with informative and context knowledge. This is substantially meaningful to analyze travel patterns and behavior of mobile users. In particular, by analyzing the historical movement, routes with high passenger flow can be discovered. Therefore, the schedule in a public transportation system can be adjusted to improve the traffic. In a recommendation or advanced service system, one could discover friends based on location history [48]. This is to understand the correlation between people and locations, and recommendation potential friends in a GIS community by measuring the similarity of trajectories. The result will benefit from knowing precise transportation modes.

This imposes new challenges on database systems regarding the data management as well as efficient query processing. The work of this paper does not start from scratch but is based on [43]. There, a data model is presented to represent moving objects in different environments, in which both outdoor and indoor movements are uniformly treated.

In this paper, we focus on moving objects with multiple transportation modes and provide an efficient method to answer a novel category of queries, called RQTM (range queries with transportation modes). Standard range query is one of the most studied problems in moving objects databases, e.g., [28, 32]. The query contains a time window Q.t and a spatial window (a bounding box) Q.s, and returns all objects that pass through Q.s during Q.t. However, existing techniques only handle a single environment without considering the complete trip such as m o 1 and m o 2. As a result, transportation modes are not processed. In contrast, we manage moving objects in different environments and aim to retrieve a list of trajectories that fulfill not only temporal and spatial conditions but also transportation modes. Consider two example queries below.

  • Q1: Find all people walking through the specified area during [10am, 2pm] on Saturday.

  • Q2: Given a university area R, find all people who pass through R on Friday with the following sequence of transportation modes: <Indoor, Walk, Car >.

Besides spatial and temporal parameters, one can issue queries on a particular transportation mode (Q1) and even imposes a particular order on a set of modes (Q2). In the example, Q1 gets m o 1 and m o 2, assuming that the query region covers the walking area shown in the figure. Suppose that buildings in Fig. 1 include R, Q2 only retrieves m o 2 because m o 1 does not fulfill the condition on transportation modes. In comparison with previous work, RQTM has two noticeable differences. First, a complete trip including several environments is represented and managed in a database system. Existing works focus on one environment and only deal with a subtrip (e.g., the movement in a road network). Consequently, RQTM is not supported. Second, besides time and spatial parameters, RQTM contains an additional condition on transportation modes, which have different cases. Q1 includes one mode and Q2 specifies a sequence of transportation modes. RQTM is useful and important to understand users’ mobility, and the query result can be used to discover classical trajectories and provide advanced trip plannings such as multiple transportation modes.

The brute-force approach to answering RQTM is to access each trajectory and check spatial, temporal and transportation modes to see if they fulfill the query condition. Obviously, the performance is not acceptable for large datasets. To efficiently answer RQTM, the key is to reduce the number of objects to be accessed, i.e., minimize the portion of the dataset processed. Thus, an index structure for generic moving objects is essentially needed. Despite the fact that there is a large amount of indices proposed for trajectories in the literature [9, 10, 23, 31], they only tackle the problem in one environment without addressing transportation modes. However, the property of managing movements with transportation modes is highly desired because the query condition in RQTM contains these pieces of information. This calls for the development of a novel index that is equipped with the capability of distinguishing movements in different environments and accessing them efficiently when a complete trip is handled. To solve the problem, we develop an index structure called TM-RTree (Transportation Mode RTree), which is able to group pieces of movements on temporal, spatial and transportation modes. In other words, the three kinds of data are managed in an integrated way by the TM-RTree.

Based on the proposed index structure, several algorithms are developed for different query conditions, e.g., a single mode (Q1) and a sequence of modes (Q2). In general, the query procedure is composed of two steps: filter and refinement. The former traverses the TM-RTree to find candidate objects and the latter performs the searching step to get the precise value. More importantly, we propose a method to let the index be capable of maintaining the movement with not only a single mode but also a pair of modes following the time order, leading to a more efficient method for answering the query for a sequence of modes. The TM-RTree and related algorithms are implemented in an extensible and open source database system SECONDO to have a practical result for real applications. We perform the experimental evaluation using extensive datasets to demonstrate the efficiency and effectiveness of the proposed technique. The contribution of this paper is summarized as follows:

  • We formulate the problem of RQTM, supporting three kinds of queries on transportation modes: a single mode, multiple modes and a sequence of modes.

  • An index structure called TM-RTree is developed in a system to efficiently manage generic moving objects. We present how to derive the input data for a TM-RTree and the procedure of building such an index.

  • Employing the TM-RTree, several algorithms are proposed to answer different query conditions on transportation modes. In particular, we propose a method that significantly improves the performance for answering a sequence of modes. On average, our method is 6 times faster than the other methods.

  • We carry out extensive experiments to confirm the efficiency and effectiveness of the proposed techniques. The results demonstrate that our method substantially outperforms the other three access methods, four or five times faster on average.

The rest of the paper is organized as follows: The related work is reviewed in Section 2. We define the problem in Section 3. The TM-RTree is introduced in Section 4. Query algorithms are presented in Sections 5, 6 and 7. Experimental evaluation is performed in Sections 8 and 9 concludes the paper.

2 Related work

2.1 Transportation modes

Recently, researchers started to investigate the detection of transportation modes from GPS data based on mobile phone devices. In Microsoft’s project GeoLife, the works [46, 47] aim to discover and infer transportation modes from raw GPS trajectory data. By mining multiple users’ location histories, one can discover the most interesting locations, classical travel sequences and travel experts in a given geo-spatial region. The work in [33] is to determine the transportation modes of an individual outside where five transportation modes are considered: stationary, walking, running, biking and in motorized transport (car, bus, train). Only using GPS information might reduce the detection accuracy, thus the underlying transportation networks are utilized to improve the result. An approach to inferring a user’s mode is proposed in [35] where the method is based on the GPS sensor from the mobile device as well as the knowledge of the underlying transportation network, e.g., bus stops and spatial rails. A trip analysis system is proposed in [26] to support traffic operation planning and transit system design. Such a system, consisting of mobile apps and a centralized analyzer, automatically identifies the travel mode and purpose of the trips sensed by mobile devices. Travel modes including driving, taking bus or on foot are detected by sensing the users’ movement using embedded GPS and accelerometer.

Advanced trip plannings with multiple transportation modes are studied. A data model is proposed in [8] to provide a trip consisting of several transportation modes, e.g., <Walk, Bus, Train >. The user can also specify the constraint on a specific mode such as less than two bus transfers or the length of the walking path is 300 meters in maximum. An interesting query is considered in [5] that computes isochrones in multimodal and schedule-based transport networks. The goal is to find a set of points on a road network, and from them a specific point of interest can be reached within a given time span. Two transportation modes are supported: Walk and Bus.

Combining both outdoor and indoor movements, a data model is proposed in [43] to model moving objects with different transportation modes. Accurate locations in multiple environments are represented, including free space, road network, pavement areas, public transportation system, and indoor. A general location representation is designed and several data types are defined. A group of queries is formulated by an SQL-like language using proposed operators in a relational interface. However, that work primarily focused on data modeling, while range queries considering three factors (spatial, temporal and transportation modes) are not processed and precisely defined. Additionally, there is no index structure for generic moving objects.

2.2 Range queries and moving objects indices

Range queries [17, 24, 37, 39], representing the foundation queries in moving objects databases, have been extensively investigated. Given a query window consisting of a spatial region Q.s and a time interval Q.t, the result is a set of moving objects that are located in Q.s during Q.t. In general, Q.t can also be a time instant. According to environments, the definition of Q.s is different. In free space, a 2D region or a rectangle is used. In a road network, Q.s is a set of road sections, each of which represents a set of disjoint and ordered intervals on a road [13, 32]. Besides range monitoring in outdoor space, techniques for indoor space are also proposed due to different distance functions and positioning technologies [27, 44]. Q.s in indoor space refers to the activation range of a device such as RFID or Bluetooth, which detects and reports the observed objects at a high sampling rate. The paper [40] deals with spatio-temporal range queries over trajectory data, but does not consider transportation modes.

In the last decade, a substantial amount of index structures have been proposed to efficiently access trajectories. A good survey on trajectory indexing and retrieval is given in [25, 49]. Depending on the environment, indices can be classified into three categories: (1) free space; (2) road network; and (3) indoor. In free space, two variations of the R-Tree for polyline indexing are suggested in [31], TB-Tree and STR-Tree, assuming that the motion is piecewise linear, where the TB-tree is to bundle segments from the same trajectory into leaf nodes. The MV3R [36] is a structure combining a standard R-Tree and a variant of the partially persistent R-Tree, supporting both time-stamp and time-interval queries. A two-level indexing structure called SETI is proposed in [10], where the structure decouples the indexing of spatial and temporal dimensions. The paper [29] offers an indexing technique capable of accurately capturing the past, present, and (near) future positions of moving objects. Practically, objects usually move on a pre-defined set of paths as specified by the underlying network, thus a couple of indices for road network are proposed. Since the movement is constrained by the underlying road network, the combination of two-level R-Trees is employed by [13, 16, 30] where the first level is for roads and the second is for trajectories. The paper [32] proposed an index called T-PARINET, combining graph partitioning and a set of composite B +-tree local indices for trajectory data flows. Recently, some index structures for moving objects in a symbolic indoor space [23, 27] are also developed to support range and nearest neighbor queries over indoor objects.

However, previous queries do not consider the condition on transportation modes and those techniques deal with moving objects in one environment, i.e., a portion of the complete movement is managed. The proposed indices only have the capability of grouping objects on temporal and spatial dimensions, but do not manage transportation modes. As a result, existing indices can not prune objects that do not fulfill the condition on transportation modes, degrading the query performance for generic moving objects.

2.3 Spatial keywords search

Given a dataset O, each object o ∈ O is represented by a pair (loc, text) where o.l o c is the spatial location and o.text is the textual description showing the property of such a location, e.g., restaurant, bank. A spatial keywords query q = (loc, text), consisting of a query area and a set of keywords, returns a list of objects in O such that their distances to q.loc are in ascending order and the descriptions contain the query keywords q.text. To efficiently answer the query, several indices [11, 14, 41, 45] are proposed to manage both spatial and textual data in an integrated way. The basic idea is to perform the query on a 2D R-Tree extended with inverted files. In the IR-Tree [11], each leaf node contains a pointer to an inverted file with text descriptions of the objects stored in the node. Each non-leaf node has an identifier for a pseudo text description that is the union of all text descriptions in the entries of the child nodes. Similarly, the entry of a non-leaf or leaf node in the IR 2-Tree [14] is extended to have an item showing the signature of the subtree or an object. The signature is to denote the textual content of all spatial objects in the subtree rooted at the node. The b R ∗-tree [45] summarizes the keywords and stores the keyword MBR in the node to set up more powerful pruning rules. Spatial keyword searching in trajectory databases is studied in [12] in which trajectories contain text descriptions. The user gives a query location and a set of keywords, and the result is a set of trajectories that cover the keywords and have the shortest match distance.

We compare spatial keywords searching with our problem and point out the differences. First, spatial keywords queries deal with spatial data and additional text information, i.e., the two kinds of data are represented separately. In contrast, we seamlessly integrate transportation modes into moving objects and have a compact data representation. That is, the data type for generic moving objects includes the transportation mode information. As a result, all data are managed by the index without additional structures while spatial keywords searching needs an inverted file with text descriptions. Second, our queries include several cases on transportation modes. The user can request the query on a certain mode or multiple modes. Additionally, a particular order can be imposed on a set of modes. In spatial keywords queries, there is no particular order on keywords. Third, Our index has the capability to group objects on transportation modes and manage a pair of modes for two continuous pieces of movements (keeping the time order). This property is not maintained by the proposed indices for spatial keywords search.

3 Problem definition

3.1 Data representation

The problem setting aims to concisely capture the context of the data and queries. The core content is the representation of moving objects with multiple transportation modes. First, established environments are listed in Table 1 and we define a notation for each of them.Footnote 1

Table 1 Notations for environments
Full size table

Each environment consists of a set of geographic objects (GEOBs) representing available places for moving objects. For example, streets and roads are for I r n , and pavement areas represented by polygons are for I r b o . In the public transportation system, I b n comprises bus routes, bus stops and moving buses. Several data types are defined to represent GEOBs, e.g., line and region. In addition, each environment is related to certain transportation modes, e.g., Car for I r n . We summarize all possible values in Def. 3.1.

Definition 3.1

Transportation Modes

T M = {C a r, B u s, W a l k, I n d o o r, M e t r o, T a x i, B i k e}

Due to different environment characteristics such as outdoor and indoor, network-constrained and obstructed space, a general approach to representing the precise location in all cases is proposed. The capability is achieved by means of referencing representation and the method is as follows.

Definition 3.2

Generic Location

\(D_{\underline {gloc}}=\{(oid,(x,y))|oid \in D_{\underline {int}}, x,y \in D_{\underline {real}}\}\)

The location is represented by two parts: (1) an identifier referencing to a GEOB; and (2) the relative location according to that object. This representation has different semantics according to the environment feature. For example, in a road network, oid is a road identifier and (x, ⊥) records the relative location on the road. Given a location in I r b o , we let oid map to a polygon and (x, y) represent the local position inside the polygon. For the location of a bus/metro passenger, one can simply use oid to reference the bus/metro that the traveler takes.

Then, the location of a moving object is represented by a function f g l o c : \(D_{\underline {instant}}\) →\(D_{\underline {gloc}}\). In this paper, we focus on the complete historical movement. Using the method of sliced representation [15], a generic moving object is represented by a sequence of temporal units ordered by time, that is m o = < u 1, u 2, ... , u n >. Each unit defines the movement during a time interval as well as the transportation mode. In detail, we have

$$u_{i} = (i, gl_{1}, gl_{2}, m)(gl_{1},gl_{2} \in D_{\underline{gloc}} \wedge gl_{1}.oid=gl_{2}.oid, m\in \text{TM}), $$

where i denotes the time interval, g l 1, g l 2 are the start and end locations, respectively, and m is the transportation mode. We assume that the object moves linearly during i so that the positions between g l 1 and g l 2 are calculated by a linear function. Using the example trip m o 1 = < I n d o o r, W a l k, C a r > in the introduction, the units record ids for (1) rooms; (2) pavement areas; (3) roads. The actual locations are identified by g l 1 and g l 2.

3.2 RQTM

To compare locations of different environments in a consistent system, we define an operator freespace: \(D_{\underline {gloc}}\) →\(D_{\underline {point}}\) that maps a general location to free space. The meaning of such an operator depends on the environment, explained in the following. Given a location (o i d, (x, ⊥)) in I r n , we map such a location to free space by a road line with the identifier oid and the relative position x on that road. Similarly, the position on a bus route is also mapped to free space. In I r b o , we transform the local position (x, y) in the referenced polygon (with the oid) to the global space. For an indoor location, we omit the height value above the ground floor and project the location into 2D free space.

Let M(m o, T) = < [m 1, m 2, ... , m k ] > (m i ∈ TM, i ∈ [1, k]) return a sequence of transportation modes for mo during a time interval T. The result can be one mode or several modes. In the context of generic moving objects, the definition of range queries is given in the following.

Definition 3.3

The query is described by Q(t, s, m) where t defines a time interval, s denotes a 2D spatial bounding box, and m represents a set of transportation modes. The result is a set of trajectories {m o 1, m o 2, ... , m o n } where for each m o i (i ∈ [1, n]):

  1. (i)

    |Q.m| = 1, then ∃T ⊆ Q.t such that M(m o i , T) = Q.m and ∀t′ ∈ T : freespace(f g l o c (t′)) ∈ Q.s;

  2. (ii)

    |Q.m| ≥2, then ∀m i ∈ Q.m, ∃ T ⊆ Q.t such that M(m o i , T) = m i and ∀t′ ∈ T:freespace(f g l o c (t′)) ∈ Q.s;

  3. (iii)

    Q.m = < [m 1, m 2, ... , m l ] >, then exists T 1 < T 2 < ... < T l such that ∀i ∈ [1, l]:T i ⊆ Q.t ∧ M(m o i , T 1) = m 1, M(m o i , T 2) = m 2, ... , M(m o i , T l ) = m l ∧ T i , T i+1 are continuous, and ∀t′ ∈ T i : freespace(f g l o c [(t′)) ∈ Q.s.

Since the meanings of spatial and temporal parameters are straightforward, we give more description about Q.m as several cases are involved. This parameter can be either one mode (case (i)) or several modes. If Q.m represents several modes, they can be specified by a certain order (case (iii)) or without any order (case (ii)). We show examples for each case as below.Footnote 2

  • Who rode a bicycle through the central park on Sunday?

    • Q.t: Sunday

    • Q.s: park area

    • Q.m: Bike

  • Find all people passing through the city center by bus and walking on Saturday.

    • Q.t: Saturday

    • Q.s: city center

    • Q.m: {B u s, W a l k}

  • Who arrived by taxi at the university on Friday?

    • Q.t: Friday

    • Q.s: university area

    • Q.m: <Taxi, Walk, Indoor >

Compared with traditional range queries, RQTM contains one more parameter on transportation modes, the information of which is included by the data type for moving objects. Therefore, the query performance can be improved if the index can manage the data. Based on this motivation, we present the TM-RTree in the next section. For clarity, we summarize main notations used in the paper in Table 2.

Table 2 Summary of notations
Full size table

4 The TM-RTree

4.1 Input data

To efficiently answer RQTM, we develop an index based on a 3D R-tree [38]. The key idea of R-tree is to group nearby objects and represent them with their minimum bounding boxes in the next higher level of the tree. We intend to group pieces of movements with the locality on three factors: temporal, spatial and mode. The proposed structure TM-RTree is built on pieces of movements, each of which represents a subtrip of a generic moving object and only includes one transportation mode. To achieve the goal, we create a set of so-called movement tuples for each generic moving object and repeat the same procedure for all moving objects. Afterwards, the index is built on these movement tuples.

Definition 4.1

Movement Tuples

A movement tuple mt is derived from a subtrip of mo, represented by a three-tuple (t r a j_i d, box, m) where t r a j_i d (∈ \(D_{\underline {int}})\) records the trajectory identifier, box stores a 3D box built on temporal and spatial data, and m (∈ TM) refers to the transportation mode. The subtrip includes only one mode.

We present how to retrieve movement tuples in the following. Recalling the representation of mo, a unit u i (∈ mo) records a subtrip where the location is represented by referencing to a GEOB. One can simply build a movement tuple for each u i . However, this method results in the spatial locality of tree nodes being not well maintained as the bounding box sizes for different movement tuples have a large deviation. The spatial range for each u i depends on the referenced GEOB. For example, u i can be a bus trip, a car movement or an indoor trip. Some are in a small spatial range such as indoor trips or a short distance walking, but others are in a large scale such as traveling on a long road or a bus trip.

To solve the problem, we develop a method to (i) minimize the deviation of spatial range (good locality in TM-RTree nodes) and (ii) reduce the quantity of produced movement tuples. Basically, the procedure is to access each unit in mo, collect one or several units as one subtrip and build a movement tuple on the subtrip. Depending on transportation modes (environments), the methods are different. We use U(m o, m) to denote a set of continuous units from mo with the mode m (∈ TM) and Len (U(m o, m)) to show the path length of such a subtrip, respectively.

  • I r n : In this environment, we collect a set of units as one group U(m o, m)(m ∈ {C a r, T a x i, B i k e}) fulfilling the condition that Len (U(m o, m)) does not exceed a threshold l, e.g., 1000m. Then, a movement tuple is created on U(m o, m).

  • I r b o : Using the same threshold l as I r n , we directly build a movement tuple on U(m o, Walk ) if Len(U(m o, Walk )) < l. Otherwise, a new movement tuple will be created.

  • I b n (I m n ): Using the bus network, U(m o, Bus ) references to a unit recording the bus id as well as the start and end bus stops of such a trip. We split the movement into several pieces, each of which represents the trip between two adjacent stops and is used to create a movement tuple.

  • I i n d o o r : Since the spatial range of a building is in a small scale, we create a movement tuple on U(m o, Indoor ), which represents a complete indoor trip such as first from the office room to the corridor and then to the staircase. We perform the union on those pieces and get the movement tuple.

A movement tuple manages temporal and spatial data as well as the transportation mode. The value denotes either a piece of the complete trip or the union of several pieces . We apply the procedure for all generic moving objects and get a set of movement tuples, denoted by MT, to be the input for a TM-RTree. Using the example trips m o 1 and m o 2, Fig. 2 shows the resulting movement tuples. To be concise, we only show the mode in each mt and omit the other information. For m o 1, we get seven movement tuples: {m t 1(I n d o o r), m t 2(W a l k), ... , m t 7(C a r)}. For m o 2, we have \(\{mt_{1}^{\prime }(Indoor), mt_{2}^{\prime } (Walk), mt_{3}^{\prime }(Indoor)\}\).

Fig. 2
figure 2

MT on m o 1 and m o 2

Full size image

In order to have a good locality for TM-RTree nodes, before building the index we process MT as follows. First, the time range for all movement tuples is divided into a set of intervals and each mt is set an id for its time interval. For example, if all moving objects represent one week movement, one can set 12 (or 24) hours as one interval. Second, the space is partitioned into a set of equal size cells represented by rectangles, and each mt is assigned two values cellx and celly to show x and y positions of the cell where mt is located. Third, we sort movement tuples in the following order: (1) time interval id; (2) cellx, celly; (3) m t.m, and these sorted movement tuples are the input for a TM-RTree.Footnote 3

4.2 TM-RTree nodes

In addition to spatial and temporal boxes, each node in a TM-RTree maintains the information of transportation modes. Thus, a node has the form:

  1. 1.

    MBR: the bounding box that contains temporal and spatial data in the subtree below.

  2. 2.

    ObjPtr: an array of entries pointing to child nodes or objects.

  3. 3.

    M: an integer indicating transportation modes represented by the subtree.

In a TM-RTree, entries in non-leaf nodes are pointers to subtrees. In a leaf node, an entry references to a movement tuple. To preserve the proximity of transportation modes, we only store movement tuples with the same mode in a leaf node. Correspondingly, M indicates one transportation mode in such a node. In a non-leaf node, the value of M is the union of modes contained by its sub-trees, denoting either a single mode (all son nodes have the same mode) or a set of modes. The method of keeping modes in nodes benefits the query processing because nodes that do not contain qualified transportation modes can be pruned when traversing the index. In consequence, the following lemma is used.

Lemma 1

Given a node N in a TM-RTree, let tm(N.M) (⊆ TM ) return the set of modes. Then, tm (N.M) \(\cap Q.m = \varnothing \Rightarrow \) N can be pruned.

Next, we introduce in detail how transportation modes are represented by M. A bit in M is set for one mode, which is assigned a value as an index to locate the bit. We mark the bit true indicating the existence of such a mode and false for nonexistence. Suppose that the least significant (right-most) seven bits are used for the modes in Def. 3.1. We assign 0 for Car as the bit index, 1 for Bus, 2 for Walk and so on. Table 3 shows the bit value for each mode. For example, m o 1 containing modes {I n d o o r, W a l k, C a r} defines the value 11 (binary 0001101). This representation incurs little storage overhead and results in a fast method of checking transportation modes due to the relatively high speed of bitmap operations. Figure 3 shows an example of TM-RTree nodes using movement tuples in Fig. 2.

Table 3 Bit values for modes
Full size table
Fig. 3
figure 3

Example of TM-RTree nodes

Full size image

4.3 Insertion algorithm

We build the TM-RTree by a bulkload method [6, 7], which works as follows. The index retrieves a set of sorted movement tuples and puts them into a leaf node until one of the following things occurs:

  • the leaf node is full;

  • the coming movement tuple contains a new transportation mode.

If the case happens, the current leaf node is inserted into a node at the higher level and a new leaf node will be created. We do not consider the distance deviation between the new box and the current bounding box of the leaf node when splitting a leaf node. The reason is, when creating movement tuples, we already process the spatial and time ranges for size controlling by defining the time interval for sorting and the threshold for splitting the movement, see Section 4.1.

Following this procedure, the index is built in a bottm-up way. The method of inserting movement tuples into the TM-RTree is shown in Algorithm 1. An important aspect is that only movement tuples with the same transportation mode are maintained in a leaf node, keeping the proximity of objects.

figure d

After inserting all movement tuples, we need to update the mode value, especially non-leaf nodes. The reason is some operations such as splitting and adjusting are performed on these nodes when building the TM-RTree and modes are changed after that. Algorithm 2 illustrates the pseudo code. The procedure is straightforward for a leaf node. For a non-leaf node, the value depends on its son nodes. We iteratively call the same procedure for each son node and perform the union to update M. The mode value is updated in a bottom-up manner, and is returned when all son nodes are processed. To update the complete tree, we call the function UpdateMode by taking the root node as input. Suppose that there are totally n nodes in a TM-RTree, the time complexity of UpdateMode is O(n) as each node is visited once.

figure e

5 Single transportation mode

We first consider a single mode in the query condition, case (i) in Def. 3.3. Applying the TM-RTree, the query procedure follows a two-phase approach: filter and refinement. The filter step accesses the TM-RTree to find candidate objects. In the refinement step, the accurate value for each object is checked and a set of trajectory ids is returned as the result. We give the pseudo code in Algorithm 3.

figure f

In the beginning, the filter step (Algorithm 4) is called. We create a 3D query box based on Q.t and Q.s. Then, starting from the root node, we traverse the TM-RTree in breadth-first search to examine nodes according to the query condition.

figure g

A list L is used to store TM-RTree nodes, initialized by the root node. Given a node N i , tm(N i .M) (⊆ TM) returns the transportation modes that the node represents (Lemma 1 in Section 4.2). If Q.m ∈ tm(N i .M), we open such a node and proceed to check spatial and temporal conditions. For each entry in N i , we check whether the box of the child node intersects the query box. If N i is a leaf node (only contains one mode), we insert qualified pointers (tuple ids for movement tuples) into the candidate list CL. If N i is a non-leaf node, its child nodes will be inserted into L for further consideration if their boxes intersect the query box. During the procedure, nodes that do not fulfill conditions on spatial, temporal and modes are pruned.

In the refinement step, we use a binary tree Tr with the key traj_id to hold the result. The notation SubTrip(mt) is used to denote the subtrip that a movement tuple corresponds to. For each candidate from CL, we get the movement tuple and check the precise value for spatial and temporal data. The transportation mode is already determined in the filter step. If SubTrip(mt) satisfies spatial and temporal conditions, we insert mt.traj_id into Tr if such an object does not exist in Tr. Otherwise, mt is ignored. A moving object includes a set of movement tuples and several of them can fulfill the query condition. For example, assuming Q.m = C a r, {m t 4, m t 5, m t 6, m t 7} from m o 1 (Fig. 2) are all located in Q.s during Q.t. It is not necessary to access all of them if m o 1 already satisfies the query condition. Finally, we traverse Tr to collect the result.

6 Multiple modes

The goal is to find a list of trajectories, each of which contains all transportation modes requested by Q.m. We also apply the filter and refinement method, and give the algorithm in Algorithm 5. Since the filter step is similar as the procedure for answering a single mode, we omit the algorithm RQMul_Filter(TM-RTree, Q). The only exception is, as Q.m includes multiple values, the filter step here needs to examine the existence of each mode contained by Q.m. If a TM-RTree node includes one mode in Q.m, such a node has to be further considered.

figure h

The refinement step is as follows. We use a binary tree Tr to hold candidates where the node in Tr has the form (traj_id, modebits). The first value is a key and the second is a bitmap that marks corresponding bits for transportation modes. For each candidate mt, the spatial and temporal conditions are first examined. Afterwards, we determine whether mt is to be inserted into Tr or not. If the key m t.traj_id does not exist in Tr, a new node is created and inserted into Tr. For an existing object in Tr, there are two possibilities. Case (i): such a trajectory already satisfies the query condition. That is, all bits of Q.m are marked true. Then, this candidate does not have to be processed. Case (ii): if the corresponding bit for m t.m is false, we mark the value. Finally, we traverse Tr to produce the result. For each node n i in Tr, if |b i t m a p[n i ]| = |Q.m|, such a trajectory satisfies the query condition and is returned.

Figure 4 gives an example to illustrate the refinement step. For simplicity, we focus on processing transportation modes. Assume that Q.m = {W a l k, I n d o o r}. At the current state there are some objects in Tr including m o 1 (Fig. 4a), for which only the mode Indoor (b i t m a p = 0001000) is found from the processed movement tuples. Suppose that the candidates in CL are \(\{mt_{2}(Walk), mt_{1}^{\prime }(Indoor), mt_{2}^{\prime }(\textit {Walk}), mt_{3}^{\prime }(Indoor)\}\), and they all satisfy spatial and temporal conditions. We explain how to process them regarding transportation modes. First, m t 2(Walk) is received from the list. As m o 1 already exists in Tr, we check the bitmap and mark the Walk bit. m o 1 will be returned because all requested modes are found (Fig. 4b). Second, we get \(mt_{1}^{\prime }\)(Indoor)(∈ m o 2), which is not in Tr. We insert a new node (m o 2, 0001000) into an appropriate position in the tree, see Fig. 4c. Next, another movement tuple \(mt_{2}^{\prime }\) from m o 2 is taken from CL. Correspondingly, the bit for Walk is marked true and we have (m o 2, 0001100), shown in Fig. 4d. Such a node fulfills the query condition and will be returned. Finally, we derive \(mt_{3}^{\prime }\)(Indoor) (∈ m o 2) and ignore it because the trajectory already satisfies the condition.

Fig. 4
figure 4

Example of the refinement step

Full size image

7 A sequence of transportation modes

We proceed to consider the case that the user imposes a particular order on a set of modes. First, we introduce the baseline method. Then, we develop a method to let the index be capable of maintaining a pair of modes following the time order, resulting in a more efficient method to answer the query.

7.1 Baseline method

Following the filter-refinement step, we can directly employ the TM-RTree to first prune movements that do not contain transportation modes requested by Q.m. The filter step is the same as the procedure for multiple modes. Given a node N i in a TM-RTree, if N i .M does not contain any mode in Q.m, N i is pruned. Next, we check the precise value of spatial and temporal data for candidate objects. In comparison with the refinement step before, there are some differences here. Since Q.m refers to a sequence of modes, we need to maintain the time order on transportation modes. Assuming that Q.m = < C a r, W a l k, I n d o o r>, movement tuples {m t 1(I n d o o r),mt2(W a l k), m t 3(W a l k), m t 4(C a r)} (from m o 1) are in the candidate list. Suppose that they are located in Q.s during Q.t. Although m o 1 contains all modes requested by Q.m, we need to check the time order on transportation modes to see if they are equal to the query condition. In the example here, m o 1 should not be returned because from movement tuples we get the sequence M(m o 1, Q.t) = < Indoor, Walk, Car >, which is not equal to Q.m.

To maintain the time order, we propose the concept temporal mode, which stores transportation modes with time intervals. The definition is given below.

Definition 7.1

Temporal Mode

\(UMode \!= \{(i, m)|i \in D_{\underline {interval}}, m\in TM\}\)

\(D_{\underline {tmode}} ~= \{<u_{1}, u_{2},...,u_{n}>|n \geq 1,n \in D_{\underline {int}}, and \forall i \in [1,n], u_{i} \in UMode \}\)

The temporal mode consists of a sequence of units, each of which records a time interval and a transportation mode. To keep candidate objects in the refinement, a binary tree Tr is employed in which each node has the form (traj_id, T_Mode, s) (T_Mode ∈ \(D_{\underline {tmode}}\), \(s \in D_{\underline {bool}}\)). The first is the key, the second maintains transportation modes following the time order and the third records the status of such an object. For each mt from the candidate list, after checking spatial and temporal conditions, we insert a new node into Tr if mt.traj_id does not exist. Otherwise, we update T_Mode for the current mt. For the two elements in a temporal mode unit, the time interval is from one dimension of m t.b o x and the transportation mode is from m t.m. Afterwards, we check whether T_Mode satisfies Q.m. If yes, we modify the status of such a node, s = t r u e. Then, this node will be returned as a result and movement tuples coming later with the same key do not have to be processed.

7.2 A pair of modes

According to the study in [46], the walk segment is an important part for moving objects with multiple transportation modes as such a segment builds the connection between movements with different motion modes. Usually people do not directly switch from Car to Bus or from Indoor to Metro because a short distance walking is needed. The property of capturing transportation modes following the time order in a TM-RTree is crucial to efficiently process a sequence of modes. Motivated by this, we extend the semantic meaning of m t.m (Def. 4.1) to represent not only a single mode but also a pair of modes < m 1, m 2 > (m 1, m 2 ∈ TM and m 1 ≠ m 2). Such a pair fulfills the following condition: (i) the movement with m 1 appears before m 2; and (ii) m 1 = W a l k or m 2 = W a l k. Since the number of modes (Def. 3.1 in Section 3.1) is finite, we can determine the set for all possible pairs of modes. That is, we combine Walk with another mode and treat them as one transportation mode. As a consequence, two modes are kept in such a value and the time order on them is also maintained. This results in a new and more efficient method to answer the query.

The method is as follows. We get a new mode set excluding Walk, T M′ = T M∖ {W a l k}. Depending on the time order, there are two cases for a pair of modes: (i) < W a l k, m′>(m′ ∈ T M′); and (ii) < m′, W a l k > (m′ ∈ T M′), e.g., < W a l k, C a r > or < W a l k, B u s >. For each kind of combinations, an integer bit is used to represent the value. Let I(m)(m ∈ T M) return the bit for a single mode. In case (i), we let |T M|+I(m′)(m′ ∈ T M′) be the bit for such a pair, and in case (ii) we let 2 × |T M|+I(m′)(m′ ∈ T M′) return the bit. Plus the number of bit values for a single mode, we need 2 × (|T M|−1)+|T M| = 19 values in total (< Walk, Walk > is not required). As we use a 32 bits integer, m t.m is still available after the extension. Table 4 lists the bit for each mode value. For the pair (Walk, Walk), we keep the bit to have a simple value assignment system. The definition of transportation modes is extended and the new one is given in Def. 7.2.

Table 4 Bit values for modes: an extension
Full size table

Definition 7.2

Extended Transportation Modes

TM_Ext = TM ∪{< Walk, m′>|m′ ∈ T M′} ∪ {< m′, Walk >|m′ ∈ T M′}, where T M′ = TM ∖{Walk }

7.3 Revisit movement tuples

After the mode extension, the procedure of getting movement tuples is modified accordingly. Besides movement tuples for a single mode, a pair of modes are to be represented. As mentioned above, Walk is the only value connecting two different modes. Compared with the previous procedure of getting movement tuples (introduced in Section 4.1), the difference is that we merge two continuous units with different modes and represent them as one movement tuple. Given a sequence of units < u 1, u 2, ... , u n >, we create a movement tuple for u i and u i+1 if (1) u i = m′(∈ T M′) and u i+1 = W a l k; or (2) u i = W a l k and u i+1 = m′(∈ T M′). Using m o 1 as an example, originally, the movement tuples are {m t 1(I n d o o r), m t 2(W a l k), m t 3(W a l k), m t 4(C a r), ... , m t 7(C a r)}. Now, the new movement tuples are {m t a (< I n d o o r, W a l k >), m t b (< W a l k, C a r >), m t c (C a r), m t d (C a r), m t e (C a r)}. The old four movement tuples {m t 1, m t 2, m t 3, m t 4} are merged into two new movement tuples {m t a , m t b }, each of which represents the movement with a pair of modes. Several movement tuples with the mode Car are also created for m o 1. They are produced by the same method as before and fulfill the condition on the path length.

Considering m o 2, before the extension we have \(\{mt_{1}^{\prime }\)(Indoor), \(mt_{2}^{\prime }\) (Walk), \(mt_{3}^{\prime }\)(Indoor) }. One can merge \(mt_{1}^{\prime }\) and \(mt_{2}^{\prime }\) as one movement tuple with the mode < Indoor, Walk > and leave \(mt_{3}^{\prime }\) as another movement tuple. However, this causes that such a pair < Walk, Indoor > (\(mt_{2}^{\prime }\) and \(mt_{3}^{\prime }\)) is missing in the representation, leading to extra work in the future to find such a sequence. To overcome the shortcoming, we split the walk movement into two parts, each of which is combined with another movement. Therefore, we have \(\{mt_{a}^{\prime }(<Indoor, Walk>), mt_{b}^{\prime }(<Walk, Indoor>)\}\) as new movement tuples. If the walk movement is a long trip and represented by several units, we get the result \(\{mt_{a}^{\prime }(<Indoor, Walk>), mt_{b}^{\prime }(Walk), mt_{c}^{\prime }(<Walk, Indoor>)\}\) where the first and last walk units are combined with another movement. The rest walking units are represented as one movement tuple if the path length does not exceed the threshold. Otherwise, more than one movement tuple are created.

Next, we discuss the procedure of building a TM-RTree that supports a pair of modes. In total, there are three groups of transportation modes represented by movement tuples: (1) m ∈ TM; (2) < W a l k, m′>(m′ ∈ T M′); and (3) < m′, W a l k >(m′ ∈ T M′). For each possible value, a unique integer is assigned and movement tuples are sorted according to this value. We keep the property that a leaf node only contains movement tuples with the same mode. Although we extend the semantic meaning of the mode integer and modify the method of producing movement tuples, the algorithm of creating the index is the same as before. The new feature is expressed by the mode integer in each TM-RTree node.

Due to the semantic extension, the query algorithms for a single mode and multiple modes have to be modified, i.e., the procedure of transportation modes examination. In the filter step, given a leaf node N L , if N L .M denotes a single mode (∈ TM), we can prune the node if (i) tm (N L .M) ≠ Q.m for answering a single mode and (ii) tm (N L .M) ∉ Q.m for answering multiple modes. However, if N L .M represents a pair of modes, we can only prune N L if tm \((N_{L}.M) \cap Q.m = \varnothing \). In the refinement step, since the movement tuple may correspond to a trip with two modes, one has to extract a part of the trip if only one mode is requested by Q.m. Spatial and temporal checking is performed on the extracted part instead of the whole trip.

7.4 The algorithm

We present the algorithm that uses the TM-RTree capable of maintaining a pair of modes. First, the filter step is introduced. Given a node N i , we compare the modes contained by N i .M with Q.m to see if N i is to be pruned or not. Since Q.m = < m 1, m 2, ... , m l > represents a sequence of modes, instead of checking the existence of each m i in N i .M, we process Q.m as follows. Each two continuous modes are combined as a pair, that is Q.m′ = {< m 1, m 2 >, < m 2, m 3 >, ... , < m l−1, m l >}. Then, for each node, we check the existence of each pair in Q.m′. This can significantly improve the query performance. Many leaf nodes containing a single mode are pruned, as only nodes containing a pair of modes in Q.m′ are further considered. Some movement tuples recording a single mode may contain one mode from Q.m, but such a value is included by another movement tuple with a pair of modes.

For example, consider that leaf nodes \(\{{N_{L}^{1}}(<\) Indoor, Walk \(>), {N_{L}^{2}}\)(Walk), \({N_{L}^{3}}\)(Walk, Car) } are to be processed. Given that Q.m = < Indoor, Walk, Car >, we have Q.m′ = {< Indoor, Walk >, < Walk, Car >}, then the leaf node \({N_{L}^{2}}\) is to be pruned. Remarkably, this can prune many leaf nodes during the query processing (e.g., a node contains the mode Car) and improve the performance. Applying Lemma 1 in Section 4.2, a function is used to check the modes between N i and Q.m′. If the result is true, N i will be further considered. Otherwise, N i is pruned. We give the function in Algorithm 6. The filter step is almost the same as Algorithm 4 except that line 6 is replaced by CheckMode.

figure i

We give the algorithm in Algorithm 7 where the detailed procedure of the filter step is omitted. In the refinement step, a binary tree Tr is employed to store candidates. The field T_Mode in Tr is to maintain the time order on transportation modes. Definition 7.1 is extended to include a pair of modes, that is

Definition 7.3

UMode \(= \{(i, m)|i \in D_{\underline {interval}}, m\in TM\_Ext\}\)

8 Performance evaluation

We report experimental results in this section. The implementation is developed in an extensible database system Secondo [18] and programmed in C/C++. A standard PC (Intel(R) Core(TM) i7-4770CPU, 3.4GHz, 8GB memory, 2TB hard disk) running Suse Linux 13.1 (32 bits, kernel version 3.11.6) is used.

8.1 Datasets

We utilize a tool called MWGen [42] to create generic moving objects. Such a tool takes in roads and some public floor plans (e.g., office building [4], hotel [3]), then creates the underlying environments including road network, pavement areas, bus network, metro network and a set of buildings. Afterwards, moving objects are generated based on the result of trip planning over different environments. In the experiment, we use road datasets of Berlin [1] and Houston [2], shown in Fig. 5a, and eight floor plans in total (listed in [42]). Each trip may contain several transportation modes and possible values are listed in Fig. 5b.

figure j
Fig. 5
figure 5

The statistics of datasets

Full size image

The whole time period for moving objects is four weeks and the statistics are reported in Fig. 5c. We give a notation for each dataset describing the road data and the number of moving objects. The notation B40K means 40k moving objects in Berlin, B200K means 200k moving objects in Berlin, and so on. The precise number of moving objects is provided in the column Trips No. |M T| shows the number (millions) of produced movement tuples from trajectories and |I| says the average number of units per trip. The size of disk storage for moving objects is also given.

8.2 Competing methods

We compare the performance between the TM-RTree and the other three indices, AD-RTree (Adaptive RTree), 3D-RTree and 4D-RTree. Correspondingly, the query algorithms employing the AD-RTree, the 3D-RTree and the 4D-RTree are also implemented in the system. The AD-RTree is based on a 3D-RTree and the structure adds a value in each node to store transportation modes contained by its sons (or objects). Such an index simply stores the data of transportation modes in a node, but does not group objects on transportation modes. A leaf node does not hold the condition that only movement tuples with the same mode are contained. Instead, objects with different transportation modes are inserted, which is different from the TM-RTree. In addition, a sequence of transportation modes is not maintained by the AD-RTree.

The 3D-RTree manages spatial and temporal data without supporting transportation modes. This index does not have the capability of pruning objects that do not contain requested transportation modes, resulting in the weak pruning ability in the filter step. The refinement step checks transportation modes for each candidate. The 4D-RTree treats transportation modes as one dimension, and the mode is implemented by an integer. In order to create a 4D bounding box on movement tuples, we employ an epsilon and represent the transportation mode by an range instead of an integer. The bounding box is built on time, x, y and mode, and the 4D-RTree is created in a bulkload way.

8.3 Experimental setup

In order to have a good shape of the index, we perform some experiments to set appropriate values for the sizes of the time interval S t and the spatial cell S c , which are used to process movement tuples before sorting. This experiment is conducted on datasets B500K and H300K (not listed above), and several possible values are tested (e.g., S t = 12 h or 24 h, S c = 4000.0 or 5000.0). From the result, we find that the following settings achieve the best performance: (1) S t = 24 h; and (2) S c = 6000.0 for Berlin and S c = 20000.0 for Houston. In addition, the threshold l used for splitting outdoor movements (see Section 4.1) is also determined by testing different values, and we get l = 1500.0 for Berlin and l = 2000.0 for the best performance. Therefore, we choose those values in the following experiments. Investigating these values in a deep (theoretical) way is out of scope of this paper.

We report the settings of query parameters in Fig. 6. The values of temporal and spatial parameters are set according to the overall range. The numbers in bold are standard settings. When we vary the value of spatial (temporal) parameter to evaluate the impact on the performance, the other parameter is set as the standard value. A notation is defined for each kind of Q.m, summarized in Table 5.

Fig. 6
figure 6

Query parameters settings

Full size image
Table 5 Notations for queries
Full size table

For the sake of easy description, we define a particular set of transportation modes.

Definition 8.1

Vehicle Transportation Modes

TM v = {B u s, M e t r o, T a x i, C a r, B i k e}

The settings for transportation modes are shown in Fig. 6b. For Q s i n , a mode from TM is randomly selected for one query. If several modes are requested, we let |Q.m| be two or three because usually a person does not have too many modes during his trip. If |Q.m| = 2, we let the two values be randomly chosen among TM excluding the case that both modes are vehicles. If |Q.m| = 3, we let the result be {Indoor, Walk } plus a vehicle. In the case Q s e q , we define a set of possible combinations and randomly choose one of them for each query.

For each kind of queries (Q s i n , Q m u l and Q s e q ), we generate 100-500 cases and take the average cost as the final result. In each case, Q.m is randomly chosen from its possible values. Q.t and Q.m are set as standard values by default, and accurate values are randomly generated within the possible set. We evaluate the performance in terms of CPU time and I/O accesses.

8.4 Transportation modes in the index

Since both the TM-RTree and the AD-RTree maintain transportation modes, we compare the average number of modes contained by a node between the two indices. Datasets B2M and H1M are used for the evaluation. Figure 7 reports the numbers at different levels. We define 0 the root level, 1 the next level and so on. There are two extreme cases: root level and leaf level. Both indices maintain the total number of modes at root level, 19 in total (according to Def. 7.2). At leaf level, the TM-RTree only contains one but the AD-RTree includes more values. This factor has significant effect on the performance and we report the result in the following subsections, see Figs. 8, 11 and 12. The reason is, the less number of modes maintained in a node, the better the pruning ability of the index is. For example, root node always has to be considered as it includes all modes. By observation, the event of pruning unqualified nodes usually occurs when the traversing procedure goes into the low level as nodes at the high level have large extent in terms of spatial, temporal and transportation modes. Compared with the AD-RTree, nodes in TM-RTree keep much smaller number of modes at the low level.

Fig. 7
figure 7

Average number of modes maintained in a node

Full size image
Fig. 8
figure 8

Q s i n: a single mode - scaling datasets

Full size image

8.5 Scaling datasets

We report the result for different queries on transportation modes in Figs. 8, 9 and 10. Q.s and Q.t are defined to be standard values. When the number of trips increases, the cost of all indices rises proportionally. The TM-RTree is faster than the other three in all cases. In particular, the deviation becomes large for the big dataset. Using B2M, on average TM-RTree is 5 times faster than AD-RTree and 6 times faster than 3D R-Tree. This is because when applying the AD-RTree and the 3D-RTree, the filter step does not efficiently prune unqualified nodes, incurring much more CPU and I/O cost. The 3D-RTree does not maintain transportation modes. Although the AD-RTree stores modes in a node, the index does not group objects on transportation modes. A leaf node may contain several kinds of modes, leading to the weak pruning ability and many nodes to be visited. Therefore, a large amount of movement tuples will be accessed in the refinement step, resulting in more processing time.

Fig. 9
figure 9

Q m u l : multiple modes - scaling datasets

Full size image
Fig. 10
figure 10

Q s e q : a sequence of modes - scaling datasets

Full size image

The time cost of the TM-RTree is better than the 4D-RTree for Q s i n , while the I/O cost is slightly worse. This is because the TM-RTree maintains a single mode as well as a pair of modes. When only a single mode is requested, both nodes containing a single mode and a pair of modes have to be investigated, leading to more I/O accesses. For Q m u l and Q s e q , the performance of the TM-RTree is superior to the 4D-RTree in both time and I/O cost.

We also observe that there is no obvious performance difference between the AD-RTree and the 3D-RTree (see Figs. 8, 9 and 10), demonstrating that the effect of simply storing modes in a node is not obvious for improving the query efficiency. The 4D-RTree treats transportation modes as one dimension and its performance is better than the AD-TRee and the 3D-RTree. We put the precise value of each query cost in Appendix B.

8.6 Varying spatial and temporal parameters

Using the dataset B2M, we perform the experiment on all kinds of query modes: Q s i n , Q m u l and Q s e q . In each case, two groups of results are reported. We evaluate the impact of spatial (temporal) parameter on the performance by keeping the standard value for the other parameter. The performance of the TM-RTree is much better than the AD-RTree, the 3D-RTree and the 4D-RTree, especially when the size of the query box becomes large. On average, TM-RTree is 5 times faster than the other three indices. Similar to the result in the scaling experiment, there is a subtle difference between the performance of the TM-RTree and the 4D-RTree for Q s i n . Our index shows its advantages in Q m u l and Q s e q . Figures 11 and 12 report the result for Q s i n , Figs. 13 and 14 report the result for Q m u l , and Figs. 15 and 16 report the result for Q s e q .

Fig. 11
figure 11

Q s i n : a single mode - spatial

Full size image
Fig. 12
figure 12

Q s i n : a single mode - temporal

Full size image
Fig. 13
figure 13

Q m u l : multiple modes - spatial

Full size image
Fig. 14
figure 14

Q m u l : multiple modes - temporal

Full size image
Fig. 15
figure 15

Q s e q : a sequence of modes - spatial

Full size image
Fig. 16
figure 16

Q s e q : a sequence of modes - temporal

Full size image

8.7 The capability of TM-RTree

In the end, we compare two kinds of TM-RTrees where one only supports the movement with a single mode and the other manages both a single mode and a pair of modes. To distinguish between them, we name the former TM-RTree_sin. Two datasets are used, B2M and H1M. The evaluation is performed on different transportation mode conditions. Spatial and temporal parameters are set as standard values.

The results are different for the three cases, shown in Figs. 17 and 18. The TM-RTree_sin has better performance than the TM-RTree for Q s i n . Although the CPU time is almost the same, less I/O accesses are incurred for TM-RTree_sin. The reason is, after the mode extension, the total number of modes increases. The TM-RTree maintains more transportation modes than the TM-RTree_sin, i.e., different pairs of modes. Given a mode m (m ≠Walk), the procedure only has to consider leaf nodes containing m for TM-RTree_sin. However, using the TM-RTree we also have to process nodes containing the mode < m, W a l k > or < W a l k, m >. In addition, there exists an extreme case for Walk which builds the connection between different modes, resulting in many cases to be included, e.g., < Walk, Bus > and < Indoor, Walk >. As a result, the TM-RTree incurs more nodes to be accessed.

Fig. 17
figure 17

B2M: TM-RTree and TM-RTree_sin

Full size image
Fig. 18
figure 18

H1M: TM-RTree and TM-RTree_sin

Full size image

The performance is almost the same between the TM-RTree and the TM-RTree_sin for Q m u l . In Q s e q , as expected, the TM-RTree is significantly better than the TM-RTree_sin (see in Figs. 17 and 18). On average, the former is 6-7 times faster than the latter, and I/O accesses by the TM-RTree are about 1/3 as the TM-RTree_sin.

8.8 Discussion

We discover some behaviors based on the experimental result and give a summary. First, the performance is significantly improved when the index manages spatial, temporal and transportation modes in an integrated way. On average, the TM-RTree is 5 times faster than AD-RTree, 3D-RTree and 4D-RTree. Second, the 4D-RTree is superior to the AD-RTree and the 3D-RTree. Especially, if a single mode is requested, the performance of a 4D-RTree is even close to or slightly better than the TM-RTree. Third, in comparison with the TM-RTree_sin which only supports a single mode, the TM-RTree incurs more I/O accesses for Q s i n , but is much faster for Q s e q . The performance of the TM-RTree_sin decreases substantially for Q s e q as the index does not maintain the time order on transportation modes. In the end, regarding the three kinds of transportation modes, Q m u l needs more CPU time and I/O accesses than the other two cases. Between Q s i n and Q s e q , the performance for Q s e q is even better than that for Q s i n when employing the TM-RTree.

9 Conclusions

In this paper, we study range queries for moving objects with multiple transportation modes and consider three query cases: a single mode, multiple modes and a sequence of modes. An index structure called TM-RTree is proposed to efficiently manage moving objects with transportation modes. Such a structure manages not only spatial and temporal data but also transportation modes. The TM-RTree has the capability of maintaining the movement with a single mode as well as a pair of modes following the time order. Several algorithms are developed to efficiently answer queries. A comprehensive experimental study is reported to verify the performance of our solution in terms of efficiency and scalability.