图索引技术研究综述

J4 ›› 2013, Vol. 48 ›› Issue (11): 44-52.

图索引技术研究综述

刘雅辉1,2,刘春阳3*,张铁赢1,程学旗1

1.中国科学院计算技术研究所, 北京 100190; 2.石河子大学, 新疆石河子 832003;
3.国家计算机网络应急技术处理协调中心，北京 100029

收稿日期:2013-09-02 出版日期:2013-11-20 发布日期:2013-11-25
通讯作者: 刘春阳(1962- )，男，副研究员，博士，研究方向为大规模数据处理. Email:lcy@isc.org.cn
作者简介:刘雅辉(1979- ),女,讲师,博士研究生,研究方向为分布式数据库、图、大数据. Email:liuyahui@software.ict.ac.cn
基金资助:
国家重点基础研究发展计划(“九七三”计划)项目（2012CB316303,2013CB329602）；高技术研究发展计划(“八六三”计划)项目（2012AA011003）;国家自然科学基金重点项目（60933005,61232010）;国家科技支撑计划项目（2012BAH39B04）;国家242项目(2012F124);国家自然科学基金资助项目（61202214）

An overview of graph indexing technology

LIU Ya-hui1, 2, LIU Chun-yang3*, ZHANG Tie-ying1, CHENG Xue-qi1

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

Received:2013-09-02 Online:2013-11-20 Published:2013-11-25

摘要/Abstract

摘要：

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

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

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 information 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.

Key words: graph indexing; graph search; feature; subgraph; supergraph

中图分类号:

TP391

刘雅辉1,2,刘春阳3*,张铁赢1,程学旗1. 图索引技术研究综述[J]. J4, 2013, 48(11): 44-52.

LIU Ya-hui1, 2, LIU Chun-yang3*, ZHANG Tie-ying1, CHENG Xue-qi1. An overview of graph indexing technology[J]. J4, 2013, 48(11): 44-52.

参考文献

相关文章 11

[1]	于然1,2,刘春阳3*,靳小龙1,王元卓1,程学旗1. 基于多视角特征融合的中文垃圾微博过滤[J]. J4, 2013, 48(11): 53-58.
[2]	郑建兴,张博锋*,岳晓冬，成泽宇. 基于友邻-用户模型的微博主题推荐研究[J]. J4, 2013, 48(11): 59-65.
[3]	彭庆喜,钱铁云. 基于量化情感的网店垃圾评论检测[J]. J4, 2013, 48(11): 66-72.
[4]	黄亮,杜永萍. 基于信任关系的潜在好友推荐方法[J]. J4, 2013, 48(11): 73-79.
[5]	张乃洲1, 曹薇2, 陈珂锐1, 李石君3. 一种基于时间感知的搜索引擎模型[J]. J4, 2013, 48(11): 80-86.
[6]	陈珂锐,潘君. 基于扩展特征向量空间模型的多源数据融合[J]. J4, 2013, 48(11): 87-92.
[7]	方志军,刘心韵,伍世虔,郑文娟. 基于子带加权融合的多尺度 Retinex图像增强算法[J]. J4, 2013, 48(11): 93-98.
[8]	刘伍颖,易绵竹,张兴. 一种时空高效的多类别文本分类算法[J]. J4, 2013, 48(11): 99-104.
[9]	李玉倩刘林李金屏. 视频分析中灰度直方图的叠加原理研究[J]. J4, 2009, 44(11): 63-67.
[10]	谢桦林尚垣任雪芳. 单向粗关系及数据通讯安全[J]. J4, 2009, 44(9): 93-96.
[11]	许洁萍1,殷宏宇1,范子文2. 基于近似子乐句的翻唱歌曲识别研究[J]. J4, 2013, 48(7): 68-71.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed