东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

图索引技术研究综述

ISSN号：1671-9352
期刊名称：山东大学学报(理学版)
时间：2013.10.10
页码：44-52
分类：TP391[自动化与计算机技术—计算机应用技术;自动化与计算机技术—计算机科学与技术]
作者机构：[1]中国科学院计算技术研究所,北京100190, [2]石河子大学,新疆石河子832003, [3]国家计算机网络应急技术处理协调中心,北京100029
相关基金：国家重点基础研究发展计划（“九七三”计划）项目（2012CB316303,2013CB329602）;高技术研究发展计划（“八六三”计划）项日（2012AA011003）;国家自然科学基金重点项目（60933005,61232010）;国家科技支撑计划项目（2012BAH39B04）;国家242项目（2012F124）;国家自然科学基金资助项目（61202214）
相关项目：Web搜索与挖掘的新理论和新方法—支持舆情监控的Web搜索与挖掘的理论与方法研究

关键词：图索引, 图查询, 特征, 子图, 超图, graph indexing , graph search , feature , subgraph , supergraph

中文摘要：

随着信息技术和网络技术的发展，图作为一种通用的数据结构被用于不同学科建模各种实体以及实体之间的关系，，图中各实体间隐藏了很多有价值的信息，为了挖掘图中隐藏的这些信息，图的相关研究成为了各领域的研究热点，但在大多数图研究中最关键的问题是如何有效地进行图查询。在图数据库中存在着两种图数据集：单图和图集。针对单图或图集进行图查询是相当费时的，为了加快图查询速度，图索引成为各种图查询算法的研究重点，而图索引的焦点在于利用图索引的结构模式来最小化搜索空间的大小。本文将图查询归为两种：子图查询和超图查询。在每种查询中，依据图索引建立时选择的图结构特性进行了细分，主要集中于图索引的构建思想，并对典型的索引方法进行了详细的叙述。针对不同的图索引分析了各自的优缺点，并比较了各种索引方法的特点，最后，总结并探讨了图索引的发展趋势。

英文摘要：

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.

同期刊论文项目