基于Top-k持续匹配机制的动态图查询方法

DYNAMIC GRAPH QUERY METHOD BASED ON TOP-K CONTINUOS MATCHING MECHANISM

  • 摘要: 为实现高效的持续图形查询,提出一种基于Top-k持续匹配机制的动态图查询方法。通过遍历标记版本图来识别持续匹配,其中每个节点、边和标签均存在于图中的时间间隔集,标记版本图的高效内存布局允许在每个快照快速检索相邻节点;为了减少候选匹配的数量,引入基于Bloom滤波器的邻域和路径时间索引,利用基于时间索引确定持续时间阈值。实验验证了该方法能够有效实现最持续动态图查询,并且具有较高的计算效率。

     

    Abstract: In order to realize efficient continuous graph query, a dynamic graph query method based on Top-k continuous matching mechanism is proposed. Continuous matching was identified by traversing the marked version graph, in which each node, edge and label existed in the interval set in the graph. The efficient memory layout of the labeled version graph allowed fast retrieval of adjacent nodes at each snapshot. In order to reduce the number of candidate matches, the neighborhood and path time index based on Bloom filter were further introduced, and the duration threshold was determined by using the time index. The experimental results show that the proposed method can effectively realize the most sustainable dynamic graph query, and has high computational efficiency.

     

/

返回文章
返回