基于索引的子图查询技术研究进展  

Research progress of index-based subgraph query technology

作　　者：施炜杰 董一鸿[1] 王雄 潘剑飞 SHI Weijie;DONG Yihong;WANG Xiong;PAN Jianfei(College of Information Science and Engineering,Ningbo University,Ningbo Zhejiang 315211,China;Baidu Online Technology Company Limited,Beijing 100084,China)

机构地区：[1]宁波大学信息科学与工程学院,浙江宁波315211 [2]北京百度在线科技有限公司,北京100084

出　　处：《计算机应用》2019年第1期39-45,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61572266);浙江省自然科学基金资助项目(LY16F020003);宁波市自然科学基金资助项目(2017A610114)~~

摘　　要：图作为表示实体间的数据结构,在社区发现、生物化学分析、社会安全分析等数据关联性要求较高的领域有着广泛的应用。对于大规模数据下进行实时的图查询问题,通过构建合适的索引可以有效降低查询响应时间,提高查询精确度。首先介绍基于索引的子图查询算法的基本结构;然后按索引的构建方式将主流算法分为基于枚举的方法和基于频繁模式挖掘的方法两大类,分别从索引特征、索引结构、应用数据集等方面进行介绍和分析;最后对基于索引的子图查询算法面临的主要问题进行总结和分析,阐述了最新的分布式系统下图查询技术,并对未来趋势进行展望。As a type of data structure representing entities,graphs are widely used in fields that have high requirements on data relevance,such as community data discovery,biochemical analysis and social security analysis.Focusing on the issue of real-time graph query operation under large-scale data,building a suitable index can effectively reduce query response time and improve query accuracy.The basic structure of index-based subgraph query algorithm was firstly introduced and then state-of-the-art algorithms were divided into two categories by construction method of index:enumeration construction and frequent pattern mining construction.Then these algorithms were introduced and analyzed from three aspects:index features,index structures and application datasets.Finally,main problems toward index-based subgraph query algorithm were summarized and analyzed,the latest query technology based on the distributed system was briefly described,and the future trend was forecasted.

关 键 词：子图同构 索引 子图查询 频繁模式 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]