折叠树编码索引的大规模图可达查询处理

作     者：宋宝燕 张瑞浩 单晓欢 丁琳琳 SONG Bao-yan;ZHANG Rui-hao;SHAN Xiao-huan;DING Lin-lin

作者机构：辽宁大学信息学院沈阳110036 

基　　金：国家自然科学基金项目(61472169 61502215)资助 辽宁省教育厅一般项目(L2015193)资助 辽宁省博士科研启动基金项目(201501127)资助 辽宁大学青年科研基金项目(LDQN201438)资助 

出 版 物：《小型微型计算机系统》 (Journal of Chinese Computer Systems)

年 卷 期：2017年第38卷第9期

页      码：2152-2156页

摘      要：可达查询作为图查询中一类基本查询,在众多领域得到广泛应用.研究发现,图规模的不断增长导致传统单机环境下的查询算法已无法满足大规模图的查询需求.为此,提出一种折叠树编码索引的大规模图可达查询方法,该方法由离线预处理和在线查询两阶段构成.预处理阶段,提出一种折叠树编码索引方法 FTCI,该方法建立了基于B+树的标记机制对分割子图进行标记,并通过标记子图上的折叠树创建及相应类哈夫曼编码,良好地保存了子图内部及子图间的可达信息;在线查询阶段,采用分布式技术,设计了基于FTCI的可达查询方法,根据查询节点隶属子图情况,给出子图内、子图间查询策略.实验证明提出的方法在保证高效查询的同时降低了索引的存储开销,提高了可达查询的处理效率.

主 题 词：分布式 大规模图 可达查询 类哈夫曼编码 

学科分类：08[工学] 0835[0835] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1000-1220.2017.09.043

馆 藏 号：203262179...