首页 | 本学科首页   官方微博 | 高级检索  
     检索      

图索引技术研究综述
引用本文:刘雅辉,刘春阳,张铁赢,程学旗.图索引技术研究综述[J].山东大学学报(自然科学版),2013(11):44-52.
作者姓名:刘雅辉  刘春阳  张铁赢  程学旗
作者单位:[1]中国科学院计算技术研究所,北京100190 [2]石河子大学,新疆石河子832003 [3]国家计算机网络应急技术处理协调中心,北京100029
基金项目:国家重点基础研究发展计划(“九七三”计划)项目(2012CB316303,2013CB329602);高技术研究发展计划(“八六三”计划)项日(2012AA011003);国家自然科学基金重点项目(60933005,61232010);国家科技支撑计划项目(2012BAH39B04);国家242项目(2012F124);国家自然科学基金资助项目(61202214)
摘    要:随着信息技术和网络技术的发展,图作为一种通用的数据结构被用于不同学科建模各种实体以及实体之间的关系,,图中各实体间隐藏了很多有价值的信息,为了挖掘图中隐藏的这些信息,图的相关研究成为了各领域的研究热点,但在大多数图研究中最关键的问题是如何有效地进行图查询。在图数据库中存在着两种图数据集:单图和图集。针对单图或图集进行图查询是相当费时的,为了加快图查询速度,图索引成为各种图查询算法的研究重点,而图索引的焦点在于利用图索引的结构模式来最小化搜索空间的大小。本文将图查询归为两种:子图查询和超图查询。在每种查询中,依据图索引建立时选择的图结构特性进行了细分,主要集中于图索引的构建思想,并对典型的索引方法进行了详细的叙述。针对不同的图索引分析了各自的优缺点,并比较了各种索引方法的特点,最后,总结并探讨了图索引的发展趋势。

关 键 词:图索引  图查询  特征  子图  超图

An overview of graph indexing technology
LIU Ya-hui,LIU Chun-yang,ZHANG Tie-ying,CHENG Xue-qi.An overview of graph indexing technology[J].Journal of Shandong University(Natural Science Edition),2013(11):44-52.
Authors:LIU Ya-hui  LIU Chun-yang  ZHANG Tie-ying  CHENG Xue-qi
Institution:1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. Shihezi University, Shihezi 832003, Xinjiang, China; 3. National Computer Network Emergency Response Technical Team Coordination Center of China, Beijing 100029, China)
Abstract:Graph is a general data structure for modeling in varies of fields. With the development of information and network technology, it is widely applied for representing relationship between entities. In this way, most valuable infor- mation is hidden in entities. So as to mine the hidden information in graph, related researches on this topic are becoming popular. The key to solve the problem is how to efficiently search on graph. In the graph database, there are two kinds of graph data sets: Single Graph and Graphs. However, it is time-consuming in searching either Single Graph or Graphs. Thus, graph indexing is proposed to be a promising way to minimize the search space on graph in order to speed up graph search algorithms. This paper categorizes graph search into subgraph search and supergraph search. They are subdivided into smaller categories in terms of selected graph structure in building graph indexing. Meanwhile, the paper describes graph indexing building methods and detailed explanation on typical graph indexing. It compares kinds of graph indexing and analyzes their specific applications. At last, it discusses the development trend of graph indexing.
Keywords:graph indexing  graph search  feature  subgraph  supergraph
本文献已被 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号