A study is performed of the issues arising in the efficient 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 identified. 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., proxmity queries), and those that involve attributes of the line segments. Handling the three types of queries requires that the line segments be stored implicity 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 finding the nearest line segment to a given 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.
Efficient processing of spatial queries in line segment databases
Effiziente Verarbeitung geometrisch-räumlicher Abfragen in linien-segmentierten Datenbanken
1991
20 Seiten, 7 Bilder, 2 Tabellen, 28 Quellen
Conference paper
English
European Patent Office | 2020
|British Library Conference Proceedings | 2000
|