利用频繁子图支持子图近似匹配的索引技术研究

《利用频繁子图支持子图近似匹配的索引技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号UDC密级学位论文利用频繁子图支持子图近似匹配的索引技术研究作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：许子南王国仁教授东北大学信息科学与工程学院硕士学科类别：工学计算机应用技术2010年6月1O日论文答辩日期：2010年7月4日答懒纵：赵海教授李晓光副教授、乔百友副教授东北大学2010年6月东北大学硕士学位论文Abstractbyusingalayeredstructure．Experimentsshowedthatthemethodacceleratestheprocessoflocalfrequentsubgraphsearch．Fi

2、nally,weintroducethefilterprincipletoLayeredInvertedFrequentsubgraphIndex(LIF—Index)，designanefficientalgorithmofsimilaritysearch，andcompareitwithanotherindexingmethod，gIndex，intheexperiment．Experimentsshowedthatthetechniquesthispaperproposeshavegoodperformance．Keywords：Graphdatabase；Similaritym

3、atching；Frequentsubgraphindex．IV—东北大学硕士学位论文目录3．4倒排频繁子图索引⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯283．4．1规范化标记(CanonicalLabel)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一283．4．2索引的创建⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯313．4．3查询处理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯323．4．4索引的维护⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯343。5本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯36第4章分层倒排频繁子图索引⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

4、⋯⋯⋯⋯⋯⋯⋯⋯374．1Apriori性质⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．374．1．1关联规则的概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯374．1．2Apriori算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯374．1．3Apriori性质⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯374．2分层倒排频繁子图索引⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯384．2．1索引结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯384．2．2索引创建⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯394．3查询处理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

5、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯414．3．1查询包含频繁子图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯414．3．2查询不包含频繁子图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯434．4索引维护⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯444．5本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯46第5章实验与性能分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯495．1伸缩性测试⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．505．2索引创建性能测试⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．525．3查询与过滤能力测试⋯⋯⋯⋯⋯⋯⋯

6、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．545．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一56第6章总结与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯576。1总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯576．2展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯57参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．59致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．63．V一东北大学硕士学位论文第1章绪论1．1背景知识介绍第1章绪论图是一种复杂而具有广泛应用价值的数据结构。1736年，

7、欧拉解决了哥尼斯堡七桥问题，从此图论作为一种重要的数学问题开始吸引大量学者的注意，并且得到十分迅速而完善的发展；1847年，克希霍夫用图来分析电路网络，之后图论开始广泛应用于工程科学；进入20世纪，随着新科技革命的发展，图在电子信息类研究和产业中，特别是在计算机科学中显示出越来越大的效果。图作为一种通用的数据结构类型，它能够简单而清楚的描述世界万物之问错综复杂的联系，适合作为结构化的数据模型。在数据库技术得到充分发展的情况下，将图和数据库技术结