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.

  • Corporate Authors:

    University of Minnesota, Minneapolis

    Computer Science Department
    Minneapolis, MN  United States  55455

    Minnesota Department of Transportation

    Transportation Building, 395 John Ireland Boulevard
    St Paul, MN  United States  55155
  • Authors:
    • Shekhar, S
    • Liu, D-R
  • Publication Date: 1996-4


  • English

Media Info

  • Features: Appendices; Figures; References; Tables;
  • Pagination: 59 p.

Subject/Index Terms

Filing Info

  • Accession Number: 00725565
  • Record Type: Publication
  • Report/Paper Numbers: MN/RC-96/26, Final Report
  • Contract Numbers: 72981 TOC #167
  • Created Date: Sep 13 1996 12:00AM