Paper Info
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.
Year
Venue
Field
2017
WISE
Dram,Data mining,Graph,Graph database,Computer science,Induced subgraph isomorphism problem,Theoretical computer science,Non-volatile memory,Factor-critical graph,Subgraph isomorphism problem,Blossom algorithm
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
11
2
Name
Order
Citations
PageRank
Yishu Shen100.34
Zhaonian Zou233115.78