Structure-Preserving Subgraph Query Services.

A fundamental problem of graph databases is subgraph isomorphism query (a.k.a subgraph query): given a query graph Q<alternatives> <inline-graphic xlink:type="simple" xlink:href="fan-ieq1-2399292.gif"/></alternatives> and a graph database, it retrieves the graphs G<alternatives><inline-graphic xlink:type="simple" xlink:href="fan-ieq2-2399292.gif"/> </alternatives>s from the database that contain Q<alternatives> <inline-graphic xlink:type="simple" xlink:href="fan-ieq3-2399292.gif"/></alternatives>. Due to the cost of managing massive data coupled with the computational hardness of subgraph isomorphism testing, outsourcing the computations to a third-party provider is an appealing alternative. However, confidentiality has been a critical attribute of quality of service (QoS) in query services. To the best of our knowledge, subgraph query services with tunable preservation of privacy of structural information have never been addressed. In this paper, we present the first work on structure-preserving <alternatives><inline-graphic xlink:type="simple" xlink:href="fan-ieq4-2399292.gif"/></alternatives> ( \mathsf {SPsubIso}<alternatives> <inline-graphic xlink:type="simple" xlink:href="fan-ieq5-2399292.gif"/></alternatives>). A crucial step of our work is to transform \mathsf {subIso}<alternatives> <inline-graphic xlink:type="simple" xlink:href="fan-ieq6-2399292.gif"/></alternatives>—the seminal subgraph isomorphism algorithm (the Ullmann’s algorithm)—into a series of matrix operations. We propose a novel cyclic group based encryption (\mathsf CGBE<alternatives> <inline-graphic xlink:type="simple" xlink:href="fan-ieq7-2399292.gif"/></alternatives>) method for private matrix operations. We propose a protocol that involves the query client and static indexes to optimize \mathsf SPsubIso<alternatives> <inline-graphic xlink:type="simple" xlink:href="fan-ieq8-2399292.gif"/></alternatives>. We prove that the structural information of both Q<alternatives> <inline-graphic xlink:type="simple" xlink:href="fan-ieq9-2399292.gif"/></alternatives> and G <alternatives><inline-graphic xlink:type="simple" xlink:href="fan-ieq10-2399292.gif"/></alternatives> are preserved under \mathsf CGBE<alternatives> <inline-graphic xlink:type="simple" xlink:href="fan-ieq11-2399292.gif"/></alternatives> and analyze the privacy preservation in the presence of the optimizations. Our extensive experiments on both real and synthetic datasets verify that \mathsf SPsubIso<alternatives> <inline-graphic xlink:type="simple" xlink:href="fan-ieq12-2399292.gif"/></alternatives> is efficient and the optimizations are effective. [ABSTRACT FROM PUBLISHER]