This report examines the use of the Connectivity-Clustered Access Method (CCAM) to improve network
operations. 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. 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.
The report also describes 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.
Shekhar, Shashi; Liu, Duen-Ren.
Storage and Access Methods for Advanced Traveler Information Systems.
Minnesota Department of Transportation.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.