GScan: Exploiting Sequential Scans for Subgraph Matching

Zhiwei ZHANG*, Hao Wei, Jianliang XU, Koon Kau CHOI

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


Subgraph matching is to enumerate all the subgraphs of a graph that is isomorphic to the query graph. It is a critical component of many applications such as clustering coefficient computation and trend evolution. As the real-world graph grows explosively, we have massive graphs that are much larger than the memory size of the modern machines. Therefore, in this paper, we study the subgraph matching problem where the graph is stored on disk. Different from the existing approaches, we design a block-based approach, GScan, which investigates the schedule of the blocks transferred between the memory and the disk. To achieve high I/O efficiency, GScan only uses sequential I/O read operations. We conduct experimental studies to demonstrate the efficiency of our block-based approach.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - DASFAA 2019 International Workshops
Subtitle of host publicationBDMS, BDQM, and GDMA, Proceedings
EditorsGuoliang Li, Joao Gama, Yongxin Tong, Jun Yang, Juggapong Natwichai
PublisherSpringer Verlag
Number of pages5
ISBN (Print)9783030185893
Publication statusPublished - 24 Apr 2019
Event24th International Conference on Database Systems for Advanced Applications, DASFAA 2019 - Chiang Mai, Thailand
Duration: 22 Apr 201925 Apr 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11448 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Conference on Database Systems for Advanced Applications, DASFAA 2019
CityChiang Mai

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Graph matching
  • I/O efficient
  • Sequential access


Dive into the research topics of 'GScan: Exploiting Sequential Scans for Subgraph Matching'. Together they form a unique fingerprint.

Cite this