next up previous
Next: SHORTEST PATH ALGORITHMS Up: OORF: AN OBJECT-ORIENTED ROUTE Previous: OORF: AN OBJECT-ORIENTED ROUTE

INTRODUCTION

During the last decade, the management, representation and evaluation of spatial data in information systems gained importance. Geographic information systems (GIS) are increasingly used in public administration, sciences and business. The nucleus of the GIS is the geographic database system[2]. Contrary to business applications based on standard systems, such systems are not suitable for geographic applications. The insufficient expressive power e.g. of relational systems, leads to unnatural data models, and to a poor efficiency in query processing.
Therefore, various research groups have developed a large numbers of concepts and techniques for improving single aspect of a geographic database. Example is the design of spatial data models for managing large sets of spatial objects.

In this paper, we will present an object-oriented road network data model that will be useful for solving shortest path problems integrating several concepts and techniques. In network theory this route finding is called the shortest path problem. There are many algorithms such as Dijkstra's algorithm [4,3], usually used to solve this type of problems. These algorithms are general and are not efficient for route finding [6]. However, these algorithms can be made efficient by using common sense knowledge and knowledge about the geographic information of the road network and of the area within which the route is being searched. Object-orientation promises to help use of such knowledge due to it's powerful semantics, such as generalization, aggregation relationships and different hierarchical arrangements of the data.

We divide our discussion into road network database design and route finding in this road network database. The remainder of the paper is organized as follows: In section 2 we discuss some shortest route finding algorithms and show why these algorithms need the different types of knowledge to compute shortest route. Section 3 describes the design of the Road Network Data Model(RNDM). Section 4 explains how route is searched in an Object-oriented Road Network Database and in section 5 we evaluate our approach and in section 6 related work is presented. In last we present conclusion of our work.

next up previous
Next: SHORTEST PATH ALGORITHMS Up: OORF: AN OBJECT-ORIENTED ROUTE Previous: OORF: AN OBJECT-ORIENTED ROUTE
M.Abaidullah ANWAR
1999-11-25