Scholarlink

<p>Given a data graph <i>G</i>, a source vertex <i>u</i>, and a target vertex <i>v</i> of a reachability query, the reachability query is used to answer whether there exists a path from <i>u</i> to <i>v</i> in <i>G</i>. Reachability query processing is one of the fundamental operations in graph data management, which is widely used in biological networks, communication networks, and social networks to assist data analysis. The data graphs in practical applications usually contain information such as quantization weights associated with the structural relationships, in addition to the structural relationships between vertices. Thus, in addition to the traditional reachability relationships, users may want to further understand whether such reachability relationships satisfy specific constraints. In this paper, we study the problem of efficiently processing <i>k</i>-step reachability queries with weighted constraints in weighted graphs. The <i>k</i>-step weighted reachability query questions are used to answer the question of whether there exists a path from a source vertex <i>u</i> to a goal vertex <i>v</i> in a given weighted graph. If it exists, the path needs to satisfy (1) all edges in the path satisfy the given weight constraints, and (2) the length of the path does not exceed the given distance threshold <i>k</i>. To address the problem, firstly, WKRI indexes supporting <i>k</i>-step weighted reachability query processing and index construction methods based on efficient pruning strategies are proposed. Secondly, the idea of constructing indexes based on part of the vertices is proposed to reduce the size of the indexes and two optimized indexes are designed and implemented based on the vertex coverage set to design and implement two optimized indexes GWKRI and LWKRI. Finally, experiments are conducted on several real datasets. The experimental results verify the efficiency of the method proposed in this paper in answering <i>k</i>-step weighted reachability queries.</p>

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

Efficient k-step Weighted Reachability Queries Processing Algorithms

  • 期刊论文

  • 发表日期：

    2025年3月25日

查看全文
  • Congquan Mei,
  • Junfeng Zhou,
  • Ming Du,
  • Lian Chen,
  • Sheng Yu,
  • Xian Tang,
  • Ziyang Chen

摘要

Given a data graph G, a source vertex u, and a target vertex v of a reachability query, the reachability query is used to answer whether there exists a path from u to v in G. Reachability query processing is one of the fundamental operations in graph data management, which is widely used in biological networks, communication networks, and social networks to assist data analysis. The data graphs in practical applications usually contain information such as quantization weights associated with the structural relationships, in addition to the structural relationships between vertices. Thus, in addition to the traditional reachability relationships, users may want to further understand whether such reachability relationships satisfy specific constraints. In this paper, we study the problem of efficiently processing k-step reachability queries with weighted constraints in weighted graphs. The k-step weighted reachability query questions are used to answer the question of whether there exists a path from a source vertex u to a goal vertex v in a given weighted graph. If it exists, the path needs to satisfy (1) all edges in the path satisfy the given weight constraints, and (2) the length of the path does not exceed the given distance threshold k. To address the problem, firstly, WKRI indexes supporting k-step weighted reachability query processing and index construction methods based on efficient pruning strategies are proposed. Secondly, the idea of constructing indexes based on part of the vertices is proposed to reduce the size of the indexes and two optimized indexes are designed and implemented based on the vertex coverage set to design and implement two optimized indexes GWKRI and LWKRI. Finally, experiments are conducted on several real datasets. The experimental results verify the efficiency of the method proposed in this paper in answering k-step weighted reachability queries.