一种面向近似查询的图数据库索引方法

摘要

提出了一种在图数据库中建立相似匹配查找的索引方法。因为图的近似匹配是一个NP难问题,为了避免在数据库上的顺序查找,利用k-邻接子图索引一个大规模的图数据库,首先给出k-邻接子图索引的过滤机制以及生成k-邻接子图集的广度优先搜索算法,然后通过建立k-邻接子图字典的方法压缩存储空间并优化索引,最后讨论索引的维护方法。对于一个基于编辑距离范围的近似查询,通过在k-邻接子图索引上的过滤,最终可以得到一个远小于数据库数量的图集合作为精确匹配的候选集,大大减小了匹配所需的时间和空间.