TITLE:
Storage and Access Methods for Spatial Graphs (e. g. Navigable Road-Map Databases)
PRESENTER:
Shashi Shekhar
AFFILIATION:
Computer Sc. Dept., CTS and AHPCRC, Univ. of Minnesota.
TECHNICAL ABSTRACT:
Current Spatial Database Management Systems (SDBMS) provide efficient
access methods and operators for point and
range queries over collections of spatial points, line segments, and
polygons. However, it is not clear if existing spatial access methods
can efficiently support network computations
which traverse line-segments in a spatial network based
on connectivity rather than geographic proximity.
The expected I/O cost for many network operations
can be reduced by maximizing the
Weighted Connectivity Residue Ratio (WCRR), i.e.,
the chance that a pair of connected nodes that are more likely to be
accessed together are allocated to a common page of the file.
CCAM is an access method for general
networks that uses connectivity clustering.
CCAM supports the operations of insert(), delete(),
create(), and find() as well as the new operations,
get-A-successor() and get-successors(),
which retrieve one or all successors of a node to facilitate
aggregate computations on networks. The nodes of the network are
assigned to disk pages via a graph partitioning approach
to maximize the WCRR. CCAM includes methods for static
clustering, as well as dynamic incremental reclustering, to maintain
high WCRR in the face of updates, without incurring high overheads.
We also describe possible modifications to improve the WCRR that can be
achieved by existing spatial access methods. Experiments with network
computations on the Minneapolis road map show that CCAM outperforms
existing access methods, even though the proposed modifications
also substantially improve the performance of existing spatial access methods.
KEYWORDS:
Storage/Access Methods, Spatial Databases, Navigable Roadmaps,
Traveler Info. Systems., Intelligent Transportation Systems.
NOTE:
Some of the results discussed in this talk appeared in the following recent
publication: "CCAM: A Connectivity-Clustered Access Method for Networks and Network
Computations", IEEE Trans. on Knowledge and Data Engineering,
9(1), Jan.-Feb. 1997.