Database design for spatial network management systems: Clustering and declustering techniques.

摘要

Spatial network databases are the kernel of many important applications, including transportation planning; water, electric and gas utilities; telephone networks; urban management; sewer maintenance, etc. The research question in this thesis concerns how to store and organize data in order to support efficient data access for spatial network databases. To address this question, first, clustering can be used to organize and store query-related objects together (e.g. into disk blocks) to reduce the access cost. Second, parallelism can be exploited to reduce the response time for querying over large sets of objects. This is achieved by declustering objects (e.g. disk-blocks) across multiple-disks, which can be accessed in parallel to reduce the response time for large queries.; This thesis shows that the effectiveness (i.e. I/O overhead) of clustering techniques for networks is directly dependent on 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. Based on this insight, this thesis proposes a connectivity-clustered access method (CCAM). The nodes of the network are clustered into disk pages, via a graph-partitioning, approach to maximize the WCRR. CCAM includes methods for static clustering, as well as for dynamic incremental reclustering, to maintain a high WCRR in the face of updates, without incurring high overheads. This thesis also describes possible modifications to improve the WCRR that can be achieved by existing spatial access methods. This thesis uses the spatial network data and network computation queries from the domain of Intelligent Vehicle Highway Systems (IVHS) to evaluate the proposed ideas.; In addressing declustering, this thesis proposes a new similarity-based declustering technique which is based on the max-cut partitioning of similarity graphs that model the data-sets and query-sets. This technique can adapt to available information about query distribution and can work with alternative data-types, data distributions, data sizes and partition-size constraints. Experiments in parallelizing Grid Files for spatial range queries show that this method outperforms traditional methods for several interesting query distributions, as well for several non-uniform data distributions.