Graphs are powerful tools for a wide range of real applications, from Biological and Chemical Databases, Social Networks, Citation Networks to Knowledge Bases. Large graph data repositories have been consistently found in recent applications. Due to the high complexity of graph queries, e.g., NP-Completeness of subgraph query, and the lack of IT expertise, hosting efficient graph query services for the owners of graph data has been a technically challenging task. And hence, they may prefer to outsource their services to third-party service providers (SPs) for scalability, elasticity and efficiency. Unfortunately, SPs may not always be trusted. Security, typically the integrity and confidentiality, of the data, has been recognized as one of the critical attributes of Quality of Services (QoS). This directly influences the willingness of both data owners and query clients to use SP’s services. To address these concerns, this thesis proposes novel techniques to solve both authentication-aware and privacy-aware subgraph query. Firstly, we study authenticated subgraph query services (Chapter 3). To support the service, we propose Merkle IFTree (MIFTree) where Merkle hash trees are applied into our Intersection-aware Feature-subgraph Tree (IFTree). IFTree aims to minimize I/O in a well-received subgraph query paradigm namely the filtering-and-verification framework. The structures required to be introduced to verification objects (VOs) and the authentication time are minimized. Subsequently, the overall response time is minimized. For optimizations, we propose an enhanced authentication method on MIFTree. Secondly, we propose structure-preserving subgraph query services (Chapter 4). A crucial step of this part is to transform the seminal subgraph isomorphism algorithm (the Ullmann’s algorithm) into a series of matrix operations. We propose a novel cyclic group based encryption (CGBE) method for private matrix operations. We propose a protocol that involves the query client and static indexes for optimizations. We prove that the structural information of both query graph and data graph are preserved under CGBE and analyze the privacy preservation in the presence of the optimizations. Thirdly, we propose asymmetric structure-preserving subgraph query processing (Chapter 5), where the data graph is publicly known and the query structure/topology is kept secret. Unlike other previous methods for subgraph queries, this part proposes a series of novel optimizations that only exploit graph structures, not the queries. Further, we propose a robust query encoding and adopt our proposed cyclic group based encryption method, so that the query processing can be transformed into a series of private matrix operations and performed securely. The effectiveness and efficiency of all the techniques presented in this thesis are experimentally evaluated with both real-world and synthetic dataset
| Identifer | oai:union.ndltd.org:hkbu.edu.hk/oai:repository.hkbu.edu.hk:etd_oa-1228 |
| Date | 11 August 2015 |
| Creators | Fan, Zhe |
| Publisher | HKBU Institutional Repository |
| Source Sets | Hong Kong Baptist University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Open Access Theses and Dissertations |
| Rights | The author retains all rights to this work. The author has signed an agreement granting HKBU a non-exclusive license to archive and distribute their thesis. |
Page generated in 0.0018 seconds