一种基于图结构分解的图近似查询方法研究

来源：计算机工程与科学杂志2015年第2期北京时间：

作者：杨书新,谭伟,魏朝奇

单位：江西理工大学信息工程学院，江西 赣州 341000

摘要：图近似查询能够得到与查询图近似的结果集，相比较精确查询具有更广泛的应用范围。为提高近似查询的查准率和查全率，提出一种基于图结构分解的查询算法。该算法通过对查询图和目标图进行图结构分解，对其建立图分解索引，利用查询图的最小生成树集得到满足阈值的生成树集，通过图标准编码在索引中快速定位，查找出所有可能的近似结果。实验结果表明，该算法能有效得到近似结果，提高查询速度。

关键词：图近似查询,DAG图,最小生成树,

基金资助：江西省自然基金资助项目（20122BAB201045）；江西省科技厅青年科学基金资助项目（20122BAB211035）；江西省教育厅科技资助项目（GJJ12349,GJJ11126,GJJ12347）；江西省研究生创新基金资助项目（YC2011S093）；江西理工大学自然基金资助项目（jxxj11053）