CAJ | 학술논문

最短路径查询是图数据管理与复杂关系挖掘的基本操作之一．本文针对资源描述框架图上的 top-k 最短路径查询，构造基于组件的索引，并在该索引的基础上实现查询的响应．查询优化阶段，针对查询效率问题，提出频繁路径以及结构剪枝策略，并给出有效性证明．实验表明，本文方法准确返回 top-k 最短路径并提高92％的查询速率．索引构造时间相比已有方法，提高约56％．同时，索引所占空间仅为原始数据大小的1～1．2倍．
최단로경사순시도수거관리여복잡관계알굴적기본조작지일．본문침대자원묘술광가도상적 top-k 최단로경사순，구조기우조건적색인，병재해색인적기출상실현사순적향응．사순우화계단，침대사순효솔문제，제출빈번로경이급결구전지책략，병급출유효성증명．실험표명，본문방법준학반회 top-k 최단로경병제고92％적사순속솔．색인구조시간상비이유방법，제고약56％．동시，색인소점공간부위원시수거대소적1～1．2배．
Finding the shortest path in a graph is a fundamental operation that allows complex relationships discovering in a graph database.This paper considers top-k shortest-path queries on RDF(Resource Description Framework)graphs.To solve this problem,we provide a component-based index for path queries and present an approach to answer the top-k shortest-path query.To efficiently process queries,we propose frequent path strategy and structural pruning.For frequent path strategy,we precompute the top-k shortest-paths between frequent entities obtained from the frequent paths.For the structural pruning,we find out the termina-tion condition for queries by considering the structural information of component-based index and derive two lemmas to guide this pruning mechanism.Experiments results show that the query runtime is improved by 92% using our answering approach and the construction time of our index for RDF graphs is speeded up by 56%.Meanwhile,the size of this index is only 0 ~0.2 times larger than that of the raw graphs.