| 一种基于图结构分解的图近似查询方法研究 |
| |
| 引用本文： | 杨书新,谭伟,魏朝奇.一种基于图结构分解的图近似查询方法研究[J].计算机工程与科学,2015,37(2):359-364. |
| |
| 作者姓名： | 杨书新 谭伟 魏朝奇 |
| |
| 作者单位： | 江西理工大学信息工程学院,江西赣州,341000 |
| |
| 基金项目： | 江西省自然基金资助项目（20122BAB201045）；江西省科技厅青年科学基金资助项目（20122BAB211035）；江西省教育厅科技资助项目（GJJ12349,GJJ11126,GJJ12347）；江西省研究生创新基金资助项目（YC2011 S093）；江西理工大学自然基金资助项目（jxxj11053） |
| |
| 摘 要： | 图近似查询能够得到与查询图近似的结果集,相比较精确查询具有更广泛的应用范围。为提高近似查询的查准率和查全率,提出一种基于图结构分解的查询算法。该算法通过对查询图和目标图进行图结构分解,对其建立图分解索引,利用查询图的最小生成树集得到满足阈值的生成树集,通过图标准编码在索引中快速定位,查找出所有可能的近似结果。实验结果表明,该算法能有效得到近似结果,提高查询速度。
|
| 关 键 词： | 图近似查询 DAG图 最小生成树 |
| 收稿时间： | 2013-04-03 |
| 修稿时间： | 2013-09-04 |
A graph approximate query method
based on graph decomposition |
| |
| YANG Shu-xin
,
TAN Wei
,
WEI Chao-qi.A graph approximate query method
based on graph decomposition[J].Computer Engineering & Science,2015,37(2):359-364. |
| |
| Authors: | YANG Shu-xin TAN Wei WEI Chao-qi |
| |
| Affiliation: | (School of Information Engineering，Jiangxi University of Science and Technology，Jiangxi 341000,China) |
| |
| Abstract: | The graph approximate query of graph data can get result sets similar to the query graph.It’s been more widely applied in many areas than accurate query.To obtain complete and reliable results,we propose an algorithm based on graph decomposition.This algorithm decomposes the query graph and the graph data according to the graph structure,and makes an index based on DAG.Utilizing the minimum spanning tree set of the query graph,we get the spanning tree set with a threshold;and we use graph standard codes for quick query and get approximate results as many as possible.The experimental results show that the algorithm can effectively get the approximate results and improve the query speed. |
| |
| Keywords: | graph approximate search DAG graph minimum spanning tree |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载全文 |
|
