Towards Efficient Authenticated Subgraph Query Service in Outsourced Graph Databases
Towards Efficient Authenticated Subgraph Query Service in Outsourced Graph Databases
复制标题
DOI：
10.1109/tsc.2013.42
复制
发表时间：
2014-10
影响因子：
8.1
通讯作者：
Zhe Fan;Yun Peng;Byron Choi;Jianliang Xu;S. Bhowmick
中科院分区：
文献类型：
--
作者：
Zhe Fan;Yun Peng;Byron Choi;Jianliang Xu;S. Bhowmick
图形是强大的工具，适用于各种应用，包括化学数据库和语义网等。图数据库的基本查询是子图查询：给定查询图 q，它从包含 q 的数据库中检索数据图。由于管理海量数据的成本加上子图查询处理的计算难度，将处理外包给第三方服务提供商是一个有吸引力的选择。然而，数据完整性和响应时间等安全属性是查询服务中关键的服务质量 (QoS) 问题。不幸的是，据我们所知，经过身份验证的子图查询服务之前尚未得到解决。为了支持该服务，我们提出了 Merkle IFTree (MIFTree)，其中 Merkle 哈希树应用于我们的交叉感知特征子图树 (IFTree)。 IFTree 旨在最大限度地减少广受好评的子图查询范式（称为过滤和验证框架）中的 I/O。需要引入验证对象（VO）的结构和认证时间都被最小化。随后，总响应时间被最小化。为了优化，我们在 MIFTree 上提出了一种增强的身份验证方法。我们对真实数据集和合成数据集的详细实验表明，MIFTree 显然比基线方法更有效。
Graphs are powerful tools suitable for a large variety of applications including chemical databases and the Semantic Web, among others. A fundamental query of graph databases is the subgraph query: given a query graph q, it retrieves the data graphs from a database that contain q. Due to the cost of managing massive data coupled with the computational hardness of subgraph query processing, outsourcing the processing to a third-party service provider is an appealing alternative. However, security properties such as data integrity and the response time are critical Quality of Service (QoS) issues in query services. Unfortunately, to our knowledge, authenticated subgraph query services have not been addressed before. 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 called the filtering-and-verification framework. The structures that need to be introduced to verification objects ( VOs) and the authentication time are both minimized. Subsequently, the overall response time is minimized. For optimizations, we propose an enhanced authentication method on MIFTree. Our detailed experiments on both real and synthetic datasets demonstrate that MIFTree is clearly more efficient than a baseline method.