摘要
研究了图查询中的最短路径查询问题,针对现有的查询算法存在构建索引时间长和索引规模庞大所导致的低效性和扩展性问题,在索引构建方面提出了顶点关联索引策略。对度数为1的顶点构建顶点关联索引,对其他顶点构建2-hop标签索引,通过减少冗余数据存储和图的遍历次数,降低索引规模以减少构建索引时间。基于所提出的查询策略,给出了基于顶点关联关系和2-hop标签的最短路径查询算法。
The shortest path query problem in graph query is studied. Aiming at existing algorithms＇ problem of low efficiency and expansibility caused by the long time of the construction of index and the large scale of indexes,a vertex-related index strategy is proposed in index construction： constructing a vertex-related index on the vertex of1,constructing a 2-hop tag index for other vertices,reducing the index size by reducing the number of traversal times of redundant data storage and graphs to reduce the build index time. Based on the proposed query strategy,the shortest path query algorithm based on vertex-related index and 2-hop tag is given.
出处
《高技术通讯》
北大核心
2017年第11期899-906,共8页
Chinese High Technology Letters
基金
国家自然科学基金(61572421)资助项目
