Partial Order Based Layout Strategy For Large-scale Knowledge Base Completion

Knowledge base completion has received extensive attention as an important part of knowledge base technology.Among them,the path-based knowledge completion algorithm has a strong logical correlation,can reflect the connection between the affairs in the real world in a deep level,and is suitable for applications in scenarios with high requirements for completion results.However the feature extraction process in the path-based knowledge completion algorithm is particularly time-consuming,there are a series of optimizations based on the memory model for this stage.The use of the limited-length graph traversal algorithm for feature extraction is proposed.With the scale of knowledge bases gradually increasing,large-scale knowledge bases cannot be fully loaded into memory.When using classical external memory model graph process system to improve the efficiency of limited-length graph traversal algorithm,it is pointed out that these systems' data partition scheme lacks of sequentially and locality.This paper proposes a data layout strategy BFLS(BFS Forest Based Layout Strategy)which rearranges graph node index based on BFS forest formed by some limited-length BFS subtrees to improve the data partition scheme's succession and locality,thereby improving the execution efficiency of the limited-length graph traversal algorithm.BFLS is tested on several widely used open knowledge bases.On the classical external model graph process system,the execution efficiency of the limited length graph traversal algorithm before and after the BFLS is compared and the validity of the BLFS is verified.The limited-length graph traversal algorithm execution time can be reduced to 20%-80% after BFLS being applied.