CCAM: A connectivity-clustered access method for networks and network computations

Shashi Shekhar, Duen Ren Liu

Research output: Contribution to journalArticlepeer-review

78 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)102-119
Number of pages18
JournalIEEE Transactions on Knowledge and Data Engineering
Volume9
Issue number1
DOIs
StatePublished - 1997

Bibliographical note

Funding Information:
This research was supported by the Federal Highway Authority (FHWA), Minnesota Department of Transportation and the Center for Transportation Studies at the University of Minnesota. We would like to thank Dr. H.V. Ja-gadish (AT&T Bell Labs) and Professor K. Hua (University of Florida) for helping with the survey and focus of this research. We would also like to thank Professor C.K. Cheng (University of California, San Diego) and Dr. L.T. Liu (AT&T Bell Labs) for helping with the ratio-cut program. Finally, the interaction with the Network Engine group at Environmental Systems Research Institute helped in assessment of many ideas for suitability to GIS software systems such as ARC/INFO.

Keywords

  • Access methods
  • Geographic information systems
  • Network computations
  • Spatial databases
  • Spatial networks

Fingerprint

Dive into the research topics of 'CCAM: A connectivity-clustered access method for networks and network computations'. Together they form a unique fingerprint.

Cite this