Unified Query Processing Mechanism over Large-scale Graph Data
Author:
Affiliation:

Clc Number:

TP311

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Graph data can represent a wide range of real-world application scenarios, and query processing over graphs plays a crucial role in various tasks, such as reachability, shortest path, keyword search, graph pattern matching, PageRank, SimRank, k-core, k-truss, and Clique. For specific query problems, existing approaches typically propose corresponding query processing algorithms and build index structures to speed up the query. However, the diversification of application demands and the explosive growth in graph data scale present two major challenges to this methodology. First, a single graph dataset may involve multiple types of queries in practice, yet each query type often requires distinct processing mechanisms and index structures. Consequently, multiple indexes and corresponding query algorithms need to be constructed when designing a graph database. Second, index structures are often larger than the original graph data, and maintaining multiple indexes simultaneously can lead to significant space overhead, resulting in sharp performance degradation and limited practical applicability. To address these challenges, this study proposes a unified query processing mechanism. A unified and efficient index structure is constructed for large-scale graph data, upon which four query processing algorithms are designed, supporting reachability, shortest path, keyword search, and graph pattern matching. To build the unified index structure, the graph data is partitioned, and important vertices are extracted based on the characteristics of the four queries. The resulting unified index is smaller in size than the original graph and efficiently supports all four queries. Finally, the effectiveness and scalability of the unified index and the proposed algorithms are validated through experiments on four real-world datasets.

    Reference
    Related
    Cited by
Get Citation

陈迪,袁野,潘雅妮,王国仁.大图数据的统一查询处理机制.软件学报,2026,37(5):2235-2256

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:January 15,2025
  • Revised:April 11,2025
  • Adopted:
  • Online: December 17,2025
  • Published: May 06,2026
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063