A study is performed of the issues arising in the e cient processing of spatial queries in large spatial databases. The domain is restricted to line segment databases such as those found in transportation networks and polygonal maps. Three classes of queries are identi ed. Those that deal with the line segments themselves, those that involve both the line segments and the space from which they are drawn e.g., proximity queries, and those that involve attributes of the line segments. Handling the three types of queries requires that the line segments be stored implicitly using a bucketing approach on the space from which they are drawn. A number of bucketing approaches are examined and the pmr quadtree is chosen as the most suitable representation. Its storage and execution time requirements are evaluated in the context of nding the nearest line segment t o a g i v en point. This operation is shown to take time proportional to the splitting threshold similar to the bucket capacity and is independent of the density of the data. The evaluation uses the road networks in the data of the U.S. Bureau of the Census.
In REF , the PMR quadtree is used as an access method for line segment databases and an algorithm for finding the nearest line segment to a given point is presented (a query belonging to the second class above).
EFFICIENT PROCESSING OF SPATIAL QUERIES IN LINE SEGMENT DATABASES*
SSD
Geography Computer Science