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 contributionpeer-review

Abstract

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
Pages471-475
Number of pages5
ISBN (Print)9783030185893
DOIs
Publication statusPublished - 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

Conference

Conference24th International Conference on Database Systems for Advanced Applications, DASFAA 2019
Country/TerritoryThailand
CityChiang Mai
Period22/04/1925/04/19

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Graph matching
  • I/O efficient
  • Sequential access

Fingerprint

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

Cite this