Nothing Special   »   [go: up one dir, main page]
Next Article in Journal
Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road Networks
Next Article in Special Issue
An Exploratory Study Investigating Gender Effects on Using 3D Maps for Spatial Orientation in Wayfinding
Previous Article in Journal / Special Issue
Interest Aware Location-Based Recommender System Using Geo-Tagged Social Media
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
IJGI
Volume 5
Issue 12
10.3390/ijgi5120246
ijgi-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Line Graph-Based Continuous Range Query Method for Moving Objects in Networks

by
Hengcai Zhang
1,2,
Feng Lu
1,2,3,* and
Jie Chen
1
1
State Key Lab of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101, China
2
Fujian Collaborative Innovation Center for Big Data Applications in Governments, Fuzhou 350003, China
3
Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China
*
Author to whom correspondence should be addressed.
ISPRS Int. J. Geo-Inf. 2016, 5(12), 246; https://doi.org/10.3390/ijgi5120246
Submission received: 31 May 2016 / Revised: 4 December 2016 / Accepted: 13 December 2016 / Published: 19 December 2016
(This article belongs to the Special Issue Location-Based Services)
Browse Figures
Figure 1
<p>An example of a network.</p> "> Figure 2
<p>Line graph structure.</p> "> Figure 3
<p>An example of bridgeable edges. (<b>a</b>) A query object in network; (<b>b</b>) The schematic of bridgeable edges</p> "> Figure 4
<p>Distance edge.</p> "> Figure 5
<p>Graph-based expansion tree.</p> "> Figure 6
<p>System architecture.</p> "> Figure 7
<p>GT-MobiSIM. (<b>a</b>) The simultion with 5000 moving objects and 500 query objects; (<b>b</b>) The simultion with 10,000 moving objects and 1000 query objects.</p> "> Figure 8
<p>The CPU time needed for the calculation of the query candidate.</p> "> Figure 9
<p>The average number of moving objects obtained in query results and the query candidate.</p> "> Figure 10
<p>Comparison of Stojanovic continuous range (StojanovicCR) and line graph-based continuous range (LGCR). (<b>a</b>) The result of the experiment with 5000 moving objects and 500 query objects; (<b>b</b>) The result of the experiment with 10,000 moving objects and 1000 query objects.</p> ">
Versions Notes

Abstract

:
The rapid growth of location-based services has motivated the development of continuous range queries in networks. Existing query algorithms usually adopt an expansion tree to reuse the previous query results to get better efficiency. However, the high maintenance costs of the traditional expansion tree lead to a sharp efficiency decrease. In this paper, we propose a line graph-based continuous range (LGCR) query algorithm for moving objects in networks, which is characterized by a novel graph-based expansion tree (GET) structure used to monitor queries in an incremental manner. In particular, GET is developed based on the line graph model of networks and simultaneously supports offline pre-computation to better adapt our proposed algorithm to different sizes of networks. To improve performance, we create a series of related data structures, such as bridgeable edges and distance edges. Correspondingly, we develop several algorithms, including initialization, insertion of objects, filter and refinement and location update, to incrementally re-evaluate continuous range queries. Finally, we implement the GET and related algorithms in the native graph database Neo4J. We conduct experiments using real-world networks and simulated moving objects and compare the proposed LGCR with the existing classical algorithm to verify its effectiveness and demonstrate its greater efficiency.

1. Introduction

With the advancement of wireless networks and the development of positioning technologies, such as GPS, RFID and WiFi, online location-based services and intelligent surveillance systems have attracted an increasing amount of attention [1,2,3,4,5,6,7]. Motivated by this, spatial-temporal queries for moving objects have been studied extensively in the fields of moving object databases (MOD) and geographical information systems (GIS) [8,9,10,11]. Many types of queries and corresponding efficient query algorithms have been proposed, such as range queries [12,13], k-nearest neighbor queries [14,15,16], reverse nearest neighbor queries [17], skyline queries [18], density queries [19,20] and visible nearest neighbor queries [21].
The widely-used and fundamental range queries for objects moving in Euclidean space or networks return a set of objects within a given area at a given query time [22,23,24,25,26,27]. This paper addresses the problem of processing continuous range queries for moving objects in networks. That is, querying objects and moving objects are both in high-speed motion and constrained by underlying networks. In contrast to snapshot range queries that are evaluated only once, the continuous range queries need to maintain activity over a period of time and continuously retrieve query results. Many real-world applications depend substantially on these types of queries, such as fleet monitoring, vehicle rescue and traffic control and management [28,29]. For example, because of the long journey to the railway station, we first need to take a bus and then take a taxi. In this situation, we need to receive the continuous notification of when and where can we get a transfer to a nearby taxi within 500 meters from the running bus.
The continuous evaluation of range queries leads to increasing challenges to efficiency and server workloads due to ensuring the completeness and correctness of query results [19,30]. It is not easy to answer the continuous range queries for moving objects in networks over a period of time. There are two approaches for continuous range queries. The incremental approaches characterized by maximizing the reuse of previous results have better efficiency than other approaches that split the continuous range query into discrete snapshot range queries [22,29,31]. However, it has a strong dependence on the design of in-memory data structures to maintain the reusable candidates, such as an expansion tree and a safe region [13,25,32]. However, when the scale of networks is large, but the distribution of moving objects is relatively sparse, these data structures require more online re-computation to maintain the up-to-date query candidates, because the objects frequently enter and leave the regions of the expansion tree [16,17]. That invalidates these data structures and results in performance degradation. Thus, we need to develop novel data structures to maintain query candidates.
In this paper, we present a novel line graph-based continuous range (LGCR) query algorithm for moving objects in networks. First, the network is modeled as a line graph G l g = ( V l g , E l g ) . Segments are represented as graph nodes V l g , and edges E l g (i.e., spatial relationships) connect two adjacent road segments. Additionally, we also model moving objects as a graph structure G m o . Based on the two relatively independent graph structures, a special edge E m o → l g from a node of the object’s graph G m o to a node on the line graph G l g represents the fact that an object is moving on a particular segment. An advantage of this design is that it provides more flexibility and control for the location update cost, because when a moving object turns into a new segment, this object only deletes the original edge and creates a new edge to reflect this change at the client side. Hence, this greatly reduces the location update cost and server workloads. Additionally, it is easier for the server to retrieve accurate moving objects using the special edge E m o → l g .
Additionally, we propose an innovative graph-based expansion tree (GET) structure that maintains the candidate moving objects. It creates a unique query node v q for each query request and then creates a set of edges E q → l g to represent candidate relationships between a query node v q and line graph node v l g . Hence, given that the update cost of GET depends on the cost of deleting or creating edges E q → l g , server workloads are reduced further. We implement the LGCR query algorithm and related data structures in the native graph database system Neo4J. We perform the experimental evaluation using a simulated dataset generated by GT-MobiSIMto demonstrate efficiency and performance compared with a classical continuous range query algorithm. The contributions of this paper lie in the following aspects:
  • We develop a novel graph-based expansion tree (GET) based on the line graph model of networks. It supports offline pre-computation and could effectively reduce the online maintenance time of the traditional expansion tree in continuous queries.
  • Based on GET, we propose a line graph-based continuous range (LGCR) query algorithm for moving objects in networks, including the algorithms for initialization, insertion, location update, filter and refinement.
  • We conducted experiments to evaluate our proposed LGCR using real-world networks and simulated moving objects and compare with existing classical algorithms to verify its effectiveness.
The remainder of this paper is organized as follows. Section 2 summarizes the related work. Section 3 presents the related data structures for continuous range queries in networks. Section 4 elaborates on the proposed LGCR query algorithm. Section 5 illustrates the experimental setting and results. Finally, Section 6 concludes the paper and proposes further developments.

2. Related Work

A straightforward approach to process continuous range queries is to split them into discrete snapshot range queries [8,16,33]. Wang et al. proposed the moving objects in road networks (MOVNet) algorithm to process continuous queries based on snapshot range queries for moving objects on road networks [34]. It introduced several significant features and a shortest distance-based tree (SD-tree), which was used to maintain network connectivity and network distance information to alleviate the effects of frequent object updates in continuous range queries. Kolahdouzan et al. developed an upper bound algorithm to improve the performance of continuous k-nearest neighbor queries by only performing snapshot queries at the location where they are required [16]. The UNICONS algorithm divided a query path into multiple subpaths based on the similarity principle and computed valid intervals. The query results for subpaths were combined to obtain the final results [8]. The advantage of this approaches is that the existing methods of snapshot range queries can be directly applied to continuous range queries without a drastic adjustment. However, the shortcoming is how to efficiently find the split points, which specify the location and time instant that keep the results of range queries the same. If a query algorithm is repeatedly evaluated at every time instant, performance obviously degrades. However, if a query algorithm is evaluated over long time intervals, query accuracy cannot be guaranteed.
Another widely-used strategy employs the incremental approaches adopted in our paper. The evaluation cost of continuous range queries could be reduced by reusing history results maintained by in-memory specific data structures. In particular, when updates from moving objects fall in this tree, they triggered a change of query results. In contrast, irrelevant updates were ignored [9,25]. Mouratidis et al. proposed an expansion tree structure in the incremental monitoring algorithm (IMA) and group monitoring algorithm (GMA) [32]. The algorithms start with the position of the querying object at network distance q . k N N _ d i s t , traverse around road segments and construct an expansion tree. Then, IMA/GMA monitor the changes of the query object and moving object’s position, prune this expansion tree structure and reuse the candidate results to produce the query result of continuous queries. Similarly, the concept of the safe regions that calculate the closest moving objects to the border of the query was proposed to minimize the communication and computational cost of continuously monitoring a moving range query [35]. The concept of safe exits was proposed as the concise representation of the safe region that captures the border of the network-based safe region. Additionally, efficient algorithms for computing safe exits were developed [11,36]. Range Euclidean restriction (RER) and range network expansion (RNE) are well-known query processing algorithms based on this idea [37]. However, large-scale networks could decrease the performance of continuous queries based on the expansion tree because of high maintenance costs. Hence, the proposed GET in this paper expands and optimizes the original expansion tree structure. Simultaneously, it supports offline pre-computation to make our proposed have algorithm higher reliability for different sizes of networks.

3. Proposed Data Structures

In this section, we elaborate on related data structures in the LGCR query algorithm, which includes line graph, distance graph and GET.
Figure 1 illustrates an example of a city network G n e t including 12 segments ( s 1 , s 2 , … , s 12 ) and 13 junctions ( j 1 , j 2 , … , j 13 ) . Nine moving objects (green points) are moving along the network and sending location updates to a server. The query object q (yellow points) continually issues range queries over a period of time.
(1) Basic types:
We present a set of basic types used for the definitions in the following parts. Three basic types are proposed for the following definitions:
i n t = Z
r e a l = R
b o o l = { t r u e , f a l s e }
Two time types are provided to represent the time:
i n s t a n t = R
p e r i o d = { ( s , e ) | s , e ∈ i n s t a n t }
The geometry types are employed from OGC, which releases a series of specification about the geometry object model. The proposed LGCR involves three basic geometry types:
p o i n t = { ( l a t , l o n ) | l a t , l o n ∈ r e a l }
l i n e = { < p t 1 , p t 2 , . . . , p t n > | n ∈ i n t , ∀ i ∈ [ 1 , n ] , p t i ∈ p o i n t }
p o l y g o n = { < l 1 , l 2 , . . . , l n > | n ∈ i n t , ∀ i ∈ [ 1 , n ] , l i ∈ l i n e }
(2) Line graph structure:
The network G n e t includes a set of segments S e g . Let the domain of segments be defined as follows:
S e g = { ( s i d , l , g e o , s t a r t ) | s i d ∈ i n t , l ∈ r e a l , g e o ∈ l i n e , s t a r t ∈ { s m a l l e r , l a r g e r } }
with an identifier s i d , length l and the flag s t a r t that defines the orientation of a geometric line g e o .
The line graph G l g is another graph in which each vertex of G l g represents a segment of G n e t . The formal definition is given as follows:
G l g = ( V l g , E l g )
where:
V l g = { < s e g 1 , s e g 2 , . . . , s e g n > | n ∈ i n t , ∀ i ∈ [ 1 , n ] , s e g i ∈ S e g }
and:
E l g = { < g r e l 1 , g r e l 2 , . . . , g r e l n > | n ∈ i n t , ∀ i ∈ [ 1 , n ] , g r e l i ∈ R g }
E g represents a set of spatial relationships between two segments. We employ OGC-compliant nine-intersection model, which presents a comprehensive definition of topological relationships between spatial objects in two-dimensional space [38,39]. In this paper, topological relationships R g are defined as follows:
R g = { ( s e g i , s e g j , t y p e ) | s e g i , s e g j ∈ V l g , t y p e ∈ { m e e t , e q u a l } }
where the relationship m e e t denotes the case in which segments s e g i and s e g j are adjacent to each other and e q u a l denotes the case in which two segments are the same.
Figure 2 illustrates an example of a line graph that corresponds to the network in Figure 1. The segment s 1 is modeled as a graph node. The connecting relationship between segments s 1 and s 2 is constructed as spatial relationships m e e t .
(3) Object graph structure:
A moving object is defined as follows:
M o = { ( m i d , n a m e , p a r a m ) | m i d ∈ i n t , n a m e ∈ s t r i n g }
where m i d and n a m e denote the identification and name of the object and p a r a m represents the set of other attributes of the object.
The object graph structure models moving objects and the social relations between them. It is defined as follows:
G m o = ( V m o , E m o )
where V m o denotes moving objects and is defined as follows:
V m o = { < m o 1 , m o 2 , . . . , m o n > | n ∈ i n t , ∀ i ∈ [ 1 , n ] , m o i ∈ M o }
and E m o denotes the social relations between two moving objects and is defined as follows:
E m o = { < s r e l 1 , s r e l 2 , . . . , s r e l n > | n ∈ i n t , ∀ i ∈ [ 1 , n ] , s r e l i ∈ R m o }
where:
R m o = { ( m o i , m o j , t y p e ) | m o i , m o j ∈ V m o , t y p e ∈ s t r i n g }
and the t y p e represents social relationships between moving objects.
(4) Network location
A moving object’s network position g l o c is defined as follows:
g l o c = { ( s i d , d ) | s i d ∈ int , d ∈ r e a l , 0 ≤ d ≤ l }
where s i d is an identifier of the segment and d represents a real number that provides a position on that segment.
An object’s moving vector m v e c t o r at time t is defined as follows:
m v e c t o r = { ( m i d , g l o c , v , t ) | m i d ∈ i n t , v ∈ r e a l , t ∈ i n s t a n t }
where m i d is an identifier of a moving object, g l o c denotes the objects’ network position on a certain segment and v denotes the instantaneous velocity at time t.
(5) Bridgeable edges:
E m o → l g connects a moving object and segment to represent the case in which a moving object moves on the segment and is defined as follows:
E m o → l g = { < m l r e l 1 , m l r e l 2 , . . . , m l r e l n > | n ∈ i n t , ∀ i ∈ [ 1 , n ] , m l r e l i ∈ R m o l g }
where:
R m o l g = { ( m o i , s e g j , t y p e ) | m o i ∈ V m o , s e g j ∈ V l g , t y p e ∈ s t r i n g }
Figure 3 illustrates an example of bridgeable edges, where a query object q travels from segment s 1 to segment s 2 , as shown in Figure 3a. The edge (blue arrow line) from node s 1 to node q will be deleted, and a new edge (red arrow line) from node s 5 to node q will be created, as shown in Figure 3b.
(6) Distance edges
The network distance calculation is the most time-consuming operation. Offline pre-computation network distance could effectively improve the algorithm’s efficiency [16]; we create distance edges E l g → l g to represent network distance. Then, we could use the convenient graph traversal operation to retrieve the distance value with lower query cost.
E l g → l g represents a set of edges between any two line graph nodes. Its attributes store the network distance value between two segments and is defined as follows:
E l g → l g = { < l l r e l 1 , l l r e l 2 , . . . , l l r e l n > | n ∈ i n t , ∀ i ∈ [ 1 , n ] , l l r e l i ∈ R l g l g }
where:
R l g l g = { < s e g i , s e g j , d e d g e > | s e g i , s e g j ∈ V l g , d e d g e ∈ r e a l }
We introduce the concept of edge distance d e d g e , which is defined as the distance between two edges (i.e., road segments) according to the node types of the segments [40]. The edge distance can be classified into four types: S S , S E , E S , E E , where E S defines the distance from the end node E of e d g e i to the start node S of e d g e j . Distance types S E , E S and E E are defined similarly.
As shown in Figure 4, the moving object qthat issues continuous range queries as it moves along segment s 2 . d e s ( s 2 , s 3 ) is defined as the distance from j 2 − e to j 3 − s , and d e s ( s 1 , s 2 ) is defined as the distance from j 1 − e to j 2 − s .
(7) Graph-based expansion tree:
GET includes a set of segments and is defined as follows:
G E T = { ( s e g q , ( s e g 1 , . . . , s e g n ) ) | n ∈ i n t , ∀ i ∈ [ 1 , n ] , s e g q , s e g i ∈ V l g } , ∀ i ∈ { 1 , 2 , . . . , n } , d e d g e ( s e g q , s e g i ) < r g
where r g denotes the given distance parameters of continuous range queries and s e g q denotes the segment on which the query object moves. Clearly, segment s e g q and input parameters r g are critical for computing GET. Hence, for each segment in a network, we could precompute GET offline to improve the LGCR query algorithm’s efficiency.
Figure 5 illustrates an example of GET. When the querying object q leaves the segment s 1 , GET has to be recalculated to maintain up-to-date candidate results. Given that GET has already been precomputed, this significantly reduces the time required to process the LGCR query algorithm.

4. LGCR Query Algorithm

Based on the proposed data structures, the proposed LGCR query algorithm for moving objects in networks includes several algorithms for initialization, insertion, location update, filter and refinement, as shown in Figure 6.

4.1. Algorithms

(1) Initialization:
The initialization of the LGCR query algorithm constructs the line graph structures and finishes the creation process of distance edges according to Algorithm 1. The input parameter of the algorithm is the network. To improve the efficiency of the LGCR query algorithm, we create an R-tree I r t r e e to index the segments, as shown in Line 2, which traverses all of the segments and creates corresponding graph nodes on line graph G l g , as shown in Lines 4–5. Then, the algorithm searches the adjacent segment nodes and creates connective edges to maintain complete topological relationships between the segments (Lines 8–10). Simultaneously, it constructs a minimum bounding rectangle (MBR) approximation of segments and links the leaf node of I r t r e e to the corresponding segment nodes (Lines 6–7). Next, the algorithm traverses all segments to calculate the network edge distance between any two segments and constructs distance edges (Lines 13–20).
Finally, the algorithm traverses the segment node on the line graph and retrieves adjacent road segment nodes (Lines 22–23). Then, it obtains the value of the network edge distance d e d g e . If the edge distance d e d g e is less than the input continuous query range parameter r g , an edge is created and inserted into the line graph structure (Lines 24–27). Note that the initialization could only be executed once for the LGCR query algorithm.
Algorithm 1: Initialization algorithm.
Ijgi 05 00246 i001
(2) Insertion of moving objects and query objects:
As illustrated in Algorithm 2, the insertion of the moving object constructs a node. Then, the algorithm locates corresponding road segments on which this object is moving and builds bridgeable edges E m o → l g (Lines 3–7).
Algorithm 2: Insertion of moving objects and query objects.
Ijgi 05 00246 i002
(3) Filter and refinement step for the LGCR query algorithms:
Algorithm 3 illustrates the filter and refinement step of the LGCR query algorithm. The filter step traverses GET to locate all of the candidate moving objects using bridgeable edges E m o → l g , as shown in Line 1. The refinement step is performed periodically. The algorithm traverses the candidate results and determines whether the moving object’s current time and network distance to the query object satisfy the given continuous range query condition (Lines 3–8). If the lifecycle of the LGCR query algorithm contains the object’s current time and the object’s location intersects the query range, then the candidate object is moved into the set of incremental query results (Line 6).
Algorithm 3: Filter and refinement step.
Ijgi 05 00246 i003
(4) Location update of moving objects:
There are three types of location update strategies for moving objects: speed-threshold-triggered location update (STTLU), distance-threshold-triggered location update (DTTLU) and ID-triggered location update (IDTLU) [41]. Given that the location update will be triggered by the moving object turning into a new road segment, the IDTLU strategy is more appropriate for the LGCR query algorithm. Algorithm 4 manages those location updates. First, it locates the object n o d e m o that needs to be updated according to the identifier m i d . Simultaneously, the old road segment n o d e l g o l d could be easily retrieved using the bridgeable edges E m o → l g (Lines 1–2). Then, Lines 3–4 update the object n o d e m o value with a new location and time from the location updates. Additionally, it creates a new bridgeable edge to a new segment. Next, when the object belongs to the query object, GET needs to be updated, as shown in Line 7. Otherwise, the filter and refinement step needs to be performed (8–12).
Algorithm 4: Location update of a moving object or query object.
Ijgi 05 00246 i004

4.2. Analysis of the Algorithm’s Complexity

Assume that there are E edges on networks, M moving objects and Q query objects. The time complexity of the LGCR query algorithm could be defined as follows:
T = T f i l t e r + T u p + T r e f
where T f i l t e r denotes the CPU time required for the calculation of query candidates obtained by GET, T u p denotes the CPU time required for location updates and T r e f denotes the CPU time required for the refinement step. The time required to retrieve query candidates includes the GET traversal time. Then, the complexity T f i l t e r of this algorithm is defined as O ( Q n ) . The location update of objects triggers an edge operation, and the time complexity of T u p is O ( M n ) . The time required to calculate the network distance depends on the graph traversal time because of the distance edges. Then, the time complexity T r e f depends on the size of the candidate results and is defined as O ( Q M n ) .

5. Experiments

5.1. Experimental Settings

We conducted experiments on a standard personal computer with an Intel i7-4790 CPU, 8G RAM and a 1-TB mechanical hard disk. We used the generator GT-MobiSIM [42] driven by an XML configuration file to simulate moving objects, and query objects were randomly selected to issue continuous range query requests. In order to test the performance and efficiency of our proposed LGCR, we prepared two experiments. The first experiment simulated 5000 moving objects in a network and randomly selected 500 query objects to issue continuous range query requests with different range parameters, as shown in Figure 7a. The second experiment simulated 10,000 moving objects and randomly selected 1000 query objects, as shown in Figure 7b. As illustrated in the figure, the red points were moving objects, and the blue points were querying objects. The input employed real network datasets from Beijing, with 26,220 segments and 18,856 intersections. The generator included various mobility models in networks, such as random waypoint and random trip. Additionally, there were three ways to represent continuous-time traces, including the location step-function, velocity set-function and acceleration step-function. It also included various parameter distributions for moving objects, such as the Gaussian distribution and normal distribution. In experiments, we set the parameter distribution to the Gaussian distribution, and each moving object followed the shortest path to the final destination generated from a predefined random waypoint mobility model. The related data structures were implementation using the native graph database Neo4J 1.9.7. The proposed LGCR query algorithm was implemented using Java as the main programming language and Eclipse as the development environment.
For comparison, we used the classical algorithm proposed by Stojanovic et al., known as StojanovicCR [13] for a continuous range query over moving objects in networks with high efficiency and effectiveness, which satisfied real-world, location-based services and applications. This algorithm generated a series of in-memory data structures, segment R*-tree (SR*-tree), continuous query table (CQT), network connectivity table (NCT) and mobile object table (MOT), to support the evaluation of the continuous range query. In particular, the SR*-tree extended R*-tree to store MBR information of road segments. The leaf node entry of SR*-tree was represented as ( s e g i d , m b r , o l i s t , q l i s t ) , where m b r was the minimum bounding rectangle, o l i s t and q l i s t denoted the list of objects and querying objects moving along the road segment with the identifier s e g i d . The NCT table stored connectivity information of the road segments. An NCT table entry was represented as ( s e g i d , r t E n t r y , s e g L e n g t h , s t a r t C o n , e n d C o n ) , where s e g i d was the identifier of road segment, r t E n t r y denoted the pointer to SR*-tree, s e g L e n g t h represented the length of road segment an the elements s t a r t C o n and e n d C o n denoted the lists of adjacent road segments. The CQT table stored information of continuous range queries. A CQT entry was represented as ( q i d , o i d , r a n g e , v a l i d P e r i o d , a n s w e r S e t ) , where q i d was the identifier of continuous range queries, o i d denoted the querying object, r a n g e defined the range parameters, a n s w e r S e t denoted the initial query answer and v a l i d P e r i o d represented the valid period of the query. The MOT table stored the information of moving objects. A MOT entry was represented as ( m o i d , l o c , t i m e , s p e e d , q u e r y S e t ) , where m o i d was the identifier of moving objects, l o c was the current location at the time t i m e and s p e e d denoted the current velocity. The q u e r y S e t represented the list of queries in which this object participates. The innovative StojanovicCR introduced a pre-refinement step to further refine the moving objects by the filter step in a traditional query processing strategy. First, according to the query condition, the filter-step selected the candidate moving objects using the SR*-tree index. The pre-refinement step was to further refine the moving objects obtained by the filter step. The refinement step was preformed periodically by processing the candidate objects generated by the pre-refinement step and generated the query answer.

5.2. Experimental Results

The initialization of LGCR took about 983 seconds in the experiment. It mainly included the three following parts: importing networks, building the proposed data structures and constructing the GET structure. GET is the key to improving the performance of the LGCR query algorithm in an incremental manner. According to the query range, queries are classified into different groups. We calculate the average calculation time of the query candidate for each group with the same query range. Figure 8 illustrates the time taken to retrieve candidate objects using GET. The results show that retrieving candidate objects required more CPU time as the query range increased. Given that the basic operation is graph traversal in GET, the large query range requires more graph traversal operations, which results in more time consumed.
Figure 9 illustrates that the average number of moving objects in the query results (orange bar) is very close to the average number of moving objects in the candidate results (blue bar). The average utilization ratio of candidate objects retrieved by GET increased to 81.2%, that is GET effectively maintained the reusable candidate moving object for incremental continuous range queries for the LGCR query algorithm. The basic unit of GET is a road segment. Hence, the length of a road segment is related to the number of candidates. A longer road segment led to the ratio between the query results and candidate results decreasing. The average length of road segments in Beijing in the experiments was 202.25 meters, which is a relatively short distance; hence, GET maintains more accurate candidate sets.
Figure 10a shows the average CPU time per query in the experiment with 5000 moving objects and 500 query objects. Figure 10b illustrates the experimental results with 10,000 moving objects and 1000 query objects. The experimental results show that the LGCR query algorithm provided better performance and stability for the evaluation of continuous queries than StojanovicCR. The average CPU time per query for both approaches generally increased as the query range increased. StojanovicCR required more time to update in-memory data structures, such as SR*-tree, MOT and CQT. The LGCR query algorithm also triggered longer execution times for query candidates for continuous range queries. However, the basic graph operators, such as creating or deleting edges and graph traversal, were less time consuming. Hence, the LGCR query algorithm was more stable and efficient. In addition, the proposed distance edges and GET support offline pre-computation and could further improve the LGCR’s efficiency.

5.3. Discussion

The proposed LGCR query algorithm was efficient for continuous range queries over moving objects in networks. However, there are still limitations worthy of attention.
(1) For the LGCR query algorithm, special data structures, including bridgeable edges, distance edges and the GET and offline precomputation steps, significantly improved efficiency. However, an oversized network scale made these preprocessing steps very time consuming and required massive storage space. In addition, our proposed LGCR could be easily extended to support geo-social queries because that the ObjectGraph structure has the capability of modeling social relationships between moving objects, such as colleagues, friendships, followership, interest groups or fan relationships.
(2) As the key task of the LGCR query algorithm, the basic unit of GET contained a set of segments. However, those segments had no obvious physical meaning; they could not adapt well to conceptual entities in real-world complex road network environments [2,15]. The concept of routes corresponding to highways or expressways in the real world could be introduced to model road networks. Hence, a composite GET that contains both road segments and routes could further improve the flexibility of the LGCR query algorithm.
(3) We assumed that the network structure changed little and that updates mainly considered the location updates of moving objects. However, in a real-world scenario, the weight of a segment always changes with traffic information, and new road segments might be inserted. These influencers would affect the query results of continuous range queries. Hence, more types of updates should be considered to make the LGCR query algorithm more extensive.

6. Conclusions

Motivated by a substantial need for location-based services and applications for spatial-temporal queries, we presented a novel LGCR query algorithm that depended on a line graph structure and GET structure that could solve the problem of the efficient processing of continuous range queries over massive moving objects in networks. The algorithm can be applied directly to real-world location-based services and applications.
Future work needs to implement parallel processing of continuous range queries based on the LGCR query algorithm to further improve performance. The benefits of the proposed data structure include the line graph mode and GET structure; the proposed LGCR query algorithm is easy to deploy in distributed computing environments with the help of a large-scale graph commutating processing framework, such as Pregel and bulk synchronous parallel (BSP).

Acknowledgments

This research was supported by the State’s Key Project of Research and Development Plan (Grant No. 2016YFB0502104) and the National Natural Science Foundation of China (Grant No. 41401460, 41571431, 41421001). Additionally, we would also like to thank the anonymous referees for their helpful comments and suggestions.

Author Contributions

Hengcai Zhang and Feng Lu provided the core idea for this study. Hengcai Zhang implemented the LGCR query algorithm and carried out the experimental validation. Hengcai Zhang and Feng Lu wrote the main manuscript. Jie Chen made the important comments and suggestions for this paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Wolfson, O.; Xu, B.; Chamberlain, S.; Jiang, L. Moving objects databases: Issues and solutions. In Proceedings of the 10th International Conference on Scientific and Statistical Database Management, Washington, DC, USA, 1–3 July 1998.
  2. Güting, R.H.; Ding, Z. Modeling and querying moving objects in networks. Int. J. Very Large Data Bases 2006, 15, 165–190. [Google Scholar] [CrossRef]
  3. Ciuonzo, D.; Buonanno, A.; D’Urso, M.; Palmieri, F.A. Distributed classification of multiple moving targets with binary wireless sensor networks. In Proceedings of the 2011 Proceedings of the 14th International Conference on Information Fusion (FUSION), Chicago, IL, USA, 5–8 July 2011.
  4. Buonanno, A.; D’Urso, M.; Prisco, G.; Felaco, M.; Meliadò, E.; Mattei, M.; Palmieri, F.; Ciuonzo, D. Mobil sensor networks based on autonomous platforms for homeland security. In Proceedings of the 2012 Tyrrhenian Workshop on Advances in Radar and Remote Sensing (TyWRRS), Naples, Italy, 12–14 September 2012.
  5. Parent, C.; Spaccapietra, S.; Renso, C.; Andrienko, G.; Andrienko, N.; Bogorny, V.; Damiani, M.L.; Gkoulalas-Divanis, A.; Macedo, J.; Pelekis, N. Semantic trajectories modeling and analysis. ACM Comput. Surv. 2013, 45, 1–42. [Google Scholar] [CrossRef]
  6. Shekhar, S.; Jiang, Z.; Ali, R.Y.; Eftelioglu, E.; Tang, X.; Gunturi, V.; Zhou, X. Spatiotemporal Data Mining: A Computational Perspective. ISPRS Int. J. Geo-Inf. 2015, 4, 2306–2338. [Google Scholar] [CrossRef]
  7. Zheng, Y. Trajectory data mining: An overview. ACM Trans. Intell. Syst. Technol. 2015, 6, 1–29. [Google Scholar] [CrossRef]
  8. Cho, H.-J.; Ryu, K.; Chung, T.-S. An efficient algorithm for computing safe exit points of moving range queries in directed road networks. Inf. Syst. 2014, 41, 1–19. [Google Scholar] [CrossRef]
  9. Xuan, K.; Zhao, G.; Taniar, D.; Rahayu, W.; Safar, M.; Srinivasan, B. Voronoi-based range and continuous range query processing in mobile databases. J. Comput. Syst. Sci. 2011, 77, 637–651. [Google Scholar] [CrossRef]
  10. Zhu, T.; Wang, C.; Lv, W.; Huang, J. Continuous range monitoring of moving objects in road networks. In Proceedings of the 2010 10th International Conference on Intelligent Systems Design and Applications (ISDA), Cairo, Egypt, 29 November–1 December 2010.
  11. Yung, D.; Yiu, M.L.; Lo, E. A safe-exit approach for efficient network-based moving range queries. Data Knowl. Eng. 2012, 72, 126–147. [Google Scholar] [CrossRef]
  12. Zheng, K.; Trajcevski, G.; Zhou, X.; Scheuermann, P. Probabilistic range queries for uncertain trajectories on road networks. In Proceedings of the Proceedings of the 14th International Conference on Extending Database Technology, Uppsala, Sweden, 21–24 March 2011.
  13. Stojanovic, D.; Papadopoulos, A.N.; Predic, B.; Djordjevic-Kajan, S.; Nanopoulos, A. Continuous range monitoring of mobile objects in road networks. Data Knowl. Eng. 2008, 64, 77–100. [Google Scholar] [CrossRef]
  14. Huang, Y.K.; Chen, Z.W.; Lee, C. Continuous k-nearest neighbor query over moving objects in road networks. Adv. Data Web Manag. 2009, 5446, 27–38. [Google Scholar]
  15. Jensen, C.S.; Kolářvr, J.; Pedersen, T.B.; Timko, I. Nearest neighbor queries in road networks. In Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, New Orleans, LA, USA, 3–8 November 2003.
  16. Kolahdouzan, M.R.; Shahabi, C. Continuous k-nearest neighbor queries in spatial network databases. In Proceedings of the STDBM’04, Toronto, ON, Canada, 30 August 2004.
  17. Safar, M.; Ibrahimi, D.; Taniar, D. Voronoi-based reverse nearest neighbor query processing on spatial networks. Multimedia Syst. 2009, 15, 295–308. [Google Scholar] [CrossRef]
  18. Safar, M.; El-Amin, D.; Taniar, D. Optimized skyline queries on road networks using nearest neighbors. Pers. Ubiquitous Comput. 2011, 15, 845–856. [Google Scholar] [CrossRef]
  19. Hao, X.; Meng, X.; Xu, J. Continuous density queries for moving objects. In Procedings of the ACM International Workshop on Data Engineering for Wireless and Mobile Access, Vancouver, BC, Canada, 13 June 2008.
  20. Jensen, C.S.; Lin, D.; Ooi, B.C.; Zhang, R. Effective Density Queries on Continuously Moving Objects. In Procedings of the International Conference on Data Engineering, Atlanta, GA, USA, 3–8 April 2006.
  21. Gao, Y.; Zheng, B.; Chen, G.; Li, Q.; Guo, X. Continuous visible nearest neighbor query processing in spatial databases. VLDB J. 2011, 20, 371–396. [Google Scholar] [CrossRef]
  22. Alamri, S.; Taniar, D.; Safar, M. A taxonomy for moving object queries in spatial databases. Future Gener. Comput. Syst. 2014, 37, 232–242. [Google Scholar] [CrossRef]
  23. Gaede, V.; Günther, O. Multidimensional access methods. ACM Comput. Surv. 1998, 30, 170–231. [Google Scholar] [CrossRef]
  24. Guo, X.; Zheng, B.; Ishikawa, Y.; Gao, Y. Direction-based surrounder queries for mobile recommendations. VLDB J. 2011, 20, 743–766. [Google Scholar] [CrossRef]
  25. Jung, H.; Kim, Y.S.; Chung, Y.D. QR-tree: An efficient and scalable method for evaluation of continuous range queries. Inf. Sci. 2014, 274, 156–176. [Google Scholar] [CrossRef]
  26. Tao, Y.; Xiao, X.; Cheng, R. Range search on multidimensional uncertain data. ACM Trans. Database Syst. 2007, 32, 1–15. [Google Scholar] [CrossRef]
  27. Xu, J.; Güting, R.H.; Zheng, Y. The TM-RTree: An index on generic moving objects for range queries. GeoInformatica 2015, 19, 487–524. [Google Scholar] [CrossRef]
  28. Sowell, B.; Salles, M.V.; Cao, T.; Demers, A.; Gehrke, J. An experimental analysis of iterated spatial joins in main memory. Proc. VLDB Endow. 2013, 6, 1882–1893. [Google Scholar] [CrossRef]
  29. Taniar, D.; Rahayu, W. A taxonomy for region queries in spatial databases. J. Comput. Syst. Sci. 2014, 81, 1508–1531. [Google Scholar] [CrossRef]
  30. Huang, Y.K.; Lin, L.F.; Chung, Y.C.; Su, I.F. Continuous min-max distance bounded query in road networks. In Web Technologies and Applications; Springer: Berlin, Germany, 2012; pp. 423–434. [Google Scholar]
  31. Long, J.A.; Nelson, T.A. A review of quantitative methods for movement data. Int. J. Geogr. Inf. Sci. 2013, 27, 292–318. [Google Scholar] [CrossRef]
  32. Mouratidis, K.; Yiu, M.L.; Papadias, D.; Mamoulis, N. Continuous nearest neighbor monitoring in road networks. In Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, 12–15 September 2006.
  33. Huang, Y.-K.; Lin, L.-F. Efficient processing of continuous min–max distance bounded query with updates in road networks. Inf. Sci. 2014, 278, 187–205. [Google Scholar] [CrossRef]
  34. Wang, H.; Zimmermann, R. Processing of continuous location-based range queries on moving objects in road networks. IEEE Trans. Knowl. Data Eng. 2011, 23, 1065–1078. [Google Scholar] [CrossRef]
  35. AL-Khalidi, H.; Taniar, D.; Betts, J.; Alamri, S. Dynamic safe regions for moving range queries in mobile navigation. Int. J. Ad Hoc Ubiquitous Comput. 2014, 16, 250–259. [Google Scholar] [CrossRef]
  36. Cheema, M.A.; Brankovic, L.; Lin, X.; Zhang, W.; Wang, W. Continuous monitoring of distance-based range queries. IEEE Trans. Knowl. Data Eng. 2011, 23, 1182–1199. [Google Scholar] [CrossRef]
  37. Papadias, D.; Zhang, J.; Mamoulis, N.; Tao, Y. Query Processing in Spatial Network Databases. In Proceedings of the 29th International Conference on Very Large Data Bases, Berlin, Germany, 9–12 September 2003.
  38. Egenhofer, M.J.; Franzosa, R.D. Point-set topological spatial relations. Int. J. Geogr. Inf. Syst. 1991, 5, 161–174. [Google Scholar] [CrossRef]
  39. Egenhofer, M.J.; Herring, J. A Mathematical Framework for the Definition of Topological Relationships. In Proceedings of the Fourth International Symposium on Spatial Data Handling, Zurich, Switzerland, 23–27 July 1990.
  40. Liu, F.; Do, T.; Hua, K. Dynamic range query in spatial network environments. In Database and Expert Systems Applications; Springer: Berlin, Germany, 2006; pp. 254–265. [Google Scholar]
  41. Ding, Z.; Guting, R.H. Managing moving objects on dynamic transportation networks. In Proceedings of the 16th International Conference on Scientific and Statistical Database Management, Santorini Island, Greece, 21–23 June 2004.
  42. GT-Mobisim. 2015. Available online: https://github.com/Sdcxv/gt-mobisim (accessed on 14 December 2016).
Ijgi 05 00246 g001 550
Figure 1. An example of a network.
Figure 1. An example of a network.
Ijgi 05 00246 g001
Ijgi 05 00246 g002 550
Figure 2. Line graph structure.
Figure 2. Line graph structure.
Ijgi 05 00246 g002
Ijgi 05 00246 g003 550
Figure 3. An example of bridgeable edges. (a) A query object in network; (b) The schematic of bridgeable edges
Figure 3. An example of bridgeable edges. (a) A query object in network; (b) The schematic of bridgeable edges
Ijgi 05 00246 g003
Ijgi 05 00246 g004 550
Figure 4. Distance edge.
Figure 4. Distance edge.
Ijgi 05 00246 g004
Ijgi 05 00246 g005 550
Figure 5. Graph-based expansion tree.
Figure 5. Graph-based expansion tree.
Ijgi 05 00246 g005
Ijgi 05 00246 g006 550
Figure 6. System architecture.
Figure 6. System architecture.
Ijgi 05 00246 g006
Ijgi 05 00246 g007 550
Figure 7. GT-MobiSIM. (a) The simultion with 5000 moving objects and 500 query objects; (b) The simultion with 10,000 moving objects and 1000 query objects.
Figure 7. GT-MobiSIM. (a) The simultion with 5000 moving objects and 500 query objects; (b) The simultion with 10,000 moving objects and 1000 query objects.
Ijgi 05 00246 g007
Ijgi 05 00246 g008 550
Figure 8. The CPU time needed for the calculation of the query candidate.
Figure 8. The CPU time needed for the calculation of the query candidate.
Ijgi 05 00246 g008
Ijgi 05 00246 g009 550
Figure 9. The average number of moving objects obtained in query results and the query candidate.
Figure 9. The average number of moving objects obtained in query results and the query candidate.
Ijgi 05 00246 g009
Ijgi 05 00246 g010 550
Figure 10. Comparison of Stojanovic continuous range (StojanovicCR) and line graph-based continuous range (LGCR). (a) The result of the experiment with 5000 moving objects and 500 query objects; (b) The result of the experiment with 10,000 moving objects and 1000 query objects.
Figure 10. Comparison of Stojanovic continuous range (StojanovicCR) and line graph-based continuous range (LGCR). (a) The result of the experiment with 5000 moving objects and 500 query objects; (b) The result of the experiment with 10,000 moving objects and 1000 query objects.
Ijgi 05 00246 g010

Share and Cite

MDPI and ACS Style

Zhang, H.; Lu, F.; Chen, J. A Line Graph-Based Continuous Range Query Method for Moving Objects in Networks. ISPRS Int. J. Geo-Inf. 2016, 5, 246. https://doi.org/10.3390/ijgi5120246

AMA Style

Zhang H, Lu F, Chen J. A Line Graph-Based Continuous Range Query Method for Moving Objects in Networks. ISPRS International Journal of Geo-Information. 2016; 5(12):246. https://doi.org/10.3390/ijgi5120246

Chicago/Turabian Style

Zhang, Hengcai, Feng Lu, and Jie Chen. 2016. "A Line Graph-Based Continuous Range Query Method for Moving Objects in Networks" ISPRS International Journal of Geo-Information 5, no. 12: 246. https://doi.org/10.3390/ijgi5120246

APA Style

Zhang, H., Lu, F., & Chen, J. (2016). A Line Graph-Based Continuous Range Query Method for Moving Objects in Networks. ISPRS International Journal of Geo-Information, 5(12), 246. https://doi.org/10.3390/ijgi5120246

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop