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

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