CCAM - A CONNECTIVITY-CLUSTERED ACCESS METHOD FOR NETWORKS AND NETWORK COMPUTATIONS

Current Spatial Database Management Systems (SDBMS) provide efficient access methods and operators for point and range queries over collecti ons of spatial points, line segments, and polygons. However, it is not clear if existing spatial access methods can efficiently support netw ork computations which traverse line-segments in a spatial network bas ed on connectivity rather than geographic proximity. The expected I/O cost for many network operations can be reduced by maximizing the Weig hted Connectivity Residue Ratio (WCRR), i.e., the chance that a pair o f connected nodes that are more likely to be accessed together are all ocated to a common page of the file. CCAM is an access method for gene ral networks that uses connectivity clustering, CCAM supports the oper ations of insert, delete, create, and iind as well as the new operatio ns, get-A-successor and get-successors, which retrieve one or all succ essors of a node to facilitate aggregate computations on networks. The nodes of the network are assigned to disk pages via a graph partition ing approach to maximize the WCRR. CCAM includes methods for static cl ustering, as well as dynamic incremental reclustering, to maintain hig h WCRR in the face of updates, without incurring high overheads. We al so describe possible modifications to improve the WCRR that can be ach ieved by existing spatial access methods. Experiments with network com putations on the Minneapolis road map show that CCAM outperforms exist ing access methods, even though the proposed modifications also substa ntially improve the performance of existing spatial access methods.