CCAM: A Connectivity-Clustered Access Method for Networks and
Networks Computions.
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:
Access Methods, Geographic Information Systems,
Network Computations, Spatial Databases, Spatial Networks
Please select the format you would like to view the paper
If your browser do not support the viewing of postscript file, it
will save as a file instead
![[HOME PAGE]](../home_btn.gif)
Design and Maintain by Julian Chow
Questions and Comments?
![[mailto:]](../icons/icnmail2.gif)
jchow@cs.umn.edu
[last Updated] Mon. July 17th 1995