Visual analytical tools for multivariate higher-order information for emergency management

Abstract

Higher-order information of moving objects is of great importance for processing in-case scenarios in emergency management. Multivariate higher-order information management is a crucial key to the success of emergency management since emergency management involves developing plans with a given set of multiple resources. Past studies focus on univariate higher-order information limiting the scope of applicability and usability. This paper proposes a set of visual analytical approaches supporting multivariate higher-order information for dynamically moving disasters. We introduce a robust Voronoi-based data structure supporting multivariate datasets and dynamic disasters and propose visual analytical approaches for effective emergency management. The proposed visual analytical suite facilitates interactivity and enables users to explore in-case scenarios with multivariate datasets and dynamic disasters. A case study with real datasets is given to explain the applicability, usability and practicability of the proposed system.

Graphic abstract

1 Introduction

With all different sorts of uncertain and emergent situations during and after any disaster, decision-making for emergency management is crucial but difficult. Operational efficiency with strategic allocation of resources plays an important role in emergency management, especially when there are multiple points-of-interest (POIs) datasets with different emergency situations. For instance, how many people will be required to get relief support for multiple disaster regions? Where, when, what and how many emergency supplies such as food, water, medicine and sanitation kits should be pre-placed in state or regional emergency service depots? These are some common questions faced by emergency personnel and humanitarian operations (Gonçalves 2011). In this time-critical emergency management, prompt information feed and immediate decisions based on higher-order information are of great important for “in-case” analysis. (Returning higher-order information for in-case, the first k-nearest emergency centre(s) is/are closed, out of function or fully booked.) A sophisticated system that supports higher-order information for various situations is required in order to make informed and quick decisions, to balance the needs and resources in different regions as well as to improve the operational efficiency of emergency management. Particularly, spatio-temporal data analytics with dynamically moving disasters (trajectory data) is of great relevancy for answering these kinds of spatio-temporal-based resources and allocation questions in dynamic situations.

Nowadays, a vast amount of trajectory disaster data is generated by GPS-equipped sensor devices. These trajectory datasets encapsulated with valuable information require an advanced decision-making system for emergency management. However, trajectory data are uncertain due to spatial uncertainty, and trajectory analysis is complex with spatio-temporal dynamicity in nature. The combination of uncertainty and complexity of dynamic spatio-temporal trajectory data creates challenges for data analysis. Higher-order information (HOI) returning a set of alternative solutions supports in-case analysis and provides a way for decision makers to deal with the uncertainty and complexity of trajectory data analysis. There have been several attempts to use trajectory analysis (dynamic disasters) in emergency management (Lee and Lee 2009; Lee et al. 2007) and many other domains. For example, trajectories capturing the movement of wildlife were used for protection and management of wildlife resources (Handcock et al. 2009); trajectories modelling the movement of traffic and humans were used for urban planning (Chu et al. 2014), surveillance analysis (Lin et al. 2012; Morris and Trivedi 2008) and supermarket shopping paths’ analysis (Popa et al. 2013).

Despite the potential of HOI for trajectory analysis, research in this topic has received little attention (Hashemi Beni et al. 2011; Wang et al. 2014a; Xiong et al. 2005). Very often, for critical situations as in emergency management, first-order information may not be enough and even may not be functioning properly for decision-making. For instance, what is the third closest emergency centre when the first two closest centres are closed, or fully booked. HOI includes k-nearest neighbour (kNN) information and k-order region (kOR) information, and they are of great use in emergencies providing useful information to deal with in-case scenarios. There has been a limited study in HOI for emergency management (Wang et al. 2014b, 2016a), and existing methods can only deal with univariate POIs and univariate HOI, and mostly one trajectory data only. In emergency management, multivariate analysis is of importance since there exist many different emergency facilities (Aboagye-Sarfo et al. 2015).

Fig. 1

An example of HOI with a set of points, $P_{A}=\{p_{A1},...,p_{A4}\}$, and a trajectory $T=\{t_1,t_2,t_3\}$: a$P_{A}$ with T; b 1NN and 1OR of generator $P_{A}$; c 2NN and 2OR of generator $P_{A}$; d 3NN and 3OR of generator $P_{A}$

Figure 1 displays a simple example to illustrate the concept of HOI including kNN and kOR. Figure 1a shows a simple dataset $P_A$ with four POIs and a trajectory T with three nodes where POIs could represent interesting facilities (e.g. police stations), whilst the trajectory is a moving trail of a tourist. Figure 1b depicts the HOI of $t_1$ where 1NN($t_1$) is $P_{A1}$ and 1OR($t_1$) is the shaded region. Similarly, Fig. 1c displays 2NN($t_1$) ($P_{A1}$ and $P_{A2}$) and 2OR($t_1$) (the shaded region), whilst Fig. 1d shows 3NN($t_1$) ($P_{A1}$, $P_{A2}$ and $P_{A4}$ in order) and 3OR($t_1$) (the shaded region).

In this article, we propose a set of visual analytics (VA) tools for multivariate HOI (Mul-HOI) for emergency management. Our tools enable diverse analytical tasks for policy makers and emergency personnel including: (1) HOI analysis for in-case scenarios; (2) kNN and kOR queries for alternative solutions for in-case scenarios; (3) supporting in-case decision-making for crisis management.

Main contributions of the paper are in fourfold: a succinct data structure supporting Mul-HOI for emergency; a set of VA tools for Mul-HOI analysis; a new quantitative and qualitative multivariate measure; a new HOI clustering method; and a case study. Detailed contributions are as follows:

• to propose a unified vector-based data structure for supporting multivariate POIs, and for efficiently manipulating dynamically moving objects;

• to present a new VA tool based on parallel coordinates (PCs) (Heinrich and Weiskopf 2013) for analysing large trajectory datasets with three categories (geometrical, topological and directional) of Mul-HOI;

• to introduce a new measurement metric, parallel coordinates multivariate measure (PCMM), to quantify both qualitative and quantitative multivariate HOI with regard to kNN geometrical, topological and directional information;

• to improve Higher-Order Radar Chart (HORC) (Wang et al. 2016b) for the determination of Higher-Order DBSCAN (HODBSCAN) clustering for trajectory data mining.

The remainder of this paper is organised as follows. Section 2 reviews background preliminaries and past studies. Section 3 proposes a unified data structure for multivariate HOI and algorithms for computing multivariate datasets and trajectories and discusses PCMM and HODBSCAN approaches. Section 4 presents a case study with real-world datasets from Flickr. Finally, Sect. 5 concludes this study and provides future work.

2 Literature review

2.1 Preliminaries

For a given set of objects, HOI refers to hierarchical information about more than one object based on higher-order Voronoi diagrams. Here, “higher” refers to more than one target object, whilst “order” means the number of query (source) objects. k defines higher order, and there are two typical HOI (kNN information and kOR information) for trajectory data analysis. Let us consider a point set S, a query point q and a positive integer k. The kNN query denoted by kNN(q) returns a point set which is a subset of S such that d(q, r) $\le$d(q, p) holds for any point r$\in k$NN(q) and for any point $p\in$(S − kNN(q)). kNN is supplemented by kOR, that is, kNN returns k objects, whilst kOR returns a region defined by k objects. kOR returns a region R for a certain subset $P_{i}^{(k)}$ in P where the set of kNN for any location l in R is the same as $P_{i}^{(k)}$. kOR can be formulated by a kth-nearest point diagram (Okabe et al. 2009). kOR defined by a given site is the set of objects in the study region such that the site ranks k in the ordering of the sites by distance from the point, and is a collection of one or more unconnected tessellations (Okabe et al. 2009). It defines tessellations on the number of cells, known as the kth-order Voronoi diagram.

kNN has a wide range of applications including classification, image processing, data mining, regression and in-case analysis, whilst kOR has been studied for location optimisation, catchment analysis, market analysis and disaster management (Keim et al. 2008). Typically, kNN returns quantitative geometrical and topological information, but kOR retrieves qualitative geometrical and topological information. In this study, HOI refers to both kNN and kOR information. Note that HOI encompasses the three geospatial characteristics: geometrical, topological and directional. Geometrical HOI is information about shape, size, location and the properties of space. Geometrical HOI is generally quantitative. Topological HOI refers to information such as the basic properties of relationships as space, dimension and transformation. Directional HOI is about relative positioning properties with distance information. Topological HOI and directional HOI are typically qualitative.

This study investigates Mul-HOI for trajectory data. Our study is based on the order-k Voronoi diagram (OkVD) families which are generalisations of the ordinary Voronoi diagram (OVD) that define kNN and kOR.

Fig. 2

Multivariate POIs with trajectory dataset $T_{1}$: a O1VD of generator $P_{A}=\{p_{A1},...,p_{A10}\}$; b O1VD of generator $P_{B}=\{p_{B1},...,p_{B10}\}$; c O1VD of generator $P_{C}=\{p_{C1},...,p_{C10}\}$; d O1VD of 3 generators $P_{A} + P_{B} + P_{C}$

To compare the differences of univariate and multivariate HOI, consider Fig. 2 with three sets of POIs data representing ten tourist attractions (red points), ten information centres (blue points), ten emergency centres (magenta points) and one trajectory denoting tourist movements. The trajectory has 20 timestamps (nodes) representing spatial locations revealed from geo-tagged photographs taken and uploaded to a photograph-sharing website. From a univariate perspective, the geometrical HOI based on the nearest neighbours as the trajectory travels along the study region with regard to $P_A$ ($p_{A4} - p_{A3} - p_{A7} - p_{A8} - p_{A9} - p_{A10}$) is shown in Fig. 2a, whilst the trajectory geometrical HOI with regard to the generators $P_B$ ($p_{B4} - p_{B5} - p_{B8} - p_{B9} - p_{B10}$) is shown in Fig. 2b. At the same time, Fig. 2c shows the $P_C$ sequence ($p_{C4} - p_{C3} - p_{C5} - p_{C9}$). In order to conduct multivariate analysis, we need to consider building HOI for the three sets of POIs together to retrieve additional information for complex multivariate analysis. Figure 2d shows geometrical HOI of those three sets of POIs (generators) for the trajectory. This mixed sequence not only provides combined HOI for the three sets of POIs, but also provides a way to build and analyse Mul-HOI. This Mul-HOI reveals interesting multivariate HOI patterns with trajectories, which was not possible with traditional univariate approaches. Note that our Mul-HOI framework supports multivariate HOI patterns for multiple trajectories; thus, the scale of trajectories such as multiple groups and the size of trajectories do not affect the analysis.

2.2 Visual analytics for higher-order information

Even though kNN and kOR are useful for many applications, most research has been focused on algorithms or application areas of kNN and kOR. Visual analytical aspects of kNN and kOR have received less attention. In particular, visual analytical aspects of higher-order Voronoi diagrams (HOVD) have received relatively less attention due to their complexities (Huang et al. 2016; Palmer 2006; Telea and van Wijk 2001). Recently, Andrienko et al. (2012) utilised HOVD for eye movement analysis.

Lee et al. (2012) study the relation of HOVD families, applications for real-world problems and a HOVD visualisation based on the raster approach. The general idea of the raster approach (Lee et al. 2012) is to calculate the raster distance of points and to obtain neighbouring relationships between POIs (generators) based on a distance transformation. After raster mapping, all spatial information is translated into a grid of points. In the raster metric space, points, lines and polygons are processed at a spatial raster. All HOVD families can be represented by a discrete grid lattice of size $N \times N$, which gives $N^{2}$ grids in the plane. The quality of HOVD depends on N, and we need a very large value N to approximately represent the real data. The main drawback of this approach is that it is based on the topology-none structure which does not support HOI in general.

Some studies investigate visualisations of HOI using the raster HOVD. Palmer (2006) investigates visual aspects of HOVD. It makes use of contour lines and textures to represent HOI based on the raster HOVD. Order-k plots superimposing nearest neighbour plots from 1 to k-1 visually draw HOI. For example, order-3 plots are the order-3 Voronoi diagram overlaid with contour lines of order-1 and order-2 (first nearest plot and second nearest plot). Thus, order-k plots visually display qualitative HOI, but they become quickly unreadable and uninterpretable as k or n increases. They are simple visualisations for HOI, but are not suited for data mining scenarios. Since this approach is based on the raster approach, it shares the main drawback of Lee et al. (2012). In some other studies, Telea and van Wijk (2001) try to represent HOVD regions using colour and shading. It introduces concepts of cushions and bevels. Cushions have different intensity levels to give shading to represent the distance to the closest site, brighter as closer to the generators, whilst darker as close to the edges. Bevels are coloured for influencing sites and scaled to reflect the kth-order distance and hierarchy. These two methods are to superimpose k sites implicitly. However, this is based on the raster approach, and it becomes quickly complex and unreadable as k or n grows. These raster-based approaches deliver qualitative HOI rather than quantitative HOI. They focus on geometrical HOI, but fail to report topological and directional HOI. These raster-based approaches are not based on any data structure; thus, they need to redraw (recompute) the whole HOVD for every query which is time-consuming. Therefore, they are not suitable for efficient in-case emergency management and complex data mining scenarios.

Recently, some VA approaches (Wang et al. 2014a, b, 2016a, b) have been proposed to visualise HOI based on the vector data structure. Wang et al. (2014a) propose a new visual analytical approach to visualise directional HOI with regard to target generators. Specifically, they create a Directional Spider Chart (DSC) that provides a mean to visually evaluate the balance of a trajectory dataset with reference to different directions, as well as comparing the directional HOI and balance among trajectory datasets. Dissimilarity measurement methods are also introduced in this study providing quantitative ways to compare the balance of directional HOI of trajectories and to contrast the dissimilarity for multiple trajectory datasets. Another approach (Wang et al. 2014b) proposes a visual analytical approach for topological HOI, whilst Wang et al. (2016b) present a visual analytical approach called Higher-Order Radar Chart (HORC). To create a HORC, first of all, each trajectory node of geometrical information $t_k$$\in$T (original trajectory T for geometrical HORC) is calculated for that distance to generators. Once the cardinality of each distance is calculated, then it is normalised into [0,1] for relative visualisation. Then, each trajectory node of directional information $d_k$$\in$D (original trajectory D for directional HORC) is determined for that direction from POIs. Figure 3 illustrates HORC and DSC examples. However, these recent vector-based approaches only handle univariate datasets not multivariate for complex emergency scenarios and fail to support HOI analysis.

Fig. 3

Example of HORCs and DSCs with the trajectory $T_{1}$ and POIs shown in Fig. 2: a O1VD HORC based on $P_{A}$; b O1VD HORC based on $P_{B}$; c O1VD DSC based on $P_{A}$; d O1VD DSC based on $P_{B}$

2.3 Higher-order information for emergency management

There have been some studies for visualisation in emergency management (Dusse et al. 2016; Wang et al. 2017; Crnovrsanin et al. 2009; Cornel et al. 2016). Dusse et al. (2016) surveyed how researchers use information visualisation tools to improve emergency management, and Wang et al. (2017) reviewed spatio-temporal visualisation methods for emergency management. Crnovrsanin et al. (2009) proposed a proximity-based visualisation approach for moving data, whilst Cornel et al. (2016) introduced composite flow maps for evacuation procedures. However, these are not designed for in-case analysis that requires HOI for backup plans.

Emergency management requires HOI for backup plans and in-case analysis (Lee et al. 2007). Recently, various approaches from different aspects of emergency management have been proposed (Hamid et al. 2015; Palmieri et al. 2016; Saoud et al. 2017; Shan et al. 2017). Shan et al. (2017) attempt to utilise social network blog data for emergency management, Palmieri et al. (2016) study an architectural approach for emergency management, and both studies (Hamid et al. 2015; Saoud et al. 2017) try to build a simulator to assist emergency management. These approaches are case-specific but are not designed to handle general HOI for in-case analysis. Different to these recent emergency management studies, this paper investigates HOI visualisation approaches and applies them to emergency management to handle the dynamic nature of disaster and in-case analysis.

Note that there has been some research in the area of dynamic movement or trajectory visualisation (Andrienko et al. 2008; Buschmann et al. 2016; Gonçalves et al. 2015). However, these approaches purely focus on movement visualisation and fail to address HOI for in-case analysis in emergency management. This study specifically investigates HOI visualisation approaches to handle dynamically changing HOI for moving disasters.

3 Multivariate HOI data structure and visual analytical methods

3.1 Unified data structure

This paper utilises the unified Delaunay triangle-based data structure which consists of a complete set of order-k Delaunay triangles (from order 0 to order (k-1)) (Lee and Lee 2009). The Delaunay triangulation is corresponding to a dual graph of the OVD. It is obtained the OVD by connecting adjacent Voronoi generators (sharing a Voronoi edge) with lines, and the OVD is generated by connecting the perpendicular bisectors of the edges of the Delaunay triangulation. Similarly, HOVD families can be constructed by the complete set of order-k Delaunay triangles. For order-0 triangles, no generator is in the circumcircle of each Delaunay triangle in the triangulation. However, there could be triangles whose circumcircles include a number of generators within them. Order-1 triangles are those triangles whose corresponding circumcircles enclosed only one generator in them. Therefore, order-k triangles are those ones whose corresponding circumcircles enclosed k generators in them. More details of the unified Delaunay triangle data structure can be found in Lee and Lee (2009). A complete set of OkVDs could be drawn from this data structure, and the relationship between the data structure is shown in Table 1.

Note that due to lower bounds of HOVDs (Okabe et al. 1992), the unified data structure suffers from a scalability issue. A hierarchical structure could improve computational complexities and also semantics of geometry partitions for zoom-in and zoom-out operations, but this is beyond the scope of our study and we focus on its application to emergency management.

Table 1 The relationship between OkVDs and the unified data structure

For example, O2VD can be obtained by a combination of order-0 triangles and order-1 triangles. For this multivariate HOI analysis, this paper extends the unified data structure to present all order-k Delaunay triangles for each generator and to combine them all together as a group. Figure 4 illustrates the working principle of the unified data structure. Figure 4a shows three order-0 triangles and their corresponding circumcircles that do not include any other points inside. Figure 4b depicts an OVD generated from the three circumcircles where their centre points become Voronoi vertices. Figure 4c illustrates one order-1 triangle and its circumcircle which includes one other point inside, whilst Fig. 4d depicts a derived O2VD from three order-0 triangles and one order-1 triangle. Please note that our data structure is based on the Euclidean distance, and all Voronoi diagrams are constructed based on the Euclidean distance which is the most popular distance in spatial analysis and modelling (Okabe et al. 1992).

Fig. 4

Illustration of the unified data structure with four points: a order-0 triangles and their corresponding circumcircles; b OVD from order-0 triangles; c order-1 triangle; d O2VD from both order-0 triangles and order-1 triangle

3.2 Parallel coordinates multivariate measure

Figure 5 displays screenshots of the proposed visual analytical suite with three generators $P_{A2}$, $P_{B2}$ and $P_{C2}$ and a trajectory dataset $T_{2}$. The Mul-HOI implementation enables users to change various k values to get different types of Mul-HOI from the trajectory data. Since different OkVDs are drawn and visualised from the same set of datasets $P_{A2}$, $P_{B2}$ and $P_{C2}$, users are able to interact with the program suite to retrieve

Fig. 5

OkVDs: a O1VD and c O5VD with generators $P_{A2}$ in red, $P_{B2}$ in blue, $P_{C2}$ in magenta and trajectory data $T_{2}$ in green; b O1VD and d O5VD with generators, $P_{A2}$ for topologically simplified trajectory $T_{A2}$ in red, $P_{B2}$ for topologically simplified trajectory $T_{B2}$ in blue and $P_{C2}$ for topologically simplified trajectory $T_{C2}$ in magenta

different data points for any user-interested location within the set of query points on the fly. $P_{A2}$ and its corresponding Voronoi diagrams are represented in red. $P_{B2}$ and its corresponding Voronoi diagrams are represented in blue, whilst $P_{C2}$ and its corresponding Voronoi diagrams are shown in magenta. These Voronoi diagrams are drawn based on the geometrical HOI. Geometrical HOI is computed based on the Euclidean distance of the trajectory data points to a set of the nearest generators. O1VD and O5VD of the trajectory data are shown in Fig. 5a, c in green, respectively. Figure 5b, d displays topologically simplified trajectories with multivariate generators. For the topologically simplified trajectories, the program will try to go through every single data point (node) in the trajectory, cluster the data points possessing the same topological HOI (falling into the same Voronoi region) and represent them as a simplified centre node. A topologically simplified trajectory for $P_{A2}$ is presented in red, and a topologically simplified trajectory for $P_{B2}$ is presented in blue, whilst a topologically simplified trajectory for $P_{C2}$ is presented in magenta.

Fig. 6

Geometrical PCMMs (x-axis: minimum (top) and maximum (bottom) of the distance to order-k generators; y-axis: trajectory node id): a geometrical PCs–$P_{A2}$; b geometrical PCs–$P_{B2}$; c geometrical PCs–$P_{C2}$ based on the trajectory data $T_{2}$. Quantitative PCMM is shown in orange, whilst qualitative PCMM is shown in cyan. When quantitative and qualitative PCMMs are the same, it is shown in green

PCMM for mining trajectory HOI is defined based on the HOI information we discussed above. Figure 6 exhibits geometrical PCs with distance and relationship between trajectory and different generators. For each data point of the trajectory ($T_{2}$) and three POIs ($P_{A2}$, $P_{B2}$ and $P_{C2}$), we calculate the distance between each single POI and the trajectory with different order k (x-axis of the diagram) to draw the geometrical PCs. Each column (vertical bar) from left to right in the figure shows the order-1 to order-k HOI. For each data point in the trajectory, the distance to the kNN is calculated by using the Min–Max normalisation (Shalabi and Shaaban 2006), $v_\mathrm{Short}$ as shown in Eq. 1 to determine a qualitative PCMM. For each data point in the HOI trajectory of the three POIs, the distances of the data point to the 1NN to kNN HOI are used to calculate $v_\mathrm{Short}$. If the data point has the shortest distance from HOI in $P_{A2}$, this trajectory point is calculated and it determines a quantitative PCMM for $P_{A2}$. Quantitative PCMM is shown in orange, whilst qualitative PCMM is shown in cyan. For the same quantitative and qualitative PCMM, it is shown in green. In Eq. 1, Min and Max represent the minimum and maximum distance between any point in the trajectory to the kNN POIs. The newMax and newMin are scaling factors which can be chosen by users to scale the PCMM into a range of values as desired. In this study and the case study in the following section, newMin is set to 0 and newMax is set to 1; hence, $v_\mathrm{Short}$ will be scaled between 0 and 1:

$$\begin{aligned} v_\mathrm{Short}=~\frac{v - Min}{Max - Min} (newMax - newMin) + newMin. \end{aligned}$$

(1)

Fig. 7

Topological PCMMs (x-axis: order k; y-axis: trajectory node id): a topological PCs–$P_{A2}$; b topological PCs–$P_{B2}$; c topological PCs–$P_{C2}$ based on the trajectory data $T_{2}$

When considering the topological HOI of the trajectory, Fig. 7 shows PCMMs of the topological information exhibiting relationships between trajectory and generators. For each data point of the HOI trajectory ($T_{2}$) with respect to the three sets of POIs ($P_{A2}$, $P_{B2}$ and $P_{C2}$), we calculate the relationship between each trajectory data point and single POI with different order k (x-axis of the diagram) to draw topological PCs. Each column from left to right shows the order-1 to order-k information, respectively. Each of the trajectory data goes through each column by calculating the relationship of each trajectory to POIs; then, each of the trajectory data draws the relationship to each k column.

Fig. 8

Directional PCMMs (x-axis: order k; y-axis: trajectory node id): a directional PCs–$P_{A2}$; b directional PCs - $P_{B2}$; c directional PCs–$P_{C2}$ based on the trajectory data $T_{2}$

Considering the directional HOI trajectory, PCMMs of directional information for mining trajectory exhibit eight different directions (east (E), west (W), north (N), south (S), north-east (NE), south-east (SE), north-west (NW) and south-west (SW)) between trajectory and generators as shown in Fig. 8. For each single data point of the HOI trajectory ($T_{2}$) of three POIs ($P_{A2}$, $P_{B2}$ and $P_{C2}$), we calculate directional information between each single POI and trajectory with different order k (x-axis of the diagram) to draw directional PCs. Each column from left to right shows the order-1 to order-k information, respectively. Each of the trajectory data goes through each column by calculating directional information of each trajectory to POIs; then, each of the trajectory data draws the direction to each k column. In conclusion, we are able to reveal three different categories of HOI with PCMMs. The run-time of this approach is linear to the number of trajectory nodes. This approach is much faster than other existing approaches and is able to provide more details and richer information compared to other visual analytical approaches. Applications of PCMMs will be further discussed in Sect. 4 where we explain how they could be used for various stages of emergency management, in particular preparedness and response.

3.3 Higher-Order DBSCAN

In this section, we introduce a new data mining algorithm that groups HOI into top-k clusters called Higher-Order DBSCAN (HODBSCAN). We use a VA approach HORC (Wang et al. 2016b) to visualise HODBSCAN. HODBSCAN is a DBSCAN-based approach (Ester et al. 1996) for grouping a set of points into clusters with similar HOI. DBSCAN requires two parameters to set: minPT (the minimum number of points) and $\varepsilon$ (the maximum radius of neighbourhood). HODBSCAN calculates the minPt based on the average distance up to kth-order HOI (called HOk-means) minimising SSE (the sum of the squared distance between each member of cluster and its centroid) and $\varepsilon$ based on Min from PCMM to identify the distance of each cluster. The order k defining the k number of neighbours is an exploratory tool, and it is for in-case analysis allowing the user to set it to explore a given dataset. HODBSCAN identifies clusters with similar HOI which represent useful information for emergency management. The higher-order cluster centre $T\prime$ and SSE are defined as follows:

$$\begin{aligned} T\prime ~= & {} \hbox {Means}\left( \sum _{i=1}^{n}{\hbox {kNN}(t_i)}\right) ,\end{aligned}$$

(2)

$$\begin{aligned} \hbox {SSE}= & {} \sum _{i=1}^{k}\sum _{j=1}^{n}\left\| t_{i}^{(j)} - T\prime _{j} \right\| ^{2}, \end{aligned}$$

(3)

where $\left\| t_{i}^{(j)} - T\prime _{j} \right\| ^{2}$ is a chosen distance measure between a trajectory data node $t_{i}^{(j)}$ and the higher-order cluster centre $T\prime _{j}$, which is an indicator of the distance of the n data points from their corresponding higher-order cluster centres. This method is not only minimising cluster’s centroid, but also considering HOI of each trajectory.

Fig. 9

HODBSCAN with trajectory $T_{2}$: a O5VD HODBSCAN based on $P_{A2}$; b O5VD HODBSCAN based on $P_{B2}$; c O5VD HODBSCAN based on $P_{C2}$; d O5VD HODBSCAN based on all $P_{A2}$, $P_{B2}$ and $P_{C2}$ together

Figure 9 displays O5VD HODBSCAN which considers the five nearest POIs for each node. Using the proposed HODBSCAN clustering method, considering each POI with a trajectory separately, Fig. 9a shows HODBSCAN based on the order-5 Voronoi Diagram for $P_{A2}$, and HOI of $T_{2}$ in green. Figure 9a shows that based on O1VD, most POIs are very close to trajectory $T_{2}$, and almost half of POIs are inside the innermost circle, that is, under 25% of 264.85 km. Generally, most of the POIs are sitting at the west side of trajectory $T_2$, but HODBSCAN clusters are more located at the centre and west direction of trajectory $T_2$. Figure 9b displays O5VD HODBSCAN for $P_{B2}$, and HOI of $T_2$ in blue. Figure 9b shows that based on O5VD, most POIs are half distance (about 50%) of the maximum distance range which is 261.37 km. Interestingly, most HODBSCAN clusters are sitting at the centre and west side of trajectory $T_2$ similar to $P_{A2}$. Figure 9c presents O5VD HODBSCAN for $P_{C2}$, HOI of $T_2$ in magenta. Figure 9c shows that based on O5VD, most POIs are under the middle circle (about 50%) of the maximum distance range which is 251.09 km. Most POIs are sitting at the centre and north side of trajectory $T_2$. Figure 9d shows O5VD HODBSCAN for all $P_{A2}$, $P_{B2}$ and $P_{C2}$ together, and HOI of $T_2$ in red. Based on O5VD, most HODBSCAN clusters are located inside the middle circle, that is, under 50% of 140.46 km, and direct to the north and east side of trajectory $T_2$.

4 Applications

Mitigation, preparedness, response and recovery are four main phases in emergency management (Haddow et al. 2013). In this section, we illustrate how a trajectory with geometrical, topological and directional Mul-HOI can be used for each stage of emergency management. We demonstrate with a case study using geo-tagged photographs from Flickr in Queensland, Australia, in the years of 2010–2011 and tourism trajectory datasets. We utilise the Flickr API (https://www.flickr.com/services/api/) to extract the Flickr dataset where 17,066 records were preprocessed to produce the trajectory dataset used in this study. We have chosen some of these preprocessed Flickr data in the city of Cairns in Queensland, Australia, where tourism and hospitality are major industries and tropical cyclones frequently occur, to demonstrate the need of HOI for emergency management.

Figure 10a displays the dataset in Queensland, Australia, with Google Earth 6.0 (earth.google.com).

Fig. 10

Case study: a geo-tagged photographs from Flickr; b distribution of clusters in the CBD of Cairns ($P_{A3}$ in red), and information office in the CBD of Cairns ($P_{B3}$ in blue), and emergency office in the CBD of Cairns ($P_{B3}$ in magenta)

Not surprisingly, the majority of these geo-tagged records is distributed along the coastline of Queensland, where the major cities are developed. This study will use a subset of the dataset with data points from Cairns, in particular a regional capital city in Queensland, Australia, to demonstrate the usefulness and applicability of the proposed visual analytical approaches. Figure 10b illustrates a subset of $P_{A3}$ clusters (red) within the CBD of Cairns. These places are set up as potential tourist centres for emergency management in this study. Blue points $P_{B3}$ are current information centres within the CBD of Cairns. Magenta points $P_{C3}$ are current emergency centres within Cairns.

4.1 Mitigation

Mitigation is a process to remove or decrease the causes of risk or disaster. It is one of the important steps that provides prevention of removing, eliminating and reducing the effects of disaster.

Fig. 11

HOVDs for trajectory $T_{3}$: a O1VD and b O5VD of trajectory $T_{3}$ with Mul-HOI $P_{A3}$, $P_{B3}$, $P_{C3}$; c O1VD and d O5VD with three new topologically simplified trajectories. $T_{A3}$ in red, $T_{B3}$ in blue, whilst $T_{C3}$ in magenta

Figure 11a, b shows order-k Voronoi diagrams with different values of k. A trajectory dataset is collected in every minute for a period of 20 minutes from a tourist group who walked around the CBD of Cairns. The data collected from the tourist group $T_{3}$ are represented in green. Let us consider that $P_{A3}$ represents tourist attractions, $P_{B3}$ represents information centres and $P_{C3}$ represents emergency centres. Figure 11a shows O1VD, and Fig. 11b displays O5VD with only $T_{3}$ data information. Considering the three different POIs datasets, kNNs for $T_{3}$ are different for each POI dataset. Mul-HOI can provide useful information to indicate where the higher-order k-nearest help centres are along the path of the trajectory, assuming that all three types of help centres are from emergency centres, tourist attractions and information centres.

Figure 11c, d shows different values of k with three topologically simplified trajectories. $T_{A3}$ is represented in red, $T_{B3}$ is shown in blue, whilst $T_{C3}$ is in magenta. The local council can make decisions about the best top-k locations for setting up emergency tables or information tables for tourists before a disaster arrives. The k-nearest neighbouring emergency units give suggestions about areas where more activities are occurring. This provides useful information for tourists to make backup plans when the nearest information centre is not available or functional. VA approaches provide a way to leverage data visualisation and human cognitive ability (Sun et al. 2013). With the additional information from the topologically simplified trajectories, the local government can make more informed decisions for planning emergency supports before damage from the disaster occurs.

4.2 Preparedness

Preparedness explores ways to improve damage response operations by effectively coordinating various response processes. In this phase, emergency centres make plans to evaluate damages, train personnel, save lives and minimise damage from disasters having emergency personnel on standby or determining the k-nearest evacuation places with dynamic (moving/changing over time) data.

Fig. 12

Geometrical PCMMs (x-axis: minimum (top) and maximum (bottom) of the distance to order-k generators; y-axis: trajectory node id): a generator $P_{A3}$’s geometrical PCMM for $T_{A3}$; b generator $P_{B3}$’s geometrical PCMM for $T_{B3}$; c generator $P_{C3}$’s geometrical PCMM for $T_{C3}$

Fig. 13

Topological PCMMs (x-axis: order k; y-axis: trajectory node id): a generator $P_{A3}$’s topological PCMM for $T_{A3}$; b generator $P_{B3}$’s topological PCMM for $T_{B3}$; c generator $P_{C3}$’s topological PCMM for $T_{C3}$

Fig. 14

Directional PCMMs (x-axis: order k; y-axis: trajectory node id): a generator $P_{A3}$’s directional PCMM for $T_{A3}$; b generator $P_{B3}$’s directional PCMM for $T_{B3}$; c generator $P_{C3}$’s directional PCMM for $T_{C3}$

Figures 12, 13 and 14 show different values of k with order-k information. Figure 12 displays geometrical information to determine the distance and relationship of the trajectory $T_{A3}$ based on generators $P_{A3}$, $P_{B3}$ and $P_{C3}$. It also highlights the quantitative PCMM and qualitative PCMM information between Mul-HOI trajectory $T_{3}$ and generators $P_{A3}$, $P_{B3}$ and $P_{C3}$. Figure 13 shows topological information to define the relationship of trajectory $T_{A3}$ through generators $P_{A3}$, $P_{B3}$ and $P_{C3}$. It displays a relationship trend for different order-k values between trajectory and generators. Figure 14 presents directional information to appraise the directional information of the trajectory $T_{A3}$ based on generators $P_{A3}$, $P_{B3}$ and $P_{C3}$. It not only draws the trajectory directional information based on generators, but also displays the most focused/popular direction within different order k.

Before a disaster or emergency situation occurs, PCMMs can help government units to focus on top priority regions based on quantitative and qualitative PCMM where the emergency/information centre has the shortest distance to the trajectory. Secondly, government units can also focus on the most popular/sensitive generators based on topological PCMMs where the emergency/information centre has the strongest relationship with the disaster trajectory. Moreover, they can also pay attention to the directions where directional PCMMs have strong relations between trajectory and generators through different order-k values. Thus, PCMM provides three different ways to analyse multiple sets of POIs to trajectory Mul-HOI. It allows the government to suggest or provide better decisions on what (order), where (location) and which (centre) begins to provide the next emergency response.

4.3 Response

Response is to provide immediate assistance and activities following the emergency situation to aid disaster victims with shelters, food and medications. It is to stabilize the situation, to prevent the probability of secondary disaster, and to give initial repairs for recovery. When emergencies happen, the nearest emergency centres are required to cooperate and collaborate in order to effectively and quickly decrease the damage from the disaster. Typically, the first nearest emergency centre responds to each case, but when it is not available due to road closure, over capacity or the lack of resources, higher-order emergency centres should be in place to handle these dynamic situations.

Fig. 15

Geometrical PCMMs (x-axis: minimum (top) and maximum (bottom) of the distance to order-k generators; y-axis: trajectory node id): a generator $P_{A3}$’s geometrical PCMM for $T_{A3}$; b generator $P_{B3}$’s geometrical PCMM for $T_{B3}$; c generator $P_{C3}$’s geometrical PCMM for $T_{C3}$

Fig. 16

Topological PCMMs (x-axis: order k; y-axis: trajectory node id): a generator $P_{A3}$’s topological PCMM for $T_{A3}$; b generator $P_{B3}$’s topological PCMM for $T_{B3}$; c generator $P_{C3}$’s topological PCMM for $T_{C3}$

Fig. 17

Directional PCMMs (x-axis: order k; y-axis: trajectory node id): a generator $P_{A3}$’s directional PCMM for $T_{A3}$; b generator $P_{B3}$’s directional PCMM for $T_{B3}$; c generator $P_{C3}$’s directional PCMM for $T_{C3}$

Considering PCMM between trajectory $T_{A3}$ and generators $P_{A3}$, $P_{B3}$ and $P_{C3}$, geometrical PCMMs are shown in Fig. 15, topological PCMMs are in Fig. 16 and directional PCMMs in Fig. 17. Clearly, we can see that although the numbers of clusters in the topologically simplified trajectories are different, corresponding HOI patterns are very similar. Figure 15a shows the common PCMM in red based on $P_{A3}$. Figure 15b shows the common PCMM in blue based on $P_{B3},$ whilst Fig. 15c shows the common PCMM in magenta based on $P_{C3}$. The quantitative and qualitative PCMMs with topological and directional information are shown in Figs. 16 and 17, respectively.

In response to an emergency situation, better and faster solutions provided, based on different issues, are crucial. Response plans can be introduced based on patterns from PCMMs. From Fig. 15, we can choose trajectory nodes $t_{12} - t_{14}$ as response plans, since these nodes exhibit similar quantitative and qualitative geometrical PCMM. Interestingly, PCMMs with geometrical information become better after k = 6 as can be seen from Fig. 15. Based on the topological information, generators ($P_{A3-(3,6,7,8,11,13)}$, $P_{B3-(1,4,6,7,9,10)}$ and $P_{C3-(3,4,5,6,7,8)}$) exhibit better topological PCMMs. One more thing to note is that the trajectory has the east side as a focusing direction for all datasets $P_{A3}$, $P_{B3}$ and $P_{C3}$.

4.4 Recovery

Recovery is a reaction to emergencies and happens when the disaster is over. It is a set of activities that returns a community back to normal and also prevents secondary damage. Resource allocation for emergency recovery is dynamic and complex; thus, HOI for case-specific emergency is crucial for effective and efficient recovery.

Fig. 18

Distributions of SSE for HOI (x-axis: order k; y-axis: SSE). a Original elbow method for O5VD; b HO5-means for O5VD, of trajectory dataset $T_3$ with generators $P_{A3}$, $P_{B3}$ and $P_{C3}$

In Fig. 18, we can see that in the elbow chart showing the SSE after running k-means clustering for k going from 1 to 19 is evident. We see a pretty clear elbow $P_{A3}$, very similar to elbow ALL. Elbow $P_{B3}$ is lower than $P_{A3}$ and ALL, and elbow $P_{C3}$ is higher than $P_{A3}$ and ALL. Thus, we can combine $P_{A3}$ and ALL together to undertake further analysis. This result suggests that the optimal numbers of clusters of $P_{A3}$, $P_{B3}$, $P_{C3}$ and all together that the HO5-means are k = 6 for $P_{A3}$, k = 3 for $P_{B3}$, k = 4 for $P_{C3}$ and k = 4 for all generators together. Interestingly, the elbow $P_{A3}$ is very similar to the elbow ALL in HO5-means although $P_{B3}$ and $P_{C3}$ are higher. Therefore, we set minPt based on the best k value of SSE from HOk-means algorithm and $\varepsilon$ based on Min from PCMM to identify the distance of each clusters.

Fig. 19

HODBSCANs for O5VD: a generator $P_{A3}$’s HODBSCAN for $T_{A3}$; b generator $P_{B3}$’s HODBSCAN for $T_{B3}$; c Generator $P_{C3}$’s HODBSCAN for $T_{C3}$; d generator $P_{C3}$, $P_{C3}$ and $P_{C3}$’s HODBSCAN for $T_{3}$

Consider HORCs and HODBSCAN between trajectory $T_{3}$ and generators $P_{A3}$, $P_{B3}$ and $P_{C3}$, with O5VD HODBSCAN information in Fig. 19. Figure 19a displays O5VD HODBSCAN for $P_{A3}$ where HOI of $T_{A3}$ is displayed in green. Figure 19b displays O5VD HODBSCAN for $P_{B3}$ where HOI of $T_{B3}$ is presented in blue. Figure 19c displays O5VD HODBSCAN for $P_{C3}$ where HOI of $T_{C3}$ is shown in magenta. Figure 19d displays O5VD HODBSCAN for $P_{A3}$, $P_{B3}$ and $P_{C3}$ all together where HOI of $T_3$ is displayed in red. Clearly, we can see that HODBSCANs show the POIs are mostly located around a centre location (about 20% of the Max distance 167.29 km) and the north, north-west, west side and not located close to each other. In Fig. 19b, a HODBSCAN shows that the POIs are mostly located in a centre (about 20% of the Max distance 169.25 km) and the north side and very close to the trajectory. In Fig. 19c, a HODBSCAN displays that the POIs stay at west and south directions and a big cluster very close to the trajectory (less than 10% of the Max distance 148.22 km). In Fig. 19d, a HORC shows that the POIs are mostly located in a centre, west and east side and very close to the trajectory based on all $P_{A3}$, $P_{B3}$ and $P_{C3}$’s HOI information.

In the short term of emergency recovery, we can choose different numbers of clusters as recovery plans based on HORC and HODBSCAN. For the long term, recovery plans can be introduced based on patterns from PCMM and HODBSCAN, the kth of Mul-HOI and the best k for clustering trajectory HOI. Therefore, the best choice for order k and cluster number k is a solid reference for decision-making and is useful for the recovery phase of emergency management.

4.5 Comparison

This section analyses the efficiency and capabilities of our framework and compares it with other existing approaches. Figure 20 shows existing HOI approaches. Figure 20a, b shows a Web Map segmentation approach that is based on the raster approach (Lee et al. 2012). The approach is able to construct approximate HOVDs with three popular Minkowski metrics (Euclidean, Manhattan and maximum distance) and is able to visualise HOI information. However, this approach suffers from several major weaknesses that cannot be used for in-case emergency management. First, it is based on the raster approach and is not able to represent topological and directional HOI. Second, it needs to reconstruct HOVDs for every task which is not time efficient for emergency management. Third, it does not compute exact HOVDs, but approximate HOVDs using a distance transformation. Note that accurate information is crucial in emergency management. Fourth, it is for univariate datasets and not suitable for multivariate datasets. Fifth, it is a simple visualisation tool and not an interactive VA tool. Sixth, it does not support a moving trajectory for dynamic HOI analysis.

Fig. 20

Comparison of existing HOI approaches: a raster-based for O1VD; b raster-based for O1VD with a line; c HOVD families with kNN and kOR

Figure 20c displays a complete set of HOVDs for kNN and kOR queries (Lee and Lee 2009). It is based on the vector approach, and it supports a user to explore different k values for various HOVDs. It is able to support geometrical HOI and basic topological HOI, but unable to support directional HOI. As in Lee et al. (2012), this approach only supports univariate datasets and fails to deal with a moving trajectory. In addition, this approach lacks high-level interactivity to enable user-oriented queries.

Table 2 Effectiveness and efficiency comparison with existing approaches (N: the number of grids; n: the number of points)

As discussed in Sect. 2.2, Table 2 compares the effectiveness and efficiency of the proposed framework with existing studies (Lee and Lee 2009; Lee et al. 2012). The effectiveness and efficiency of the raster-based HOI approach (Lee et al. 2012) are totally dependent on the number of grid cells N and are unable to support many visual analytical interactions. Note that N is much larger than n in the vector-based HOI approach (Lee and Lee 2009); thus, the raster-based approach is computationally slower than the vector-based approach in data-rich environments or when the raster-based approach needs to produce a high-resolution tessellation close to the quality of vector-based tessellation. The vector-based HOI approach (Lee and Lee 2009) supports univariate datasets only and does not deal with dynamic trajectories which are two essential characteristics (multivariate and trajectory) in emergency management. In addition, it provides limited functionality and interactivity for various in-case emergency management processes.

Table 3 Comparison with existing HOI VA approaches

Table 3 compares the proposed framework with existing HOI VA approaches (Wang and Lee 2014; Wang et al. 2014a, b, 2016a, b). Wang and Lee (2014) introduce some naive visualisation approaches to display HOI with limited interactivity, whilst Wang et al. (2014a) introduce a higher-order spider chart visualisation approach to display directional HOI. Wang et al. (2014b) focus on topological HOI and apply to emergency management. Wang et al. (2016a) investigate geometrical Mul-HOI, but it does not support topological and directional HOI, and no data mining techniques to help users solve real-world case studies. Wang et al. (2016b) introduce a data mining algorithm that returns top-k clusters based on geometrical and topological HOI, but does not support multivariate POIs. Please note that our proposed method is designed to handle geometrical, topological and directional HOI for multivariate POIs and introduces a density-based clustering for HOI.

4.6 Discussions

This study proposes new VA approaches to analyse trajectories with multivariate datasets for emergency management. The unified data structure gives general suggestions or in-case information before making plans in all stages of emergency management. The new multivariate data structure can support multivariate data analysis and can provide useful information for multivariate in-case analysis. Topologically simplified trajectory datasets, in particular in data-rich environments, can filter and better represent data to help different groups of related entities to quickly make decisions in the preparedness step. Our proposed program suite enables users to interact with the program to obtain three different types of information at the same time (geometrical, topological and directional) based on different POIs on the fly. In the response stage, organisations or governments can well support and control tourist attractions, information centres and emergency centres with PCMM. Which, what, where and how many items should be considered can be prepared for the next recovery step. Prompt decision-making for the short-term recovery is of great importance after disaster. This approach introduces short-term and long-term suggestions with three different categories of HOI. Organisations can make decisions about where the clusters are located, what is the best cluster number k, how many clusters are within different HOI and which cluster covers multivariate HOI regarding different types of help centres. This type of multivariate HOI can help decision makers to deal with more complex and dynamic emergency scenarios.

Fig. 21

Various screenshots of our framework: a HORC; b higher-order trajectory area; c DSC; d HODBSCAN

Figure 21 displays several screenshots of our proposed framework. It allows users to navigate various menus and functions to interactively explore given datasets and to support analytical reasoning. Our system supports univariate and multivariate HOI for diverse in-case emergency management processes.

5 Conclusion

Disasters and emergencies could generate various forms of financial, structural and environmental damages that could threaten public safety, environmental properties and public critical infrastructure. Effective emergency management for dynamic trajectories is emerging, and HOI is of great importance in highly dynamic, uncertain and complex emergent situations. Note that it is almost impossible to avoid occurrences of disasters, effective prediction and preparedness along with a post-emergency management program which can mitigate the risk and damage. Dynamic emergency management with trajectory analysis has emerged in the last decade as a very active research domain with many potential applications for emergency management. However, previous research mainly focused on univariate dataset relationships with trajectories and also only one type of information. In many real situations, emergency management involves in multiple disasters with many resources. This research focuses more on emergency management with three different types of HOI with multivariate datasets associated with trajectory data.

Research on trajectory data mining with HOI is limited. This study introduces new VA approaches and HODBSCAN clustering method for analysing large trajectory datasets and HOI in particular for emergency management. These approaches are efficient and effective to provide new ways to represent geometrical, topological and directional HOI to provide semantic answers to problems such as HOI analysis and in-case analysis for emergency management. Note that our framework requires k as the only input parameter as the degree of HOI, but our framework follows the exploratory principle from VA and allows users to explore various HOVDs with different k values in order to explore different levels of HOI such as k-nearest neighbours and regions.

This paper also introduces a unified data structure for multivariate datasets that can support Mul-HOI; visual analytical approaches for topologically simplified HOI of trajectory datasets; PCMM for quantified multivariate HOI with regard to three categories of k-nearest neighbour information; and HODBSCAN. Those approaches enable users to interactively analyse a large volume of trajectories with different POIs and to understand the HOI relationship of POIs (emergency resources) and trajectories (disasters). Moreover, HODBSCAN provides a new data mining method to combine HOI with regard to target generators. Future work includes an extension to increase interactivity of the proposed system, an investigation to improve efficiency of algorithms and more comprehensive case studies to demonstrate the applicability and usefulness of the proposed visual analytical tool. In addition, network distance and weighted distance are more realistic than the Euclidean distance in real world by considering underlying road networks and weights. Currently, vector-based Voronoi diagrams are computationally expensive and HOVDs with these distances have not been widely studied. Future work includes to extend the current framework to these distances to more realistically model the real world. Our system computationally suffers when the number of trajectories increases. Clutter reduction methods such as clustering or filtering could be studied to improve the scalability issue.