TY - GEN
T1 - A privacy-preserving framework for subgraph pattern matching in cloud
AU - Gao, Jiuru
AU - Xu, Jiajie
AU - Liu, Guanfeng
AU - Chen, Wei
AU - Yin, Hongzhi
AU - Zhao, Lei
PY - 2018
Y1 - 2018
N2 - The growing popularity of storing large data graphs in cloud has inspired the emergence of subgraph pattern matching on a remote cloud, which is usually defined in terms of subgraph isomorphism. However, it is an NP-complete problem and too strict to find useful matches in certain applications. In addition, there exists another important concern, i.e., how to protect the privacy of data graphs in subgraph pattern matching without undermining matching results. To tackle these problems, we propose a novel framework to achieve the privacy-preserving subgraph pattern matching via strong simulation in cloud. Firstly, we develop a k-automorphism model based method to protect structural privacy in data graphs. Additionally, we use a cost-model based label generalization method to protect label privacy in both data graphs and pattern graphs. Owing to the symmetry in a k-automorphic graph, the subgraph pattern matching can be answered using the outsourced graph, which is only a subset of a k-automorphic graph. The efficiency of subgraph pattern matching can be greatly improved by this way. Extensive experiments on real-world datasets demonstrate the high efficiency and effectiveness of our framework.
AB - The growing popularity of storing large data graphs in cloud has inspired the emergence of subgraph pattern matching on a remote cloud, which is usually defined in terms of subgraph isomorphism. However, it is an NP-complete problem and too strict to find useful matches in certain applications. In addition, there exists another important concern, i.e., how to protect the privacy of data graphs in subgraph pattern matching without undermining matching results. To tackle these problems, we propose a novel framework to achieve the privacy-preserving subgraph pattern matching via strong simulation in cloud. Firstly, we develop a k-automorphism model based method to protect structural privacy in data graphs. Additionally, we use a cost-model based label generalization method to protect label privacy in both data graphs and pattern graphs. Owing to the symmetry in a k-automorphic graph, the subgraph pattern matching can be answered using the outsourced graph, which is only a subset of a k-automorphic graph. The efficiency of subgraph pattern matching can be greatly improved by this way. Extensive experiments on real-world datasets demonstrate the high efficiency and effectiveness of our framework.
KW - k-automorphism
KW - Label generalization
KW - Privacy-preserving
KW - Strong simulation
KW - Subgraph pattern matching
UR - http://www.scopus.com/inward/record.url?scp=85048047478&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-91452-7_20
DO - 10.1007/978-3-319-91452-7_20
M3 - Conference proceeding contribution
AN - SCOPUS:85048047478
SN - 9783319914510
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 307
EP - 322
BT - Database Systems for Advanced Applications
A2 - Pei, Jian
A2 - Manolopoulos, Yannis
A2 - Sadiq, Shazia
A2 - Li, Jianxin
PB - Springer, Springer Nature
CY - Cham, Switzerland
T2 - 23rd International Conference on Database Systems for Advanced Applications, DASFAA 2018
Y2 - 21 May 2018 through 24 May 2018
ER -