Databases for Spatial Graph Management

空间图形管理的数据库对于交通、公用事业(如燃气、电力)和城市管理等大量应用是非常重要的。该项目解决了物理数据库设计和查询处理领域的空间图形管理需求。主要目标是开发、评估和实现一种新的基于图连通性的空间图形存储和访问方法，称为连通性集群访问方法(CCAM)。CCAM通过图划分的方法将图的节点分配到磁盘页面，以最大化连通性残留率，即一对连接的节点被分配到文件的公共页面的机会。另一个目标是开发可扩展的空间图聚类算法以及增量重组策略来增强CCAM。该项目还探索了增强现有几何访问方法的策略，以管理连通性属性和邻近属性。项目中开发的技术使用来自高级旅行者信息系统应用程序的基准图表进行评估

Databases for spatial graph management are very important for a large number of applications including transportation, utilities (e.g. gas, electricity) and urban management. This project addresses the needs of spatial graph management in the areas of physical database design and query processing. The main objective is to develop, evaluate and implement a novel spatial graph storage and access method, called Connectivity-Clustered Access Method (CCAM), based on graph-connectivity. CCAM assigns the nodes of a graphs to disk pages via the graph partitioning approach to maximize the Connectivity Residue Ratio, i.e., the chances that a pair of connected nodes are allocated to a common page of the file. Another objective is to develop scalable spatial graph-clustering algorithms as well as incremental reorganization strategies to enhance CCAM. This project also explores strategies to enhance existing geometric access methods for managing connectivity properties along with proximity properties. The techniques developed in the project are evaluated with benchmark graphs from Advanced Traveler Information System applications