Project Login
Registration No:

ROAD: A New Spatial Object Search Framework for Road Networks

Platform : java

IEEE Projects Years : 2012 - 13

ROAD: A New Spatial Object Search

             Framework for Road Networks




             We present a new system framework called ROAD for spatial object search on road networks. the ROAD is Extensible to diverse object types and efficient for processing various location-dependent spatial queries (LDSQs).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 sub networks (called Rents). Each Rent 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 Rent hierarchy and several properties useful in constructing and maintaining the Rent 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. 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.
  • As solution-based approaches: Distance Index precomputes for all needs to traverse the network in a node by node fashion.
  • Ø Bulky Spots accessed for all visited nodes make this approach very I/O-inefficient. While the design and implementation of HEPV and HiTi only allow point-to-point shortest path searches.
  • Our ROAD facilitates network expansion to reach multiple destinations for objects.
  • Ø Extended spatial database approaches: Two basic search strategies were studied.
  • Ø The first strategy is based on the idea of Euclidean distance bound approaches first identify candidate objects that have Euclidean distances to the query point bounded by 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.
  • Ø The second strategy is based on network expansion that gradually expands a search range on a network until all the nodes and edges that satisfy the search criteria a revisited. .
  • Ø Network expansion approaches are still inefficient due to the slow node-by-node expansion toward all directions.






Propose System:




  • Ø We propose Association Directory an efficient object lookup mechanism in ROAD. It is also based on a one-dimensional index, e.g., Be-tree.
  • Ø The Algorithm MultiSourcekNNSearch, MultiSource Range Search.
  • Ø The algorithm MultiSourcekNNSearch: maintains a priority queue P to sort pending entries in a nondecreasing distance order from respective query nodes.
  • Ø MultiSourceRangeSearch: multisource rangequery traverses a network when all unexamined entries that include nodes or objects in the queue are beyond a specified distance range.
  • Ø ROAD adopts filtering-and-refreshing approach. In the “filtering” phase, shortcuts possibly affected by an edge change are identified.
  • Ø Only the identified shortcuts are updated in the “refreshing “Phase. The storage cost for keeping all the shortcuts in a Rent hierarchy.
  • Ø We estimate the processing time for LDSQs. Here, we only consider single-source LDSQs. In ROAD, a query typically involves two phases namely.
  • One an expansion phase that expands a search range from a local smallest Rent whereas query is issued to larger Rents that cover target objects
  • Ø Second a drill-down phase that narrows down the search from larger nets to the smallest Rents that contain required objects.
  • Ø The time for shortcut construction. We assume that Dijkstra’s algorithm is used. ROAD adopts a concurrent approach that expands a search Space from all query nodes through a best-first strategy.
  • Ø We introduce Rents, shortcuts, and object abstracts, and discuss the formation of Rent hierarchy we present the core of ROAD implementation, Namely, Route Overlay and Association Directory.






  • Authentication
  • Ø Source
  • Ø Road & Route
  • Ø Destination




Module Description:




  • In this module we are going to give Username and Password for security purpose.
  • To check the username and password to avoid the unwanted users.
  • Ø If you did not give a correct password or username we cannot able to open the link page




  • Ø LDSQs mean locations as location-dependent spatial queries.
  • In processing LDSQs on a road network, two basic operations. Network traversal and object lookup.
  • Find hotels within one mile from the conference venue;
  • Ø Locate the nearest bus station to the conference venue.
  • Ø Find a restaurant closest to the hotels of the conference participants.
  • Ø The query processing algorithms for single-source LDSQs and multisourceLDSQs respectively.
  • Ø A suite of efficient search algorithms for single-source LDSQs and multisource LDSQs.










Road  & Route:


  • Ø We introduce Rents, shortcuts, and object abstracts, and discuss the formation of Rent hierarchy.
  • A network is first formulated as a set of interconnected regional subnets called Rents, each representing search subspace.
  • Ø ROAD cleanly separates the road network and objects, exploits the idea of search space pruning, and supports searches with different distance metrics.
  • Ø We develop efficient update techniques for ROAD maintenance to handle object and network updates.
  • Ø In Route Overlay, nodes are indexed by a 1D index with unique node IDs as search keys. In our implementation, we use Bþ-tree.
  • Each leaf entry of the Bþ-tree points to one node, together with a shortcut tree, If a given node n is a border node of an Rent,






  • Ø The first experiment set evaluates the index construction time and index sizes for all the approaches with various numbers of objects and networks.
  • Ø The index construction time (in hours) and index sizes (in megabyte) for various numbers of objects on NA.
  • Ø Since the construction time is not affected by the object distribution, ROAD takes around 1 hour construction time and about 20 MB storage space.
  • Ø In contrast due to the bulky SPQTs DistBrws takes an extremely long construction time (over 100,000 hours) and a huge storage (over 10 GB) though it is almost invariant to the number of objects.
























System Components:








  • System:                          Pentium IV 2.4 GHz.
  • Hard Disk:                      500 GB.
  • Monitor:                            15” VGA Colour.
  • Mouse:                                ps/2.
  • Ram:                                    1 gb.




  • Operating System :        Windows xp.
  • Software                :          java , jdk 1.6, Net beans 7.1.
  • Front-End               :          java
  • Backend                :         Sql 2000










CALL: 08985129129 ,  E-Mail Id: