GISdevelopment.net --> Application --> Miscellaneous
M. Ravi Teja
pursuing BTech degree in Computer Science from,
International Institute of Information Technology,
Hyderabad
Mail id: ravi_teja@students.iiit.ac.in
P.V. Bhaskara Varma
pursuing BTech degree in Computer Science from,
International Institute of Information Technology,
Hyderabad
Prosenjit Gupta
professor
International Institute of Information Technology,
Hyderabad
Abstract
Spatial networks form the basis of many industrial applications like transportation planning, air traffic control, urban management; water, electric and gas utilities; telephone networks and sewer maintenance. These networks are derived from physical maps by removing open spaces and elements that are irrelevant to the context of the network.
Variants of proximity problems are very well studied in computational Geometry. However, most of the existing work in computational Geometry on proximity considers the Euclidean distance between two objects. This distance is determined by the relative position of two points in space. But in reality objects traverse along pre-determined paths (roads, railway lines) in transportation networks. The measure involved here is the network distance which is the length of the path between two points along the underlying network. Our aim is to develop efficient algorithms for conventional spatial proximity queries (e.g. closest pairs, nearest neighbors and range aggregate queries) and special queries (e.g. largest empty circle and smallest enclosing circle). The limited work that has been done in spatial networks has concentrated in experimental evaluation of the performance. In this work, we have given theoretical bounds of time and space complexity for solving the queries.
The road network is modeled as a graph G(V,E) which consists of a finite set of vertices V (or nodes) and a set of edges E (or links). An intersection on a road map is represented as a vertex and a road segment between two intersections as an edge in the graph. Each edge has its weight which represents the network distance between two neighboring intersections. The special sites like restaurants and gas stations which provide services in real networks are represented as points on the network N. They lie on an edge or on the nodes of the graph G. We have also developed a prototype system, using Google Maps in the backend, wherein we have implemented the proposed algorithms. Our design is modular and amenable to extension to cover other queries as well.
1. Introduction
Query processing techniques superficially consist of two prime components. One, the part of the query that is pre computed and in common with the other queries and the other which is specific to each query. Some believe in generalizing queries to the extent that all the necessary information is available prior to the query. Though this improves the response time for each query it largely limits the essential dynamic nature of the networks. On the other hand minimal preprocessing defeats the purpose of real time systems by making the response times of queries lengthy. We tried to find a fine balance between these two features to have the best of both concepts.
The rest of the paper is organized as follows: Section 2 describes the modeling of the network. Section 3 looks at the preprocessing necessary for the efficient solving of queries. Section 4 presents some conventional queries and their algorithms. Section 5 overviews the system in which the queries are implemented. Section 6 concludes the paper by discussing the limitations of the system and the road ahead.
2. Modeling the Network
The road network N=N(V,E) is modeled as a graph G(V,E) which consists of a finite set of vertices V (or nodes) and a set of edges E (or links). An intersection on a road map is represented as a vertex and a road segment between two intersections as an edge in the graph. Each edge has its weight. We suppose the weight represents the network distance between two neighboring intersections. The special sites like restaurants and gas stations which provide services in real networks are denoted as members of set S. These too are represented as vertices in the graph. In some cases S = R U B where R, B are sets of special sites each representing sites of a particular type.
2.1 Preliminaries
CS (u) = the closest site to vertex 'u'.
D (u, s) = length of the shortest path from u to s.
W (u, v) = weight of the edge (u, v).
FS (u) = the farthest site to vertex 'u'
3. Preprocessing the Network
This section provides the definition of the Edge Network Voronoi Diagram and the Node Network Voronoi Diagram and the methods to compute them
3.1 Definitions
Edge Network Voronoi Diagram (ENVD):
It assigns each edge in a network to one site (which is closest to these points), and the points on the other part of the edge are assigned to another site (which is closer to them). For the construction of the ENVD we have to first determine the node network voronoi diagram for the sites.
Node Network Voronoi Diagram (NNVD):
It assigns each node in a network to a site by the rule that the network distance from the node to the generator is smaller than to any other site in the network.
3.2 Determining the NNVD and the ENVD
To determine the NNVD of a network we use a modification of the Dijkstra's shortest path algorithm [1] to find the nearest site to each vertex. We consider a new vertex set W, W={S U V} as the vertex set of the network. Now add an imaginary point 'p' to the new vertex set W. We also add edges of distance 0 from P to the sites belonging to S. Now we run the Dijkstra's algorithm [1] at P. Initially all the sites are relaxed [1] one after the other. By the end of the run, the shortest paths to the other vertices in W are known. But each of these paths from P must pass through a site, special points of interest. Accordingly the site in the shortest path to non-site vertex v from P is the closest site to v.
Figure 3.1: Sample Network after running the Dijkstra’s Algorithm
4.Queries
In this section we look at some of the conventional queries and the algorithms we designed for solving them.
4.1 Closest Pair [2]
Definition
The Closest Pair query retrieves the two sites in S (say s1, s2) which are closest to each other than any other pair according to the distance measured along the network. i.e. D (s1, s2) <= D (s (i), s (j)) for all sites s(i), s(j) that belong to set S such that i != j.
Solution
While constructing the ENVD we store edge lists for each site. One of the lists stores the internal edges and the other list stores the boundary edges. The list of boundary edges is sorted such that the nearest boundary edge comes first. We look at the first boundary edge for each site. The boundary edge (split edge) has network distances from both its closest sites. We compute the total network distance between these two sites. We find the minimum of these distances for all sites. This gives us the closest pair of sites in the network.
4.2 Red-Blue Closest Pair [3]
Definition
Given two different entity sets R and B the Red-Blue Closest pair [3] query finds the closest pair (r, b), among all the object pairs such that r belongs to R and s belongs to B. Distance being measured along the network. i.e. D (r, b) <= D (r(i), b(j)) such that, 'r' belongs to set R and 'b' belongs to set B for all sites r(i), b(j) such that r(i) belongs to set R and b(j) belongs to set B.
Solution
This query is an extension of the closest pair query. The list containing the boundary edges of each site is further divided into two lists. One list L1, for edges belonging to sites of same color and another list L2 for those edges which belong to sites of different colors. These lists are sorted such that the nearest boundary edge is first. To find the red-blue closest pair we need to look at the first edge of list L2 for each site. For each site we find the closest site of the opposite color. Now we find the minimum among all these distances. This gives us the Red-Blue Closest Pair [3].
4.3 Nearest Neighbor [2]
The Nearest Neighbor [2] query gives the closest site (say ‘s1’) to a given point (say 'p') on the network. Distance being measured along the network. i.e. D (p, s1) <= D (p, s) for all sites ‘s’ that belong to S.
Solution
Given a point on the network we have two different cases.
Case (i): Point lies on a vertex of the network.
In this case we see the closest site to the concerned vertex. This has already been obtained while determining the NNVD. So the nearest neighbor to the point is the above mentioned site.
Case (ii): Point lies on an edge of the network.
If the edge is an internal edge we obtain the site to which it belongs. This has been obtained while finding the ENVD. This site is the nearest neighbor to the given point. If the edge is a boundary edge we look at the split point computed while determining the ENVD. Based on the position of the query point with respect to the split point we can determine the nearest neighbor to the query point. It has to be one of the two sites to which the edge belongs.
4.4 Largest Empty Circle [5]
Definition
The Largest Empty Circle [5] query retrieves the point on the network from which the Network Circle with the maximum radius can be drawn such that no sites in S are in it. In the Network Circle the radius is measured along the network unlike a circle in the Euclidean plane.
Solution
While determining the NNVD using the modified Dijkstra's algorithm we store the last vertex that is relaxed. This vertex (say 'v1') is the farthest from the source. This means that this vertex has the largest value for D (v, CS (v))
i.e. D (v1, CS (v1)) >= D (v, CS (v)) for all vertices ‘v’ which belong to the set V. We look at all the split edges. For each of these edges (say (u, v)) we find out the point on the edge from where the empty circle with the largest possible network radius can be drawn. This point is at a distance (W (u, v) – (D (u, CS (u)) – D (v, CS (v))) / 2 from the vertex ‘u’. From all the circles we find out the one with the largest network radius (say 'r'). We already know its center (say ‘c’).
If r > D (v1, CS (v1)), then the center of the Largest Empty Circle [5] is ‘c’ and its network radius is 'r'. If the condition is not satisfied then the center of the Largest Empty Circle is 'v1' and its network radius is D (v1, CS (v1).
4.5 All Nearest Neighbors
Definition
The All Nearest Neighbors query retrieves the sites closest to each site in the network. Distance being the network distance.
Solution:
We store the list of internal edges and the list of sorted boundary edges (split edges) separately for each site. The first entry in the list of boundary edges will be the edge to the nearest site. We repeat the process for all the sites. This gives us the nearest site to each particular site in the network.
4.6 Shortest path from a point to its nearest site [4]
Definition
Given a point 'p' on the network this query finds out the shortest path (order set of vertices) to the nearest site.
Solution
We find the nearest site to the point. This can be done by looking at the vertices of the edge on which this point lies. The closest site to each of the vertices and their distance has been computed during the pre-processing step.
Step 1: If the edge is an internal edge then we picks the vertex with the least distance and en queue it. If the edge is a split edge then we check the position of the split point and determine the vertex we have to select and en queue it.
Step 2: Once we are at a vertex we consider the internal edges incident on it and pick the one whose other vertex is closest to the site. The new vertex is en queued.
Step 3: We repeat Step 2 till we reach the site.
Step 4: If we empty the queue we will have an ordered set of vertices which denote the shortest path from the point to its nearest site.
If the point lies on a vertex then we start the algorithm from step 2.
5. Transportation Network Information System (TNIS)
The TNIS acts as a testing ground for the proposed query algorithms. The system includes the implemented query algorithms and a GUI. The interface is built using java GUI libraries. The interface is designed to be interactive, it enables the user to both modify and query data. Query results are shown on the interface using colors to represent the nodes and edges which are the query output. We have tried to maintain the integrity of the algorithms but in cases it was not possible to avoid minor adjustments.
5.1 Constructing the Network
The user can load the background image of the network he wants to work on. We have provided functions to add and remove edges, nodes and special sites. Using these functions appropriately the user constructs the network over the underlying image. An option has also been provided to save the network once it is constructed. This enables the user to work on a specific network multiple times without constructing it each time. Loading the background image of the network is optional and has been provided to simplify construction of the network. A user can also construct an imaginary network (not belonging to the real world) and work on it.
5.2 Querying the System
Once the network has been constructed we have to preprocess the network. We have enabled an option for the user to look at the ENVD.
Figure 5.1: TNIS displaying the Edge Network Voronoi Diagram
6. Conclusion
We have tried to maintain the integrity of the query algorithms while translating them from theory to practice. But at times we have been constrained by the limitations of the GUI. A simple example is that the interface needs to draw the network after each query and for this we need to look at all the edges. So even if the algorithm has a good time complexity the implementation forces a minimum bound on it. Another area of concern is the inability of the system to query points not lying on the network. We need to devise a mechanism to accommodate such queries.
In this paper we have provided solutions to some of the general queries. In addition this we need to look at some of the range aggregate queries. These queries are an extension of the conventional queries. We are given a point 'p' and a range 'd'. The intention is to solve the conventional queries in this new constrained network. E.g. Range Aggregate Closest Pair, Range Aggregate Nearest Neighbor, etc.
The TNIS is modular and this eases the possibility of making improvements to the existing queries. Additional queries can also be added with minor modifications . But the primary goal from the practical perspective is to explore methodologies that will help in loosening the implementation limitations of the system.
References
A Tool for Supporting Efficient Proximity Queries on Road Networks
M. Ravi Teja
pursuing BTech degree in Computer Science from,
International Institute of Information Technology,
Hyderabad
Mail id: ravi_teja@students.iiit.ac.in
P.V. Bhaskara Varma
pursuing BTech degree in Computer Science from,
International Institute of Information Technology,
Hyderabad
Prosenjit Gupta
professor
International Institute of Information Technology,
Hyderabad
Abstract
Spatial networks form the basis of many industrial applications like transportation planning, air traffic control, urban management; water, electric and gas utilities; telephone networks and sewer maintenance. These networks are derived from physical maps by removing open spaces and elements that are irrelevant to the context of the network.
Variants of proximity problems are very well studied in computational Geometry. However, most of the existing work in computational Geometry on proximity considers the Euclidean distance between two objects. This distance is determined by the relative position of two points in space. But in reality objects traverse along pre-determined paths (roads, railway lines) in transportation networks. The measure involved here is the network distance which is the length of the path between two points along the underlying network. Our aim is to develop efficient algorithms for conventional spatial proximity queries (e.g. closest pairs, nearest neighbors and range aggregate queries) and special queries (e.g. largest empty circle and smallest enclosing circle). The limited work that has been done in spatial networks has concentrated in experimental evaluation of the performance. In this work, we have given theoretical bounds of time and space complexity for solving the queries.
The road network is modeled as a graph G(V,E) which consists of a finite set of vertices V (or nodes) and a set of edges E (or links). An intersection on a road map is represented as a vertex and a road segment between two intersections as an edge in the graph. Each edge has its weight which represents the network distance between two neighboring intersections. The special sites like restaurants and gas stations which provide services in real networks are represented as points on the network N. They lie on an edge or on the nodes of the graph G. We have also developed a prototype system, using Google Maps in the backend, wherein we have implemented the proposed algorithms. Our design is modular and amenable to extension to cover other queries as well.
1. Introduction
Query processing techniques superficially consist of two prime components. One, the part of the query that is pre computed and in common with the other queries and the other which is specific to each query. Some believe in generalizing queries to the extent that all the necessary information is available prior to the query. Though this improves the response time for each query it largely limits the essential dynamic nature of the networks. On the other hand minimal preprocessing defeats the purpose of real time systems by making the response times of queries lengthy. We tried to find a fine balance between these two features to have the best of both concepts.
The rest of the paper is organized as follows: Section 2 describes the modeling of the network. Section 3 looks at the preprocessing necessary for the efficient solving of queries. Section 4 presents some conventional queries and their algorithms. Section 5 overviews the system in which the queries are implemented. Section 6 concludes the paper by discussing the limitations of the system and the road ahead.
2. Modeling the Network
The road network N=N(V,E) is modeled as a graph G(V,E) which consists of a finite set of vertices V (or nodes) and a set of edges E (or links). An intersection on a road map is represented as a vertex and a road segment between two intersections as an edge in the graph. Each edge has its weight. We suppose the weight represents the network distance between two neighboring intersections. The special sites like restaurants and gas stations which provide services in real networks are denoted as members of set S. These too are represented as vertices in the graph. In some cases S = R U B where R, B are sets of special sites each representing sites of a particular type.
2.1 Preliminaries
CS (u) = the closest site to vertex 'u'.
D (u, s) = length of the shortest path from u to s.
W (u, v) = weight of the edge (u, v).
FS (u) = the farthest site to vertex 'u'
3. Preprocessing the Network
This section provides the definition of the Edge Network Voronoi Diagram and the Node Network Voronoi Diagram and the methods to compute them
3.1 Definitions
Edge Network Voronoi Diagram (ENVD):
It assigns each edge in a network to one site (which is closest to these points), and the points on the other part of the edge are assigned to another site (which is closer to them). For the construction of the ENVD we have to first determine the node network voronoi diagram for the sites.
Node Network Voronoi Diagram (NNVD):
It assigns each node in a network to a site by the rule that the network distance from the node to the generator is smaller than to any other site in the network.
3.2 Determining the NNVD and the ENVD
To determine the NNVD of a network we use a modification of the Dijkstra's shortest path algorithm [1] to find the nearest site to each vertex. We consider a new vertex set W, W={S U V} as the vertex set of the network. Now add an imaginary point 'p' to the new vertex set W. We also add edges of distance 0 from P to the sites belonging to S. Now we run the Dijkstra's algorithm [1] at P. Initially all the sites are relaxed [1] one after the other. By the end of the run, the shortest paths to the other vertices in W are known. But each of these paths from P must pass through a site, special points of interest. Accordingly the site in the shortest path to non-site vertex v from P is the closest site to v.
Figure 3.1: Sample Network after running the Dijkstra’s Algorithm
4.Queries
In this section we look at some of the conventional queries and the algorithms we designed for solving them.
4.1 Closest Pair [2]
Definition
The Closest Pair query retrieves the two sites in S (say s1, s2) which are closest to each other than any other pair according to the distance measured along the network. i.e. D (s1, s2) <= D (s (i), s (j)) for all sites s(i), s(j) that belong to set S such that i != j.
Solution
While constructing the ENVD we store edge lists for each site. One of the lists stores the internal edges and the other list stores the boundary edges. The list of boundary edges is sorted such that the nearest boundary edge comes first. We look at the first boundary edge for each site. The boundary edge (split edge) has network distances from both its closest sites. We compute the total network distance between these two sites. We find the minimum of these distances for all sites. This gives us the closest pair of sites in the network.
4.2 Red-Blue Closest Pair [3]
Definition
Given two different entity sets R and B the Red-Blue Closest pair [3] query finds the closest pair (r, b), among all the object pairs such that r belongs to R and s belongs to B. Distance being measured along the network. i.e. D (r, b) <= D (r(i), b(j)) such that, 'r' belongs to set R and 'b' belongs to set B for all sites r(i), b(j) such that r(i) belongs to set R and b(j) belongs to set B.
Solution
This query is an extension of the closest pair query. The list containing the boundary edges of each site is further divided into two lists. One list L1, for edges belonging to sites of same color and another list L2 for those edges which belong to sites of different colors. These lists are sorted such that the nearest boundary edge is first. To find the red-blue closest pair we need to look at the first edge of list L2 for each site. For each site we find the closest site of the opposite color. Now we find the minimum among all these distances. This gives us the Red-Blue Closest Pair [3].
4.3 Nearest Neighbor [2]
The Nearest Neighbor [2] query gives the closest site (say ‘s1’) to a given point (say 'p') on the network. Distance being measured along the network. i.e. D (p, s1) <= D (p, s) for all sites ‘s’ that belong to S.
Solution
Given a point on the network we have two different cases.
Case (i): Point lies on a vertex of the network.
In this case we see the closest site to the concerned vertex. This has already been obtained while determining the NNVD. So the nearest neighbor to the point is the above mentioned site.
Case (ii): Point lies on an edge of the network.
If the edge is an internal edge we obtain the site to which it belongs. This has been obtained while finding the ENVD. This site is the nearest neighbor to the given point. If the edge is a boundary edge we look at the split point computed while determining the ENVD. Based on the position of the query point with respect to the split point we can determine the nearest neighbor to the query point. It has to be one of the two sites to which the edge belongs.
4.4 Largest Empty Circle [5]
Definition
The Largest Empty Circle [5] query retrieves the point on the network from which the Network Circle with the maximum radius can be drawn such that no sites in S are in it. In the Network Circle the radius is measured along the network unlike a circle in the Euclidean plane.
Solution
While determining the NNVD using the modified Dijkstra's algorithm we store the last vertex that is relaxed. This vertex (say 'v1') is the farthest from the source. This means that this vertex has the largest value for D (v, CS (v))
i.e. D (v1, CS (v1)) >= D (v, CS (v)) for all vertices ‘v’ which belong to the set V. We look at all the split edges. For each of these edges (say (u, v)) we find out the point on the edge from where the empty circle with the largest possible network radius can be drawn. This point is at a distance (W (u, v) – (D (u, CS (u)) – D (v, CS (v))) / 2 from the vertex ‘u’. From all the circles we find out the one with the largest network radius (say 'r'). We already know its center (say ‘c’).
If r > D (v1, CS (v1)), then the center of the Largest Empty Circle [5] is ‘c’ and its network radius is 'r'. If the condition is not satisfied then the center of the Largest Empty Circle is 'v1' and its network radius is D (v1, CS (v1).
4.5 All Nearest Neighbors
Definition
The All Nearest Neighbors query retrieves the sites closest to each site in the network. Distance being the network distance.
Solution:
We store the list of internal edges and the list of sorted boundary edges (split edges) separately for each site. The first entry in the list of boundary edges will be the edge to the nearest site. We repeat the process for all the sites. This gives us the nearest site to each particular site in the network.
4.6 Shortest path from a point to its nearest site [4]
Definition
Given a point 'p' on the network this query finds out the shortest path (order set of vertices) to the nearest site.
Solution
We find the nearest site to the point. This can be done by looking at the vertices of the edge on which this point lies. The closest site to each of the vertices and their distance has been computed during the pre-processing step.
Step 1: If the edge is an internal edge then we picks the vertex with the least distance and en queue it. If the edge is a split edge then we check the position of the split point and determine the vertex we have to select and en queue it.
Step 2: Once we are at a vertex we consider the internal edges incident on it and pick the one whose other vertex is closest to the site. The new vertex is en queued.
Step 3: We repeat Step 2 till we reach the site.
Step 4: If we empty the queue we will have an ordered set of vertices which denote the shortest path from the point to its nearest site.
If the point lies on a vertex then we start the algorithm from step 2.
5. Transportation Network Information System (TNIS)
The TNIS acts as a testing ground for the proposed query algorithms. The system includes the implemented query algorithms and a GUI. The interface is built using java GUI libraries. The interface is designed to be interactive, it enables the user to both modify and query data. Query results are shown on the interface using colors to represent the nodes and edges which are the query output. We have tried to maintain the integrity of the algorithms but in cases it was not possible to avoid minor adjustments.
5.1 Constructing the Network
The user can load the background image of the network he wants to work on. We have provided functions to add and remove edges, nodes and special sites. Using these functions appropriately the user constructs the network over the underlying image. An option has also been provided to save the network once it is constructed. This enables the user to work on a specific network multiple times without constructing it each time. Loading the background image of the network is optional and has been provided to simplify construction of the network. A user can also construct an imaginary network (not belonging to the real world) and work on it.
5.2 Querying the System
Once the network has been constructed we have to preprocess the network. We have enabled an option for the user to look at the ENVD.
Figure 5.1: TNIS displaying the Edge Network Voronoi Diagram
6. Conclusion
We have tried to maintain the integrity of the query algorithms while translating them from theory to practice. But at times we have been constrained by the limitations of the GUI. A simple example is that the interface needs to draw the network after each query and for this we need to look at all the edges. So even if the algorithm has a good time complexity the implementation forces a minimum bound on it. Another area of concern is the inability of the system to query points not lying on the network. We need to devise a mechanism to accommodate such queries.
In this paper we have provided solutions to some of the general queries. In addition this we need to look at some of the range aggregate queries. These queries are an extension of the conventional queries. We are given a point 'p' and a range 'd'. The intention is to solve the conventional queries in this new constrained network. E.g. Range Aggregate Closest Pair, Range Aggregate Nearest Neighbor, etc.
The TNIS is modular and this eases the possibility of making improvements to the existing queries. Additional queries can also be added with minor modifications . But the primary goal from the practical perspective is to explore methodologies that will help in loosening the implementation limitations of the system.
References
- T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, “Introduction to Algorithms, MIT Press, 2001”.
- Dimitris Papadias, Jun Zhang, Nikos Mamoulis and Yufei Tao, “Query Processing in Spatial Network Databases”.
- A.Corral, Y. Manolopoulos, Y. Theodoridis, M.Vassilakopoulos, “Closest Pair Queries in Spatial Databases”.
- Y.-W. Huang, N. Jing and E.A. Rundensteiner, “Path Queries for Transportation Networks: Dynamic Reordering and Sliding Window Paging Techniques”.
- Preparata F.1'. and Shamos M.I., "Computational Geometry -An Introduction," Springer-Verlag. 1988.