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

一种面向图包容搜索的图索引模型
引用本文:黄崇本,陶剑文,程光华.一种面向图包容搜索的图索引模型[J].计算机应用,2008,28(2):479-483.
作者姓名:黄崇本  陶剑文  程光华
作者单位:1. 浙江工商职业技术学院,计算机应用研究所,浙江,宁波,315012
2. 浙江工商职业技术学院,计算机应用研究所,浙江,宁波,315012;宁波大学,信息科学与工程学院,浙江,宁波,315211
基金项目:浙江省重中之重信息与通信工程学科开放基金
摘    要:由于图模型的广泛采用,图数据的快速包容搜索在许多不同领域广泛应用。给定一个模型图集D和一个查询图集q,传统的图搜索旨在检索所有包含q的图(qg),与此不同,包容搜索有其自身的索引特性,针对这些特性进行系统地研究,并提出一种基于对比子图的索引模型(csgIndex):使用一个冗余感知特征选择过程,csgIndex能挑选出一个鲜明的具有区分力的对比子图集,并最大化其索引能力。对实时测试数据的实验结果显示,csgIndex对不同的包容搜索荷载能达到近优化修剪力,相较于传统图搜索方法表现出明显的索引性能优势。

关 键 词:采样技术  层次索引模型  图搜索  子图索引  聚类
文章编号:1001-9081(2008)02-0479-05
收稿时间:2007-09-06
修稿时间:2007-12-07

Effective graph indexing model for graph containment search
HUANG Chong-ben,TAO Jian-wen,CHENG Guang-hua.Effective graph indexing model for graph containment search[J].journal of Computer Applications,2008,28(2):479-483.
Authors:HUANG Chong-ben  TAO Jian-wen  CHENG Guang-hua
Affiliation:HUANG Chong-ben1,TAO Jian-wen1,2,CHENG Guang-hua1(1.Institute of Computer Applications,Zhejiang Business Technology Institute,Ningbo Zhejiang 315012,China,2.College of Information Science , Engineering,Ningbo University,Ningbo Zhejiang 315211,China)
Abstract:Due to the wide use of graph models, fast containment search of graph data finds many applications in various domains. Given a set of model graphs D and a query graph q, in comparison to traditional graph search that retrieves all the graphs containing q (q  g), containment search has its own indexing characteristics that have not yet been examined. In this paper,we performed a systematic study on these characteristics and proposed a contrast subgraph-based indexing model, called csgIndex. Using a redundancy-aware feature selection process, csgIndex can sort out a set of significant and distinctive contrast subgraphs and maximize its indexing capability. Experimental results on real test data show that csgIndex achieves near-optimal pruning power on various containment search workloads, and demonstrates its obvious advantage over indices built for traditional graph search in this new scenario.
Keywords:graph search  subgraph-based indexing  clustering  sampling technique  hierarchical indexing model
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机应用》浏览原始摘要信息
点击此处可从《计算机应用》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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