KIT | KIT-Bibliothek | Impressum | Datenschutz

Secrecy and performance models for query processing on outsourced graph data

Suntaxi, G.; El Ghazi, A. A.; Böhm, K.

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.

Open Access Logo

Verlagsausgabe §
DOI: 10.5445/IR/1000105706
Veröffentlicht am 18.07.2020
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2021
Sprache Englisch
Identifikator ISSN: 0926-8782, 1573-7578
KITopen-ID: 1000105706
Erschienen in Distributed and parallel databases
Verlag Springer
Band 39
Seiten 35–77
Vorab online veröffentlicht am 20.01.2020
Schlagwörter Secrecy, Data outsourcing, Graph data, Performance model
Nachgewiesen in Scopus
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page