ROAD: A New Spatial
Object Search Framework for Road Networks
ABSTRACT:
In this paper, we present a new system
framework called ROAD for spatial object search on road networks. ROAD is extensible
to diverse object types and efficient for processing various location-dependent
spatial queries (LDSQs), as it maintains objects separately from a given
network and adopts an effective search space pruning technique. Based on our
analysis on the two essential operations for LDSQ processing, namely, network traversal
and object lookup, ROAD organizes a large road network as a hierarchy of
interconnected regional subnetworks (called Rnets). Each Rnet is augmented with
1) shortcuts and 2) object abstracts to accelerate network traversals and
provide quick object lookups, respectively. To manage those shortcuts and
object abstracts, two cooperating indices, namely, Route Overlay and
Association Directory are devised. In detail, we present 1) the Rnet hierarchy
and several properties useful in constructing and maintaining the Rnet
hierarchy, 2) the design and implementation of the ROAD framework, and 3) a
suite of efficient search algorithms for single-source LDSQs and multisource
LDSQs. We conduct a theoretical performance analysis and carry out a
comprehensive empirical study to evaluate ROAD. The analysis and experiment
results show the superiority of ROAD over the state-of-the-art approaches.
EXISTING
SYSTEM:
Existing works on processing LDSQs on road networks
are categorized as solution-based approaches and extended spatial database
approaches, extended spatial database approaches incorporate road networks to
existing spatial databases. Two basic search strategies were studied. The first
strategy is based on the idea of euclidean distance bound. New roads are
constructed or existing roads are closed, the corresponding network topology is
changed. We model these changes as addition or deletion of nodes and edges.
Here, we treat changes of nodes as special cases of changes of edges, and only
consider addition and deletion of edges below. Deleting an edge breaks the link
between two nodes n and n0. Consider deleting in R2 in. Its deletion can be
managed as handling the change of its edge distance to infinity and updating
affected shortcuts. It is possible that one end node n of a deleted edge is a
border node.
PROPOSED
SYSTEM:
We propose two novel index structures, namely, Route
Overlay and Association Directory (and ROAD is named after these two key
components). The Distance browsing has been recently proposed based on the
concept of path coherence that for any node n, all other nodes with their
shortest paths from n via one of n’s immediate neighboring nodes are spatially
close. Based on this idea, shortest path quad-tree (SPQT). A new system
framework for LDSQ processing, in this paper. The design of ROAD achieves a
clear separation between objects and network for better system extensibility.
It also exploits search space pruning, a powerful technique for efficient
object search. Upon the framework, efficient search algorithms for single
source and multisource LDSQs are devised. Via a comprehensive performance
evaluation on real road networks, ROAD is shown to significantly outperform the
state-of-the art techniques.
MODULE
·
Spatial
Road Network
·
Shortest
Path:
·
Query
Performance
·
Edge
Distance:
MODULE DESCRIPTION:
Spatial
Road Network
We refer to location-dependent information (e.g.,
point of interest, traffic, and local events) as spatial objects (or objects
for short). We define queries that search for spatial objects with respect to
user-specified locations as location-dependent spatial queries (LDSQs). A novel
system framework to support spatial object searches on road networks. ROAD
cleanly separates the road network and objects, exploits the idea of search space
pruning, and supports searches with different distance metrics. The goal of
ROAD is to provide a general-purpose search platform for any added-on spatial
objects and various LDSQs, we adopt a network partitioning that can generate
equal-sized Rnets and the smallest number of border nodes, which, in turn,
minimizes the number of shortcuts formed. This network partitioning problem is,
however, known NP-complete.
Shortest
Path:
A network is first formulated as a set of
interconnected regional subnets called Rnets, each representing a search
subspace. On top of the Rnets, two kinds of additional information are
derived: selective (shortest) paths
across an Rnet that enable any traversal to bypass the Rnet if it has no object
of interest, and the existence and or
contents of objects that are inside the Rnets to provide quick traversal
guidelines. First identify candidate objects that have euclidean distances to
the query point bounded by a distance threshold. Then, they determine network
distances between individual candidate object and the query point based on
shortest path algorithms or materialized
distances and finally, they discard false candidates whose network distances
actually are larger than the threshold.
Query
Performance
We detail the design, implementation, and evaluation
of ROAD, and provide a holistic
solution to several important research issues that include organization of
Rnets, search algorithms for various LDSQs, and framework updates. We also
perform an analysis and simulation to evaluate the ROAD performance. we provide
a theoretical analysis on the performance of ROAD, in terms of 1) storage cost,
2) construction time, and 3) query processing cost. the cost for maintaining an
Association Directory is much smaller than that for Route Overlay, we focus our
analysis only on the latter.
Edge
Distance:
Road condition and road network structure change
over time. Rather than immediately rebuilding a Route Overlay upon changes,
which is expensive, we develop several techniques to incrementally update Route
Overlay for edge distance changes, and network structure changes.
HARDWARE
REQUIREMENTS:-
•
System : Pentium IV
2.4 GHz.
•
Hard Disk : 40 GB.
•
Floppy Drive : 1.44 Mb.
•
Monitor : 15 VGA
Colour.
•
Mouse : Logitech.
•
RAM : 256 Mb.
SOFTWARE
REQUIREMENTS:
•
Operating system : - Windows XP Professional.
•
Front End :
- Visual Studio.Net 2008
•
Coding Language : - Visual C# .Net.
REFERENCE:
Ken C.K. Lee, Wang-Chien Lee, Baihua
Zheng, and Yuan Tian, “ROAD: A New Spatial Object Search Framework for Road
Networks”, IEEE TRANSACTIONS ON
KNOWLEDGE AND DATA ENGINEERING, VOL. 24, NO. 3, MARCH 2012.