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

发布时间：2018-05-02 20:08

本文选题：分布式 + 大规模图　；参考：《小型微型计算机系统》2017年09期

【摘要】：可达查询作为图查询中一类基本查询,在众多领域得到广泛应用.研究发现,图规模的不断增长导致传统单机环境下的查询算法已无法满足大规模图的查询需求.为此,提出一种折叠树编码索引的大规模图可达查询方法,该方法由离线预处理和在线查询两阶段构成.预处理阶段,提出一种折叠树编码索引方法 FTCI,该方法建立了基于B+树的标记机制对分割子图进行标记,并通过标记子图上的折叠树创建及相应类哈夫曼编码,良好地保存了子图内部及子图间的可达信息;在线查询阶段,采用分布式技术,设计了基于FTCI的可达查询方法,根据查询节点隶属子图情况,给出子图内、子图间查询策略.实验证明提出的方法在保证高效查询的同时降低了索引的存储开销,提高了可达查询的处理效率.
[Abstract]:As a kind of basic query in graph query, reachable query is widely used in many fields. It is found that the traditional query algorithm in single machine environment can not meet the query demand of large scale graph due to the increasing of graph scale. For this reason, a large scale graph reachability query method based on folding tree coding index is proposed, which consists of two stages: off-line preprocessing and on-line query. In the preprocessing stage, a folding tree coding index method, FTCI, is proposed, which establishes a marking mechanism based on B-tree to mark the segmented subgraph, and creates the folding tree on the marker subgraph and the corresponding Huffman coding. The reachable information within and between subgraphs is well preserved, and in the online query stage, the reachability query method based on FTCI is designed by using distributed technology. According to the case of query node membership subgraph, the query strategy between subgraphs and subgraphs is given. Experiments show that the proposed method not only ensures efficient query, but also reduces the storage cost of index, and improves the processing efficiency of reachable query.
【作者单位】：辽宁大学信息学院;
【基金】：国家自然科学基金项目(61472169,61502215)资助辽宁省教育厅一般项目(L2015193)资助辽宁省博士科研启动基金项目(201501127)资助辽宁大学青年科研基金项目(LDQN201438)资助
【分类号】：O157.5

【相似文献】