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

Folding Tree Coding Index Based Reachability Query Processing on Large Graphs

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

As a kind of fundamental query on graphs,reachability query has been widely used in social network,semantic web and biological information,etc.With the increase of graphs,the traditional query methods in single machine environment cannot satisfy query on large-scale graphs for the low query efficiency and the expensive storage cost.Therefore,this paper proposes a reachability query method on large-scale graphs.It consists of offline pretreatment and online query.In the offline pretreatment,this paper presents a folding tree coding index method （FTCI）.FTCI establishes a result marker mechanism based on B＋ tree to mark the subgraph partition results on subgraphs.FTCI constructs folding trees and proceeds similar huffman coding to save the reachability information within each subgraph and among subgraphs;in the online query,this paper adopts distributed technology and Hadoop computing platform,designs a reachability query method based on FTCI （FTCI-DRQ）,according to the subordination relations between two query nodes,FTCI-DRQ provides the strategy within subgraph and among subgraphs respectively.Experimental results show that FTCI-DRQ method improves the query efficiency and reduce the storage cost of index.