GScan: Exploiting Sequential Scans for Subgraph Matching

Zhiwei ZHANG; Hao Wei; Jianliang XU; Koon Kau CHOI

doi:10.1007/978-3-030-18590-9_69

GScan: Exploiting Sequential Scans for Subgraph Matching

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

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-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 language	English
Title of host publication	Database Systems for Advanced Applications - DASFAA 2019 International Workshops
Subtitle of host publication	BDMS, BDQM, and GDMA, Proceedings
Editors	Guoliang Li, Joao Gama, Yongxin Tong, Jun Yang, Juggapong Natwichai
Publisher	Springer Verlag
Pages	471-475
Number of pages	5
ISBN (Print)	9783030185893
DOIs	https://doi.org/10.1007/978-3-030-18590-9_69
Publication status	Published - 24 Apr 2019
Event	24th International Conference on Database Systems for Advanced Applications, DASFAA 2019 - Chiang Mai, Thailand Duration: 22 Apr 2019 → 25 Apr 2019

Publication series

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

Conference

Conference	24th International Conference on Database Systems for Advanced Applications, DASFAA 2019
Country/Territory	Thailand
City	Chiang Mai
Period	22/04/19 → 25/04/19

Scopus Subject Areas

Theoretical Computer Science
Computer Science(all)

User-Defined Keywords

Graph matching
I/O efficient
Sequential access

Access to Document

10.1007/978-3-030-18590-9_69

Cite this

ZHANG, Z., Wei, H., XU, J., & CHOI, K. K. (2019). GScan: Exploiting Sequential Scans for Subgraph Matching. In G. Li, J. Gama, Y. Tong, J. Yang, & J. Natwichai (Eds.), Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings (pp. 471-475). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11448 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-18590-9_69

ZHANG, Zhiwei ; Wei, Hao ; XU, Jianliang et al. / GScan : Exploiting Sequential Scans for Subgraph Matching. Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings. editor / Guoliang Li ; Joao Gama ; Yongxin Tong ; Jun Yang ; Juggapong Natwichai. Springer Verlag, 2019. pp. 471-475 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0451895e99d34315b32421f5e8ebfd07,

title = "GScan: Exploiting Sequential Scans for Subgraph Matching",

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.",

keywords = "Graph matching, I/O efficient, Sequential access",

author = "Zhiwei ZHANG and Hao Wei and Jianliang XU and CHOI, {Koon Kau}",

note = "Funding Information: This work was supported by the grants from NSFC 61602395, RGC 12201518, RGC 12232716, RGC 12258116, RGC 12200817, and RGC 12201615. Funding Information: Acknowledgement. This work was supported by the grants from NSFC 61602395, RGC 12201518, RGC 12232716, RGC 12258116, RGC 12200817, and RGC 12201615.; 24th International Conference on Database Systems for Advanced Applications, DASFAA 2019 ; Conference date: 22-04-2019 Through 25-04-2019",

year = "2019",

month = apr,

day = "24",

doi = "10.1007/978-3-030-18590-9_69",

language = "English",

isbn = "9783030185893",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "471--475",

editor = "Guoliang Li and Joao Gama and Yongxin Tong and Jun Yang and Juggapong Natwichai",

booktitle = "Database Systems for Advanced Applications - DASFAA 2019 International Workshops",

address = "Germany",

}

ZHANG, Z, Wei, H, XU, J & CHOI, KK 2019, GScan: Exploiting Sequential Scans for Subgraph Matching. in G Li, J Gama, Y Tong, J Yang & J Natwichai (eds), Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11448 LNCS, Springer Verlag, pp. 471-475, 24th International Conference on Database Systems for Advanced Applications, DASFAA 2019, Chiang Mai, Thailand, 22/04/19. https://doi.org/10.1007/978-3-030-18590-9_69

GScan: Exploiting Sequential Scans for Subgraph Matching. / ZHANG, Zhiwei; Wei, Hao; XU, Jianliang et al.
Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings. ed. / Guoliang Li; Joao Gama; Yongxin Tong; Jun Yang; Juggapong Natwichai. Springer Verlag, 2019. p. 471-475 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11448 LNCS).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - GScan

T2 - 24th International Conference on Database Systems for Advanced Applications, DASFAA 2019

AU - ZHANG, Zhiwei

AU - Wei, Hao

AU - XU, Jianliang

AU - CHOI, Koon Kau

N1 - Funding Information: This work was supported by the grants from NSFC 61602395, RGC 12201518, RGC 12232716, RGC 12258116, RGC 12200817, and RGC 12201615. Funding Information: Acknowledgement. This work was supported by the grants from NSFC 61602395, RGC 12201518, RGC 12232716, RGC 12258116, RGC 12200817, and RGC 12201615.

PY - 2019/4/24

Y1 - 2019/4/24

N2 - 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.

AB - 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.

KW - Graph matching

KW - I/O efficient

KW - Sequential access

UR - http://www.scopus.com/inward/record.url?scp=85065430042&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-18590-9_69

DO - 10.1007/978-3-030-18590-9_69

M3 - Conference proceeding

AN - SCOPUS:85065430042

SN - 9783030185893

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 471

EP - 475

BT - Database Systems for Advanced Applications - DASFAA 2019 International Workshops

A2 - Li, Guoliang

A2 - Gama, Joao

A2 - Tong, Yongxin

A2 - Yang, Jun

A2 - Natwichai, Juggapong

PB - Springer Verlag

Y2 - 22 April 2019 through 25 April 2019

ER -

ZHANG Z, Wei H, XU J , CHOI KK. GScan: Exploiting Sequential Scans for Subgraph Matching. In Li G, Gama J, Tong Y, Yang J, Natwichai J, editors, Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings. Springer Verlag. 2019. p. 471-475. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-18590-9_69

GScan: Exploiting Sequential Scans for Subgraph Matching

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this