论文部分内容阅读
对复杂数据进行图模式建模在近年来越来越流行，因此，在查询执行的优化过程中图索引技术变得至关重要。在本文中，我们研究了图模式的索引问题，并且提出了一种近似的索引方法，称之为MSTA方法。MSTA方法利用最小生成树结构作为索引特征，依据最小生成树边序列的包含关系和基于最大公共子图的图距离度量，将最小生成树组织到一个称为MST树的索引结构中。MST树索引结构可以非常高效的支持其上的多种查询，例如子图查询。MSTA方法拥有着高效的索引性能。在索引大小和索引建立时间方面，传统方法是MSFA方法的数十倍，甚至上百倍。MSTA方法虽然不能返回完整结果，但是可以返回经图距离度量排序最好的部分结果。