Efficient subgraph matching on non-volatile memory

Yishu Shen; Zhaonian Zou

doi:10.1007/978-3-319-68783-4_31

Efficient subgraph matching on non-volatile memory

Yishu Shen
, Zhaonian Zou^*

^*Corresponding author for this work

School of Computer Science and Technology, Harbin Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Scopus citations

Abstract

The emerging non-volatile memory (NVM) technologies have attracted much attention due to its advantages over the existing DRAM technology such as non-volatility, byte-addressability and high storage density. These promising features make NVM a promising replacement of DRAM. Although the reading cost of NVM is close to that of DRAM, the writing cost is significantly higher than that of DRAM. Existing algorithms designed on DRAM treat read and write equally and thus are not applicable to NVM. In this paper, we investigate efficient algorithms for subgraph matching, a fundamental problem in graph databases, on NVM. We first give a detailed evaluation on several existing subgraph matching algorithms by experiments and theoretical analysis. Then, we propose our write-limited subgraph matching algorithm based on the analysis. We also extend our algorithm to answer subgraph matching on dynamic graphs. Experiments on an NVM simulator demonstrate a significant improvement in efficiency against the existing algorithms.

Original language	English
Title of host publication	Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings
Editors	Lu Chen, Athman Bouguettaya, Andrey Klimenko, Fedor Dzerzhinskiy, Stanislav V. Klimenko, Xiangliang Zhang, Qing Li, Yunjun Gao, Weijia Jia
Publisher	Springer Verlag
Pages	457-471
Number of pages	15
ISBN (Print)	9783319687827
DOIs	https://doi.org/10.1007/978-3-319-68783-4_31
State	Published - 2017
Externally published	Yes
Event	18th International Conference on Web Information Systems Engineering, WISE 2017 - Puschino, Russian Federation Duration: 7 Oct 2017 → 11 Oct 2017

Publication series

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

Conference

Conference	18th International Conference on Web Information Systems Engineering, WISE 2017
Country/Territory	Russian Federation
City	Puschino
Period	7/10/17 → 11/10/17

Keywords

Graph database
Non-volatile memory
Subgraph matching

Access to Document

10.1007/978-3-319-68783-4_31

Cite this

Shen, Y., & Zou, Z. (2017). Efficient subgraph matching on non-volatile memory. In L. Chen, A. Bouguettaya, A. Klimenko, F. Dzerzhinskiy, S. V. Klimenko, X. Zhang, Q. Li, Y. Gao, & W. Jia (Eds.), Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings (pp. 457-471). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10569 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-68783-4_31

Shen, Yishu ; Zou, Zhaonian. / Efficient subgraph matching on non-volatile memory. Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings. editor / Lu Chen ; Athman Bouguettaya ; Andrey Klimenko ; Fedor Dzerzhinskiy ; Stanislav V. Klimenko ; Xiangliang Zhang ; Qing Li ; Yunjun Gao ; Weijia Jia. Springer Verlag, 2017. pp. 457-471 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9e0586f3bf43449e89be13e12f044e0f,

title = "Efficient subgraph matching on non-volatile memory",

abstract = "The emerging non-volatile memory (NVM) technologies have attracted much attention due to its advantages over the existing DRAM technology such as non-volatility, byte-addressability and high storage density. These promising features make NVM a promising replacement of DRAM. Although the reading cost of NVM is close to that of DRAM, the writing cost is significantly higher than that of DRAM. Existing algorithms designed on DRAM treat read and write equally and thus are not applicable to NVM. In this paper, we investigate efficient algorithms for subgraph matching, a fundamental problem in graph databases, on NVM. We first give a detailed evaluation on several existing subgraph matching algorithms by experiments and theoretical analysis. Then, we propose our write-limited subgraph matching algorithm based on the analysis. We also extend our algorithm to answer subgraph matching on dynamic graphs. Experiments on an NVM simulator demonstrate a significant improvement in efficiency against the existing algorithms.",

keywords = "Graph database, Non-volatile memory, Subgraph matching",

author = "Yishu Shen and Zhaonian Zou",

note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 18th International Conference on Web Information Systems Engineering, WISE 2017 ; Conference date: 07-10-2017 Through 11-10-2017",

year = "2017",

doi = "10.1007/978-3-319-68783-4\_31",

language = "英语",

isbn = "9783319687827",

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

publisher = "Springer Verlag",

pages = "457--471",

editor = "Lu Chen and Athman Bouguettaya and Andrey Klimenko and Fedor Dzerzhinskiy and Klimenko, \{Stanislav V.\} and Xiangliang Zhang and Qing Li and Yunjun Gao and Weijia Jia",

booktitle = "Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings",

address = "德国",

}

Shen, Y & Zou, Z 2017, Efficient subgraph matching on non-volatile memory. in L Chen, A Bouguettaya, A Klimenko, F Dzerzhinskiy, SV Klimenko, X Zhang, Q Li, Y Gao & W Jia (eds), Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10569 LNCS, Springer Verlag, pp. 457-471, 18th International Conference on Web Information Systems Engineering, WISE 2017, Puschino, Russian Federation, 7/10/17. https://doi.org/10.1007/978-3-319-68783-4_31

Efficient subgraph matching on non-volatile memory. / Shen, Yishu; Zou, Zhaonian.
Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings. ed. / Lu Chen; Athman Bouguettaya; Andrey Klimenko; Fedor Dzerzhinskiy; Stanislav V. Klimenko; Xiangliang Zhang; Qing Li; Yunjun Gao; Weijia Jia. Springer Verlag, 2017. p. 457-471 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10569 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient subgraph matching on non-volatile memory

AU - Shen, Yishu

AU - Zou, Zhaonian

PY - 2017

Y1 - 2017

N2 - The emerging non-volatile memory (NVM) technologies have attracted much attention due to its advantages over the existing DRAM technology such as non-volatility, byte-addressability and high storage density. These promising features make NVM a promising replacement of DRAM. Although the reading cost of NVM is close to that of DRAM, the writing cost is significantly higher than that of DRAM. Existing algorithms designed on DRAM treat read and write equally and thus are not applicable to NVM. In this paper, we investigate efficient algorithms for subgraph matching, a fundamental problem in graph databases, on NVM. We first give a detailed evaluation on several existing subgraph matching algorithms by experiments and theoretical analysis. Then, we propose our write-limited subgraph matching algorithm based on the analysis. We also extend our algorithm to answer subgraph matching on dynamic graphs. Experiments on an NVM simulator demonstrate a significant improvement in efficiency against the existing algorithms.

AB - The emerging non-volatile memory (NVM) technologies have attracted much attention due to its advantages over the existing DRAM technology such as non-volatility, byte-addressability and high storage density. These promising features make NVM a promising replacement of DRAM. Although the reading cost of NVM is close to that of DRAM, the writing cost is significantly higher than that of DRAM. Existing algorithms designed on DRAM treat read and write equally and thus are not applicable to NVM. In this paper, we investigate efficient algorithms for subgraph matching, a fundamental problem in graph databases, on NVM. We first give a detailed evaluation on several existing subgraph matching algorithms by experiments and theoretical analysis. Then, we propose our write-limited subgraph matching algorithm based on the analysis. We also extend our algorithm to answer subgraph matching on dynamic graphs. Experiments on an NVM simulator demonstrate a significant improvement in efficiency against the existing algorithms.

KW - Graph database

KW - Non-volatile memory

KW - Subgraph matching

UR - https://www.scopus.com/pages/publications/85031411399

U2 - 10.1007/978-3-319-68783-4_31

DO - 10.1007/978-3-319-68783-4_31

M3 - 会议稿件

AN - SCOPUS:85031411399

SN - 9783319687827

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

SP - 457

EP - 471

BT - Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings

A2 - Chen, Lu

A2 - Bouguettaya, Athman

A2 - Klimenko, Andrey

A2 - Dzerzhinskiy, Fedor

A2 - Klimenko, Stanislav V.

A2 - Zhang, Xiangliang

A2 - Li, Qing

A2 - Gao, Yunjun

A2 - Jia, Weijia

PB - Springer Verlag

T2 - 18th International Conference on Web Information Systems Engineering, WISE 2017

Y2 - 7 October 2017 through 11 October 2017

ER -

Shen Y, Zou Z. Efficient subgraph matching on non-volatile memory. In Chen L, Bouguettaya A, Klimenko A, Dzerzhinskiy F, Klimenko SV, Zhang X, Li Q, Gao Y, Jia W, editors, Web Information Systems Engineering – WISE 2017 - 18th International Conference, Proceedings. Springer Verlag. 2017. p. 457-471. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-68783-4_31

Efficient subgraph matching on non-volatile memory

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this