Modeling and Querying Moving Objects with Social Relationships

Abstract

Current moving-object database (MOD) systems focus on management of movement data, but pay less attention to modelling social relationships between moving objects and spatial-temporal trajectories in an integrated manner. This paper combines moving-object database and social network systems and presents a novel data model called Geo-Social-Moving (GSM) that enables the unified management of trajectories, underlying geographical space and social relationships for mass moving objects. A bulk of user-defined data types and corresponding operators are also proposed to facilitate geo-social queries on moving objects. An implementation framework for the GSM model is proposed, and a prototype system based on native Neo4J is then developed with two real-world data sets from the location-based social network systems. Compared with solutions based on traditional extended relational database management systems characterized by time-consuming table join operations, the proposed GSM model characterized by graph traversal is argued to be more powerful in representing mass moving objects with social relationships, and more efficient and stable for geo-social querying.

1. Introduction

Moving object databases (MOD) allow modelling, manage moving entities such as people, vehicles and vessels, and have been extensively studied over the past few years, such as data modelling [1,2,3,4,5,6], indexing [7,8,9,10] , and querying [11,12,13,14,15]. This research focuses on the management of movements and involved geographic environments, but ignores the social relationships between moving objects. Let us consider the following scenario. A user visiting a shopping mall is usually associated with geo-locations through check-ins made by mobile devices. The user has some online relationships in social networks, such as Facebook, Twitter or Foursquare. In so called location based social networks (LBSN) [16,17,18], there have been a bulk of query requests concerning not only movements with spatial and temporal characteristics, but also dynamic variation of social relationships:

-

Q1: Tell me the nearest restaurants that have been checked in by my friends in this month.

-

Q2: When, where and which colleagues did I met last week?

For the above examples, the MODs are good at answering the request "find the nearest restaurants around me", but they cannot answer the query Q1 involving the social relationships. The query Q2 is also difficult for MODs because it needs to traverse both the movements and social relationships.

As we know, these geo-social data have great value for online recommender services, transportation and urban computing, human mobility research [19,20] and investigation of the connection between social ties and correlated activity [21,22]. The advancement of the wireless networks and mobile Internet further accelerate the explosive growth of the data. As of 2012, Facebook claims to have 600 million mobile users and 140 billion friend connections [23]. As of 2015, Foursquare has over 55 million users and over 7 billion check-ins worldwide [24]. The database systems should not only model the trajectories but also represent the social relationships of moving objects. More and more, real-world applications require ad hoc data management technologies, leading to a rise in new study challenges and opportunities in the field of MOD and geographical information systems (GIS) [21,25,26,27].

A natural approach to manage movement together with social relationships is to store them separately. For example, spatial database management systems (DBMS) or MOD could be used to manage trajectories and geographical space, and the social relationships can be managed with native graph databases. Obviously, such a simple combination will be extremely inefficient because it asks to traverse two databases constantly.

Another approach is to store together and retrieve together, where social relationships are transformed into tuple $<o_1,rel,o_2>$ and stored into Spatial DBMS or MOD. However, it will generate much data redundancy, and many time-consuming table-join operations are needed to perform geo social queries. Graph database systems such as Flockdb, Neo4J, and Giraph, cannot be directly applied to store trajectories, although they are undoubtedly suitable for representing social relationships because of the lack of an abstraction level and upper logical data model [28].

There is a paucity of literature regarding integrated approaches to modelling and querying geo-social data. Although Pelekis and co-workers presented a novel graph-based model that uses a dynamic graph to represent semantic mobility timelines [17], related issues of modelling social relationships have not been addressed. This calls for the development of novel data models to store, index and query moving objects with social relationships.

In this paper, we focus on modelling the moving objects with social relationships and propose a composite graph-based data model called Geo-Social-Moving (GSM) where geographical space, trajectories and social relationships are all represented with graph structures. Geographical space is divided into a set of Voronoi regions. Each Voronoi region is modelled as a graph node and an edge connecting two Voronoi regions represents the spatial adjacency relationships between them. Trajectories of moving objects are represented with a movement graph. A trajectory is split into a set of trajectory units in different Voronoi regions. In other words, all the location points along a trajectory in a specific Voronoi region are collected and modelled as one trajectory unit, i.e., a node in the movement graph. Edges connecting trajectory units form a complete trajectory. A social graph is used to model moving objects with social relationships. It contains a set of nodes and relationships. In addition, we also create two edge types $l{k}_g$ and $l{k}_s$ . $l{k}_g$ connects trajectory units in the movement graph and Voronoi region in the geographical graph, and $l{k}_s$ connects trajectory units in the movement graph and moving objects in the social graph. Based on this model, both moving objects’ trajectories and social relationships could be easily retrieved through multiple types of edges.

The contributions of this paper lie in the following aspects:

• A comprehensive GSM model is proposed to represent geographical space, trajectories and social relationships of moving objects in an integrated manner. The type system for this model is defined and a set of operators are designed. Signatures and semantics of operators are also provided.
• An implementation framework for a GSM model is proposed and implementation issues are addressed. A prototype based on the graph DBMS Neo4J [29] is implemented to verify the model.
• Extensive experiments with real-world geo social datasets are performed to evaluate the efficiency and performance of proposed GSM model. The results illustrated that the efficiency of queries enabled with GSM model outperforms the implementation based on the traditional relational DBMS.

The remainder of the paper is organised as follows. Section 2 summarizes related research work. Section 3 introduces the novel geo-social data model and elaborates on the basic concepts. Section 4 defines the data types and corresponding operators. Section 5 implements the presented data model and develops a prototype system. Section 6 conducts an experiment and analyses the results in detail. Finally, Section 7 concludes the paper and suggests future work.

2. Related Work

Early related studies on data models for moving objects focused on the representation of raw trajectories that consist of a temporal sequence of the positions of moving objects [4,17,30]. For example, the moving objects spatio-temporal (MOST) data model allowed the management of the current position of moving objects, and the prediction of future movement based on an important concept of the dynamic attribute that values change over time according to a given function of time [31,32,33]. Forlizzi et al. provided a discrete model for the abstract model presented by Guting and co-workers [34,35]. A discrete spatial–temporal-trajectory-based moving object database (DSTTMOD) that models trajectories as a function curve in three-dimensional space was developed [36]. It represents trajectories as a set of points, trajectory segments or a function $f\left(x\right)$ of time. However, semantic information of trajectories such as stay points, objects’ behaviour, contextual annotations or social relationships mentioned in our study was neglected [37,38]. Those data models for raw trajectories did not embrace different underlying environments such as free geographical spaces [6,37], networks [2,39], and indoor spaces [40,41,42]. Additionally, early related studies were more prone to simulate tracking data produced by a network-based generator [43], Oporto [44], GSTD [45], or GMOBench [46]. In addition, some research focused on the motion detection not only in dynamic scenes but also in static scenes based on the artificial neural network [47,48] and background subtraction techniques [49,50]. Chen and Huang presented a novel approach for vehicle detection based on probabilistic neural networks to detect moving vehicles in high bit-rate and low bit-rate video streams [51].

In recent years, with the development of location-based services, more and more mobile devices equipped with positioning technologies have generated massive real-world trajectories. Much additional information from the application context is considered in the modelling process. For example, the trajectories of a person can be interpreted as the sequences of points of interest such as a library, shopping mall, office building or museum. Hence, the research trends shift from raw trajectories to semantic trajectories [18,38,52,53,54]. A semantic trajectory can be defined as a trajectory enhanced with annotations such as activity, instant speed, transport mode and one or several complementary segmentations [37]. Among them, social relationships between moving objects are one of the important types of semantic information and need to be considered by the data management community, especially with respect to the trends of prevalent online social networks or location-based social networks [55]. This has provided the research motivation in the present paper. The first semantic model for trajectories represented a trajectory as a set of semantic places [53]. However, semantic information needs to be added to specific trajectory points. Zheni et al. introduced semantic activities into data model and presented a semantic model that depend on time geography theoretical framework [54,56]. Parent et al. incorporated semantic patterns and moving objects’ behaviour to model and survey privacy issues [37]. A multi-layer framework for semantic trajectories at different levels of abstraction called "SeMiTri" introduced the concept of annotation [38,57]. In this model, spatio-temporal positions are complemented with annotations. To model more semantic information for data mining, Bogorny et al. presented a semantic trajectory conceptual data model named CONSTAnt, which involves the concepts of semantic sub trajectories, semantic points, and geographical places, events and behaviour [52,58,59]. Damiani et al. proposed a data model of symbolic trajectories representing different types of semantics [60]. In addition, data models for semantic trajectories based on ontology have been presented. For instance, Hu et al. proposed an ontology design pattern for semantic trajectories [61]. Nogueira et al. leveraged ontology to represent dynamic characteristics of trajectories [62]. To add address domain-independent and application-specific geometric and semantic facets, Yan et al. proposed an ontology framework that involves geography ontology, application domain ontology and geometric trajectory ontology [63]. A meta-model based on ontology and event approach was proposed by Boulmakoul and co-workers [64]. Pelekis and co-workers presented a graph-based model that allows management of trajectories and their semantic information [17]. It uses dynamic graph representation of the semantic mobility timelines.

3. Modelling Geo-Social Data

In this section, we propose the basic idea of the GSM model and introduce its core components, including the geographical graph, social graph, and movement graph, and related issues.

First, let us reconsider the meaning of trajectory as follows. A person with many friends in the physical world or online social networks, moves around a point of interest (POI) such as a shopping mall or museum, does something over a period of time, follows new friends in social networks, and receives their messages and the latest news. This scenario is similar to that when we surf from one web page to other web pages. Therefore, geographical space and object movements can also be represented with a graph structure similar to that used in the modelling of web pages. More specifically, POIs or regions in geographical space can be modelled as nodes in a graph. Additionally, the active records in these regions can be represented as nodes with relationships to these regions and moving objects.

3.1. Geographical Graph

In the field of MOD, modelling the geographic space is beneficial to queries, e.g., finding all moving objects’ trajectories in a specific region. Many subdivision methods such as grid, triangular irregular network and Voronoi diagram have been adopted. Considering that objects often move around common POIs in free space, it is helpful to connect the trajectories with POIs. In order to keep an equal number of location points in each partitioned regions, the Voronoi diagram is an effective decomposition of geographical space according to the position of discrete POIs [65]. Each POI generates a Voronoi region V that involves all points closer to this POI than to any other in Voronoi-diagram-based subdivision. Given a set of discrete POIs $P=(p_1,\dots ,p_n)$ in geographical space, a Voronoi region can be defined as:

$$V\left(p_i\right)=\{q|d(q,p_i)\le d(q,p_j),i\ne j,p_i,p_j\in P\}$$

(1)

where $V\left(p_i\right)$ is a Voronoi region, q is an arbitrary point in space, and $d(q,p_j)$ is a distance function. This definition indicates that the distance from any point in the specific region to $p_i$ is smaller than to other points. Figure 1a shows an example of Voronoi region. The whole geographical space is divided into eight Voronoi regions based on eight POIs.

Under the space subdivision using a Voronoi diagram, a geographical graph can be regarded as a collection of nodes and edges. A Voronoi region is represented as a single node. An edge connecting adjacent Voronoi regions represents the spatial relationships between them. The types of spatial relationships refer to the OGC (Open Geospatial Consortium) compliant nine-intersection model that presents a comprehensive definition of topological relationships between spatial objects in two-dimensional space [66,67]. Figure 1b shows the structure of the geographical graph that contains eight nodes and one kind of relationship meet that represents two adjacent Voronoi regions.

3.2. Social Graph

Modelling social relationships between moving objects with graphs is taken for granted, where nodes correspond to a set of moving objects and edges correspond to a set of social relationships. The attributes of nodes could be static e.g., a name or type. The attributes of edges could be property fields representing a feature of social relationships in physical or cyber space.

In Figure 2, there are three objects ($O_1$,$O_2$ and $O_3$) and three types of social relationships (friends, followship, and colleagues). $O_1$ works with $O_3$, and $O_2$ is $O_1$’s friend. $O_2$ and $O_3$ follow each other on an online social network system.

3.3. Movement Graph

Movement graphs are designed to model the trajectories of moving objects. In our model, an object’s trajectory is split into trajectory segments using a Voronoi diagram as described by a geographical graph. Each segment is represented as a single graph node. The complete trajectory is modelled as a set of nodes. A set of edges is then generated to associate these nodes sequentially. Figure 3 shows an example of a movement graph. In Figure 3a, there are eight Voronoi regions divided by POIs (black points). The rectangle denotes location points of moving objects. As seen from the figure, an object’s location points are divided into four clusters. Hence, a definite trajectory $tra{j}_1$ for object $O_1$ can be modelled into four segments, namely $tuni{t}_1$, $tuni{t}_2$, $tuni{t}_3$, $tuni{t}_4$, as shown in Figure 3b.

In the fields of MOD and GIS, there are two kinds of trajectory modelling approaches: object-based and trip-based approaches [68]. The object-based modelling approach models a moving object’s continual locations as a single trajectory record. The complete trajectory of an object can thus be easily retrieved. It is also beneficial to human behaviour and mobility studies. However, this approach faces an oversize storage problem. In particular, when the time interval between two location points is too small, a trajectory may contain thousands of points.

Meanwhile, the trip-based modelling approach splits a continual trajectory into several trips i.e., a collection of smallest units of storage in a database system. The size of a trip is decided by segmentation methods, such as those employing regular time intervals and fixed lengths of trajectories. Although the trip-based modelling approach effectively avoids the oversize storage problem, it inevitably affects the efficiency of querying on whole trajectories because retrieving a complete trajectory that consists of a collection of segments requires the traversal of more records in a database. As shown in Figure 3b, all trajectories of an object can be easily retrieved with the proposed movement graph through graph traversal, which is similar to object-based modelling approaches. At the same time, the movement graph splits the whole trajectory into segments to keep the virtues of trip-based trajectory modelling approaches because the nodes in a movement graph naturally have links to nodes in the geographical graph (Voronoi regions).

Figure 4 illustrates an example of the proposed GSM model. A moving object’s trajectory $tra{j}_1$ is composed of four trajectory units $(tuni{t}_1,\dots ,tuni{t}_4)$. Each trajectory unit is connected to a specific Voronoi region and also connected to a moving object, such as the edge for trajectory $tra{j}_1$ to a moving object $O_1$.

4. Data Types and Operators

4.1. Data Types

With the concepts defined in Section 3, this section gives a formal definition of graphs involved in the GSM model and provides data types $G_g$,$G_s$, and $G_m$ to represent geographical space, social relationships and movement trajectories, respectively.

Definition 1 

(Basic types) Three basic types are used for the following definitions int, real and bool:

$$\underline{int}=Z$$

(2)

$$\underline{real}=R$$

(3)

$$\underline{bool}=\{true,false\}$$

(4)

Definition 2 

(Temporal types) Two time types are provided to represent the time instant and period:

$$\underline{instant}=R$$

(5)

$$\underline{period}=\{(s,e)|s,e\in \underline{instant}\}$$

(6)

Definition 3 

(Geometry types) The geometry types are employed from OGCs that release a series of specifications about geometry object models. The proposed GSM model involves three basic geometry types—point, line and polygon—to represent geographical space and trajectories.

$$\underline{point}=\{(lat,lon)|lat,lon\in \underline{real}\}$$

(7)

$$\underline{line}=\{(p{t}_1,p{t}_2,\dots ,p{t}_n)|p{t}_i\in \underline{point}\}$$

(8)

$$\underline{polygon}=\{(l_1,l_2,\dots ,l_n)|l_i\in \underline{line}\}$$

(9)

Definition 4 

(Geographical graph structure) The geographical space includes a set of Voronoi regions VR that are defined as:

$$VR=\{(rid,geom,p)|rid\in \underline{int},geom\in \underline{polygon},p\in \underline{point}\}$$

(10)

where rid is the identification of a Voronoi region, geom is represented by a geometry type polygon, and p denotes the point contained in the Voronoi region. Any position in this Voronoi region vr can then be defined as g_pos:

$$g_{pos}=\{(rid,pt)|rid\in \underline{int},pt\in \underline{point}\},$$

(11)

where rid is the identification of a Voronoi region and pt represents the latitude and longitude of the position.

A geographical graph structure $G_g$ is represented as a pair of nodes $V_g$ (Voronoi regions) and edges $E_g$ (spatial relations between Voronoi regions), and is defined as follows:

$$G_g=(V_g,E_g)$$

(12)

$$V_g=\{(v{r}_1,v{r}_2,\dots ,v{r}_n)|v{r}_i\in VR\}$$

(13)

In this paper, topological relationships $R_g$ are defined as:

$$R_g=\{<v{r}_i,v{r}_j,type>|v{r}_i,v{r}_j\in V_g,type\in (meet,equal)\}$$

(14)

The relationship meet denotes that Voronoi regions $v{r}_i$ and $v{r}_j$ are adjacent to each other. In addition, equal means that two regions are the same.

E_g represents a set of spatial relationships between Voronoi regions.

$$E_g=\{(gre{l}_1,gre{l}_2,\dots ,gre{l}_m)|gre{l}_i\in R_g\}$$

(15)

Definition 5 

(Social graph structure) A moving object is defined as:

$$MO=\{(mid,name,param),mid\in \underline{int},name\in \underline{string}\}$$

(16)

where mid and name are the identification and name of a moving object. In addition, param refers to the other attributes set of the object.

A social graph structure G_s is used to model moving objects and the social relations between them. It is defined as follows:

$$G_s=(V_s,E_s)$$

(17)

Here, $V_s$ denotes moving objects MO and $E_s$ denotes the social relations between two moving objects:

$$V_s=\{(m{o}_1,m{o}_2,\dots ,m{o}_n)|mo\in MO\}$$

(18)

$$E_s=\{(sre{l}_1,sre{l}_2,\dots ,sre{l}_m)|sre{l}_i\in R_s\}$$

(19)

$$R_s=\{<m{o}_i,m{o}_j,type>|m{o}_i,m{o}_j\in V_s,type\in \underline{string}\}$$

(20)

The string type of type represents social relations between moving objects, including colleagues, friendships, followership, interest groups or fan relationships, to name but a few.

Definition 6 

(Movement graph structure) A trajectory unit Traj_unit (sometimes called the sub-trajectory) of an object in a Voronoi region is defined as:

$$Tra{j}_{unit}=\{((mo,vr),{(t_i,g_{pos}^i,v_i)}_{i=1}^m)|mo\in MO,vr\in VR,t_i\in \underline{instant},v_i\in \underline{real}\}$$

(21)

where t_i denotes the time of location points and m denotes the count of location points. Then, a moving object’s trajectory can be modelled as a collection of trajectory units.

$$trajectory=\{(mo,{\displaystyle \sum _{i=1}^q}tuni{t}_i)|mo\in MO,tuni{t}_i\in Tra{j}_{unit}\}$$

(22)

A movement graph structure G_m is defined to represent the trajectories of moving objects. The novelty of this structure lies in the fact that the trajectory units that belong to a whole trajectory are represented as nodes of a graph. The geometry type line of segments is encoded with WKB (well-known binary) format representing vector geometry objects, and is stored as a binary attribute of a graph node. It is defined as:

$$G_m=(V_m,E_m)$$

(23)

$$V_m=\{(tuin{t}_1,tuin{t}_2,\dots ,tuin{t}_n)|tuin{t}_i\in Tra{j}_{unit}\}$$

(24)

The relationship E_m is defined as follows:

$$E_m=\{(mre{l}_1,mre{l}_2,\dots ,mre{l}_m)|mre{l}_i\in R_m\}$$

(25)

$$R_m=\{R_m^m,R_m^s,R_m^g\}$$

(26)

$$R_m^m=\{<tuni{t}_i,tuni{t}_j,type>|tuni{t}_i,tuni{t}_j\in V_m,type\in \underline{string}\}$$

(27)

$$R_m^s=\{<tuni{t}_i,m{o}_j,type>|tuni{t}_i\in V_m,m{o}_j\in V_s,type\in \underline{string}\}$$

(28)

$$R_m^g=\{<tuni{t}_i,v{r}_j,type>|tuni{t}_i\in V_m,v{r}_j\in V_g,type\in \underline{string}\}$$

(29)

where $R_m^m$ are used to represent the ordinal relations between trajectory segments that belong to the same trajectory. They help to easily retrieve the whole trajectory of a moving object. The relationships $R_m^s$ represent the relationships between segment tunit and object mo. $R_m^g$ represent the relationships between segment tunit and Voronoi regions vr. They provide the capability of finding all trajectories in a specific geographical Voronoi region.

4.2. Operators

In this section, we provide the bulk of operations on $G_g$ , $G_s$ and $G_m$, as illustrated in

Table 1. Definition of operations.

Operations	Signature
Select	$\underline{G_g}$ × string → VR
	$\underline{G_s}$ × string → MO
	$\underline{G_m}$ × string → $\underline{{Traj}_{unit}}$
Nodevalues	VR × string → string
	MO × string → string
	$\underline{{Traj}_{unit}}$ × string → string
Getnodes	MO × string → MO
	MO × string → VR
	MO × string → $\underline{{Traj}_{unit}}$
Getrajectory	MO × instant → trajectory
Atinstants	trajectory × instant → gpos
Atperiods	trajectory × period → $\underline{{Traj}_{unit}}$
Exinstants	trajectory × point → instant
Distance	trajectory × trajectory → real

. We use signature $\alpha \times \beta \to \delta$ to define operation signatures and semantics. It means that the data type variables α and δ could be instantiated; for example, int × int → int is used to multiply two numbers together.

Definition 7 select. 

The select operator receives the query condition such as the field value of attributes, and the specific graph layer of the GSM model, and returns all graph nodes that meet the condition. Depending on the hierarchical graph layers, it is written as $select(G_g,c)$, $select(G_s,c)$, or $select(G_m,c)$ for queries on a geographical graph, social graph, and movement graph, respectively, where c is the query condition.

For example, to find graph nodes with the name ’David’ over a social graph, the query expression is written as:

$$select(\underline{G_s},name{=}^{\prime }Davi{d}^{\prime })$$

(30)

Definition 8 nodevalues. 

The nodevalues operator extracts an attribute field’s value from graph node. For example, to find the email address of a moving object is written as:

$$nodevalues(\underline{mo},email)$$

(31)

Note that we define the type of return value as generic type string. In real word applications, many data type conversion operations are needed according to actual data types. For instance, the field age of a moving object belongs to int type.

Definition 9 getnodes. 

The getnodes operator retrieves the adjacent nodes according to a specific relationship value. For example, retrieving all trajectory segments of moving object mo is written as:

$$getnodes(\underline{mo},l{k}_s)$$

(32)

Benefitting from this graph structure, many query operations become more convenient than traditional relational database solution. For instance, the basic query ’finding all David’s friends’ needs many table-joint operations in the traditional table approach. In contrast, the query expression in the GSM model could be written as:

$$getnodes(\underline{mo},type=friends)$$

(33)

Definition 10 getrajectory. 

The getrajectory operator returns the whole trajectory trajectory of a moving object MO at specific date instant. For example, finding David’s trajectory at 22th July 2015 can be written as:

$$getrajectory(select(\underline{G_s},name{=}^{\prime }Davi{d}^{\prime }),2015-07-22)$$

(34)

The implementation of this operator relies on the operator getnodes.

Definition 11 atinstants. 

The atinstants operator returns any position of a moving object at the query time instant. For example, a query ’where is David at 10:00 on 22th July 2015’ can be written as:

$$atinstants(getrajectory(select(\underline{G_s},name{=}^{\prime }Davi{d}^{\prime }),2015-07-22),10:00)$$

(35)

This operator needs interpolated operation of trajectory between two adjacent points because of trajectories’ discreteness.

Definition 12 atperiods. 

The atperiods operator receives the query time condition period and the specific trajectory, and returns a trajectory unit tunit that meets the condition.

Definition 13 exinstants. 

The exinstants operator is a reverse operation of atinstants operator. It receives a coordinate and returns the time when an object passes through it.

Definition 14 distance. 

The distance operator calculates the minimum Euclidean distance between two trajectories. It finds all distance from a point of the first trajectory to any points of the second trajectory and returns the minimum value. It is written as:

$$distance(\underline{trajectory},\underline{trajectory})$$

(36)

5. Implementation

5.1. System Architecture

An implementation framework for the GSM model is shown in Figure 5. The framework has three major components: a storage engine, graph layer manager and algebra module.

The storage engine provides an underlying data storing solution for the GSM model’s composite graph structure. It is designed to support different database systems. For a graph database, the GSM model’s related structures can be stored as a basic property graph. The formats of WKB (Well-known binary) and WKT (Well-known text) can be used to represent Voronoi regions and trajectories of moving objects.

A graph layer manager provides a logic module of multiple management for the graph data, which provides more additional functions than native graph database systems that only provide methods of managing nodes and edges. In the GSM model, the graph layer manager deals with the social graph layer, movement graph layer, and geographical graph layer. In addition, the indexing structure is stored as an index graph layer.

Algebra modules group together a set of data types and operators related to the specific data model. The algebra plugin architecture provides a great deal of flexibility and control over data model implementation, similar to Secondo architecture [69,70].

5.2. Prototype Implementation

A prototype is implemented to verify the GSM model in the graph database management system Neo4J, as shown in Figure 6. GSMRoot denotes the root node of the graph database, with three child nodes (i.e., GG, MG, and SG) representing the root nodes for the geographical graph, movement graph, and social graph, respectively. The child nodes of the GG node are geographical Voronoi regions, with edges representing the spatial relationships between them. The MG node has many trajectory segments as child nodes. Similarly, the child nodes of SG nodes denote moving objects. In addition, trajectory segments have links with geographical Voronoi regions and moving objects.

Some query examples are listed and corresponding query statements are described as follows.

Query 1: What is Jack’s email address?

nodevalues(

select(Gs, name =′ jack′), email)

Query 2: Find all of Jack’s friends.

nodevalues(

getnodes(

select(Gs, name =′ jack′), friendship), name)

Query 3: Find the trajectory distance between Jack and John.

distance(

getrajectory(

select(Gs, name =′ jack′), 2015 − 07 − 22)

getrajectory(

select(Gs, name =′ John′), 2015 − 07 − 22)))

Query 4: Where was Jack at 10 a.m.?

atinstants(

getrajectory(

select(Gs, name =′ jack′), 2015 − 07 − 22), 10 : 00)

Query 5: Find Jack’s trajectories between 10 a.m. and 12 a.m.

atperiods(

getrajectory(

select(Gs, name =′ jack′), 2015 − 07 − 22), 10 : 00, 12 : 00))

Query 6: When did Jack pass Joy City shopping mall?.

exinstants(

getrajectory(

select(Gs, name =′ jack′), 2015 − 07 − 22), Joycity)

6. Experiments

6.1. Experimental Setting

Neo4J and Eclipse were used to implement the GSM data model on a standard personal computer with an Intel i7-4790 CPU and 8G RAM. Data collected from real-world LBSNs, namely Brightkite (BK) and Gowalla (GO), provided by the Stanford Network Analysis Project [19], were used to conduct experiments so as to verify the effects of the presented model. Data from Gowalla contained 196, 591 user nodes, 950, 327 friendship edges, and 6, 442, 890 check-in records, while data from Brightkite consisted of 58, 228 user nodes, 214, 078 friendship edges, and 4, 491, 143 check-in records. POIs were collected from the Census Bureau’s MAF/TIGER database. As shown in Figure 7, four states with more check-in records were chosen as the experimental regions; i.e., Washington (DC), California (CA), New York (NY), and Texas (TX).

Table 2. Experimental data.

	Voronoi Regions	Moving Objects	Social Relationships	Check-in Records
DC-GO	8655	5058	163,622	199,469
DC-BK	18,655	797	59,194	93,816
CA-GO	57,251	16,684	513,406	739,687
CA-BK	57,251	2450	142,136	293,542
NY-GO	21,657	12,388	391,144	364,940
NY-BK	21,657	1789	108,678	157,020
TX-GO	40,178	17,996	524,352	984,493
TX-BK	40,178	1328	99,528	111,247

describes the experimental data in detail.

Experiments were conducted to test the performance of queries with and without GSM model support. Considering the efficiency of managing various spatial-temporal data involved in a more general environment, the widely used relational database management system PostgreSQL with a spatial extension PostGIS was used to manage these original data but without GSM model support, as a comparison, where three tables—objects, socialrelation and trajectory—were created to store moving objects, social relationships and trajectories, respectively, by using the following SQL expressions:

• CREATE TABLE objects (moID int, email char, oname char);
• CREATE TABLE socialrelation (fromMOID int, relation char, toMOID int);
• CREATE TABLE trajectory (trajID int, traj geometry, oname char);

Additionally, in order to accelerate the query performance, we created three indices: idx_mo, idx_ids and idx_traj, as shown in the following SQL expressions.

• CREATE INDEX idx_mo ON objects (moID);
• CREATE INDEX idx_ids ON socialrelation (fromMOID, toMOID);
• CREATE INDEX idx_traj ON trajectory USING RTREE (traj).

Table 3. Tested query expressions for the GSM model.

	Query Expression
QE1	atinstants(
	getrajectory(
	select(Gs, name =′ Jack′), 2015 − 07 − 22), 10 : 00)
QE2	atinstants(
	getrajectory(
	getnodes(
	select(Gs, name =′ Jack′), friendship), 2015 − 07 − 22), 10 : 00)
QE3	atperiods(
	getrajectory(
	select(Gs, name =′ Jack′), 2015 − 07 − 22), (10 : 00, 12 : 00))
QE4	exinstants(
	getrajectory(
	getnodes(
	select(Gs, name =′ Jack′), friendship), 2015 − 07 − 22)), Joycity)

gives four query expressions used to evaluate the performance of the proposed GSM model. The query expression QE1 returns a moving object’s location at a specified time. QE2, a typical geo-social query, returns the locations of a moving objects’s friends at a specified time. The query expression QE3 retrieves a moving object’s trajectories in a definite region within a specified time period. Lastly, the query expression QE4 finds all trajectories of a moving object’s friends who moved around a specified region within a certain time period.

6.2. Experimental Results

Table 4. Performance of queries (CPU time/ms).

	QE1		QE2		QE3		QE4
	GSM Supp.	Naive Impl.	GSM Supp.	Naive Impl.	GSM Supp.	Naive Impl.	GSM Supp.	Naive Impl.
CA-BK	146	265	200	1082	213	256	185	2182
CA-GO	164	414	236	2771	150	385	189	3894
NY-BK	179	221	185	516	203	230	182	1474
NY-GO	158	282	219	865	142	273	171	1869
TX-BK	194	213	185	524	238	259	219	1528
TX-GO	164	513	220	10510	151	537	177	11593
DC-BK	186	199	173	318	202	204	167	1260
DC-GO	180	251	195	390	143	240	167	1367

* GSM Supp. means the implementation supported with GSM model; * Naive Impl. means the naive implementation.

gives the performance of different query expressions in a prototype system developed with the proposed GSM model support, and also in a naive implementation. With the increase in social relations or check-in records, the prototype system supported with the GSM model behaved more stably. This is because the operators getrajectory and getnodes have to be translated into time-consuming relational table join operations in the naive implementation. In contrast, the implementation supported with the GSM model adopted concurrent graph traversal operations to conduct these queries.

Figure 8 shows the relations between query performance and data volume. With the increase in check-in records or social relations of moving objects, the relational table join operations made the naive implementation impractical, whereas the performance of the implementation supported with the GSM model remained stable.

Figure 9 shows a schematic of a query (QE2 and QE4 are taken as examples) in the GSM-model-supported implementation. For QE2, we first used the operator getnodes to find Jack’s friends, and grabbed their trajectory nodes through edges $R_m^s$. The segment nodes satisfying the time condition were then used to retrieve the nodes of the Voronoi region through edges $R_m^g$, and return the final results of queries. A similar schematic of QE4 is also given in the figure.

7. Discussion

The present study proposes a GSM model for the integrated management and queries of moving objects’ trajectories, social relationships and underlying geographical space. However, there are still limitations worthy of attention.

Voronoi diagrams based on POIs are used to divide free geographical space into a bulk of Voronoi regions, and these regions are then abstracted as nodes of a geographical graph. This is suitable for the uneven spatial distribution of trajectories, especially for movement traces generated by an LBSN e.g., check-in records. Nevertheless, it also raises the problem of polygonal fragmentation because of the aggregation of POIs. In this case, there will be too many small Voronoi regions and trajectory segments. This will affect the efficiency of data management and queries. A preparatory POI clustering may be helpful in mitigating the problem.

The proposed GSM model can be finely tuned to support the representation of semantic information, such as stay points or an object’s behaviour, and even other activity environments such as indoor or network spaces. However, storing too much information through the attributes of nodes or edges will make the graphs overstaffed or redundant. For example, in movement graphs, some nodes may record too many location points and may hinder the querying or index performance to some extent. Compressing the trajectories and storing the attributes of graph nodes or edges with a binary system may be a useful strategy for solving the problem, with a trade-off with the efficiency of data retrieval.

The experiments conducted in this paper used check-in records from Gowalla and Brightkite systems. These records have notably different time intervals between two adjacent location points. Sometimes, objects might only have several check-in records in different locations on one day, and sometimes may have hundreds of records in a few hours. In contrast with the case for GPS-based trajectories, such as floating car data, these irregular time intervals will be a challenge to the query performance. Other kinds of trajectories will be further used to verify the proposed GSM model. In addition, the diversity of relationships for moving objects against performance will also need to be tested.

8. Conclusions

This paper presented a composite-graph-based data model for the integrated representation of trajectories, social relationships and geographical space for moving objects in free space in order to tackle management challenges related to the explosive growth of geo-social data. A bulk of user-defined data types and corresponding operators were proposed to facilitate geo-social queries on the moving objects. An implementing framework was presented and a prototype developed. Experiments for the proposed data types and operators were conducted to illustrate the efficiency of the data model. It is a step forward in the data modelling of moving objects in that it considers complex social relationships and large-scale geographical spaces, and even indoor spaces.

Further work will involve the development of a corresponding index structure and various query algorithms, and the distributed implementation of a data model using a large-scale graph commutating processing frameworks such as Pregel or Bulk Synchronous Parallel.