Spatial data traversal in road map databases
Published 1 January 1994
Jun Zhao, Ahmed S. Zaki
Citations9
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Using a probabilistic analysis, this paper shows that the graph indexing technique significantly improves the efficiency of constrained spatial queries.
Abstract
Spatial data are found in geographic information systems such as digital road map databases where city and road attributes are associated with nodes and links in a directed graph. Queries on spatial data are expensive because of the recursive property of graph traversal. We propose a graph indexing technique to expedite spatial queries where the graph topology remains relatively stationary. Using a probabilistic analysis, this paper shows that the graph indexing technique significantly improves the efficiency of constrained spatial queries.
Keywords
Computer ScienceSocial Sciences
ACM SIGMOD RecordAn amateur's introduction to recursive query processing strategies
697 Citations1986François Bancilhon, Raghu Ramakrishnan
ACM SIGMOD RecordEfficient management of transitive relationships in large data and knowledge bases
366 Citations1989R. K. Agrawal, Alexander Borgida +1 more
ACM Transactions on Database SystemsA compression technique to materialize transitive closure
179 Citations1990H. V. Jagadish
This work presents an indexing scheme that permits the storage of the pre-computed transitive closure of a database relation in a compressed form and shows how to add nodes and arcs to the compressed closure incrementally.
ACM SIGMOD RecordTraversal recursion: a practical approach to supporting recursive applications
136 Citations1986Arnon Rosenthal, Sandra Heiler +2 more
IEEE Transactions on Software EngineeringClustering a DAG for CAD databases
122 Citations1988Jayanta Banerjee, W. Kim +2 more
A study is made of the properties of the three types of clustered sequences of nodes for hierarchies and DAGs, and algorithms are developed for generating the clustered sequences, retrieving the descendants of a given node, and inserting new nodes into existing clusters of nodes which preserve their clustering properties.
Very Large Data BasesOn the Computation of the Transitive Closure of Relational Operators
110 Citations1986Yannis Ioannidis
This paper shows that the divide and conquer technique, applied to query processing in the presence of recursively defined views, is in many cases superior in performance than the Niteration algorithm.
ACM Transactions on Database SystemsDirect transitive closure algorithms: design and performance evaluation
97 Citations1990Rakesh Agrawal, Shaul Dar +1 more
This work presents new algorithms for computing transitive closure of large database relations that do not depend on the length of paths in the underlying graph and proposes a new methodology for evaluating the performance of recursive queries.
ComputerMap data processing in geographic information systems
84 Citations1989Rangachar Kasturi, Rafael Fernández +2 more
An overview of geographic information systems (GISs) is given, covering data collection, applications, organization, and data models.
ACM SIGMOD RecordA file structure supporting traversal recursion
31 Citations1989Paul A. Larson, V. Deshpande
Digital road map database for vehicle navigation and road information systems
17 Citations2003Shunsuke Kamijo, Ken-ichi OKUMURA +1 more
The preparation of a digital road map database for practical use over all of Japan commenced in Aug. 1988, and the first version was completed in March 1989.
IEEE Transactions on Knowledge and Data EngineeringEvaluating recursive queries in distributed databases
16 Citations1993Wolfgang Nejdl, Stefano Ceri +1 more
Several program transformation techniques that attempt to minimize distribution costs based on the idea of semIJoins and generalized semijoins in conventional databases are presented and an efficient method for testing the termination of the computation is developed.
Information SystemsPerformance evaluation of algorithms for transitive closure
15 Citations1992Robert Kabler, Yannis Ioannidis +1 more
The experiments indicate that the percentage of the graph nodes that need to be selected for Blocked Warren to be superior to Seminaive is rather large, which implies that for the majority of transitive closure queries with selection, Seminaives is the preferred strategy.
IEEE Transactions on Knowledge and Data EngineeringEfficient management of materialized generalized transitive closure in centralized and parallel environments
12 Citations1992K.-C. Guh, C. Yu
The proposed algorithms and the associated data structures are simple conceptually and in implementation and in a multiprocessor environment, the time complexities for insertion and deletion of the authors schemes are reduced.
DIGITAL ROAD MAP DATA BASE FOR VEHICLE NAVIGATION AND ROAD INFORMATION SYSTEMS. IN: CONFERENCE RECORD OF PAPERS PRESENTED AT THE FIRST VEHICLE NAVIGATION AND INFORMATION SYSTEMS CONFERENCE, TORONTO, ONTARIO, CANADA - SEPTEMBER 11-13, 1989
1 Citations1989Shunsuke Kamijo, Ken-ichi OKUMURA +1 more
The DRMap development program, design principles, data file contents and data base accuracy are reported upon, which are intended for use as a base map data for vehicle navigation.