Reachability query is a fundamental primitive on graph analysis. Recently, label-constrained reachability(LCR) has drawn growing research attention on edge-label graphs. However, no research has studied this problem on temporal property graphs, which are widely used to model many real-world networks with time-related activities, such as social networks and cybersecurity knowledge graphs. Edges in these networks have both time and label attributes. In this paper, we define the Temporal Label-Constrained Reachability(TLCR) query problem for the first time and design a novel index called Temporal Labeled Vertex Labeling(TL) to accelerate this type of query. To further improve query performance, we propose a hybrid index strategy (HTL) by optimizing TL with an existing index strategy Topchain. Based on this hybrid index, we design a new query algorithm. Experiments on 5 real-world datasets show that our query algorithm can achieve up to 0.5–8 times faster than the baseline method.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Hybrid Indexing for Label-Constrained Reachability on Temporal Property Graphs

  • Zhean Chen,
  • Jianye Yang,
  • Shiyu Yang

摘要

Reachability query is a fundamental primitive on graph analysis. Recently, label-constrained reachability(LCR) has drawn growing research attention on edge-label graphs. However, no research has studied this problem on temporal property graphs, which are widely used to model many real-world networks with time-related activities, such as social networks and cybersecurity knowledge graphs. Edges in these networks have both time and label attributes. In this paper, we define the Temporal Label-Constrained Reachability(TLCR) query problem for the first time and design a novel index called Temporal Labeled Vertex Labeling(TL) to accelerate this type of query. To further improve query performance, we propose a hybrid index strategy (HTL) by optimizing TL with an existing index strategy Topchain. Based on this hybrid index, we design a new query algorithm. Experiments on 5 real-world datasets show that our query algorithm can achieve up to 0.5–8 times faster than the baseline method.