Secrecy and performance models for query processing on outsourced graph data

Database outsourcing is a challenge concerning data secrecy. Even if an adversary, including the service provider, accesses the data, she should not be able to learn any information from the accessed data. In this paper, we address this problem for graph-structured data. First, we define a secrecy n...

Full description

Saved in:
Bibliographic Details
Published in:Distributed and parallel databases : an international journal 2021-03, Vol.39 (1), p.35-77
Main Authors: Suntaxi, Gabriela, El Ghazi, Aboubakr Achraf, Böhm, Klemens
Format: Article
Language:English
Subjects:
Buckets
Computer Science
Data Structures
Database Management
Encryption
Information Systems Applications (incl.Internet)
Memory Structures
Model accuracy
Operating Systems
Performance indices
Queries
Query processing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Database outsourcing is a challenge concerning data secrecy. Even if an adversary, including the service provider, accesses the data, she should not be able to learn any information from the accessed data. In this paper, we address this problem for graph-structured data. First, we define a secrecy notion for graph-structured data based on the concepts of indistinguishability and searchable encryption. To address this problem, we propose an approach based on bucketization. Next to bucketization, it makes use of obfuscated indexes and encryption. We show that finding an optimal bucketization tailored to graph-structured data is NP-hard; therefore, we come up with a heuristic. We prove that the proposed bucketization approach fulfills our secrecy notion. In addition, we present a performance model for scale-free networks which consists of (1) a number-of-buckets model that estimates the number of buckets obtained after applying our bucketization approach and (2) a query-cost model. Finally, we demonstrate with a set of experiments the accuracy of our number-of-buckets model and the efficiency of our approach with respect to query processing.
ISSN:0926-8782
1573-7578
DOI:10.1007/s10619-020-07284-0