# Exploring Hybrid-Multimodal Routing to Improve User Experience in Urban Trips
## 3 Evaluation Framework
### Data Structure  
We model all the data in MLGLS data structure, which was created by combining: (i) Linkstreams [25], a temporal graph structure that stores links sorted according to time of occurrence; (ii) KDTree [26], which is a tree structure to ease nearest neighbor searches; and, (iii) Multi-Aspect Graph [27], a derivation of static graphs that allow the creation of multiple layers to represent data features. A link is a 3-tuple (\(a\), \(b\), \(t\)) that shows a contact between \(a\) and \(b\) at time \(t\). Contacts that are represented in this stream are time-sorted and they may optionally have a duration, in which case the Linkstream may be called a Stream Graph. Because links are sorted in time, one can use a binary search to optimize queries. However, the Linkstreams are not designed to deal with positions, an important feature of mobility data. To tackle this issue, we added a complementary index to the Linkstream using KDTrees. The way that this tree is constructed allows the quick execution of neighborhood searches, as opposed to other spatial trees, such as the R*-tree [28]. The use of Linkstream and KDTree makes it possible to run quick spatio-temporal data searches. However, urban mobility is heterogeneous and it can be collected from different sources, and must be combined to perform a more insightful analysis [29]. Such a process must not lose information about the data origin since data from different contexts may have different interpretations. To combine data without losing its source information, we use a feature from the Multi-Aspect Graphs, the possibility of creating multiple layers in the graph to represent different data sources. This data structure allows for the creation of aspects, a data dimension where multiple layers can be added. Hence, we propose the usage of several layers where data from different sources can be sheltered. Formally, the MLGLS is a group of nodes \(v\in V\), connected by links \(e\in E\). These nodes and links may hold further information detailing the event identified by the node or the type of contact that is indicated by the edge. The existence of events (or nodes) are known via a data source (or layer) \(l\in L\); and, all of the interactions happen in a time interval \(T=[t_{0},\,t_{f}]\). Additionally, to enhance the spatial queries' performance, we have a Geographical Index \(I\) (i.e., the KDTree). Thus, the MLGLS is given by the tuple \(M=\langle V,E,L,T,I\rangle\). An important implementation aspect is the existence of different layer types. The data structure supports both static graphs and links stream layers. For static layers, the difference is that nodes and links exist during the whole time interval, from \(t_{0}\) to \(t_{f}\). Because of the characteristics of modern datasets, there is another type of layer, called dynamic. This type is used for layers in which nodes and edges vary in time, but the information regarding these graph entities can only be obtained when needed. For example, the bike dockers in our experiments may or may not have bicycles available at a given moment. Thus, when we need to verify the existence of a node, we perform a call to the provider API to evaluate if that node will, or will not, be listed in the graph. The dynamic layer is defined in the MLGLS as a time-dependent function called upon the necessity to evaluate the current state of a layer. Figure 3 depicts our proposed data structure, which has two dimensions: time and data sources. Layers can be created at each dimension, being represented by rows or columns of rectangles in Figure 3. The dotted blue line \(\mathrm{L_{h}}\) is surrounding the taxi data layer in the data-source dimension, and the green dotted line \(\mathrm{L_{v}}\) is surrounding the time layer \(t_{2}\). The nodes (circles) are the data entries, and each link (continuous line) represents the contact between those entries. The dashed thick lines represent contacts that persisted in time. Finally, the red lines represent the spatial index that is created by the KDTrees.