Follow us on Facebook

Header Ads

ROAD: A New Spatial Object Search Framework for Road Networks

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.