1. Towards answering analytical query over hierarchical histogram under untrusted servers.
- Author
-
Fu, Congcong, Li, Hui, Lou, Jian, and Cui, Jiangtao
- Subjects
OLAP technology ,RANDOM matrices ,DATA warehousing ,PRIVACY ,EMPIRICAL research - Abstract
Hierarchical count histograms involve the publication of count statistics at various granularities based on a predefined hierarchy within a dimension table in a data warehouse. This task finds extensive applications in on-line analytical processing (OLAP) scenarios. This paper focuses on the rigorous privacy-preserving constraint when dealing with an untrusted server. We conduct a systematic investigation of this task and uncover the limitations of the straightforward baseline approach using local differential privacy, as it fails to strike an optimal balance between privacy and utility. We are thus motivated to propose DP-HORUS, a novel crypto-assisted Differentially Private framework for Hierarchical cOunt histogRams under Untrusted Server. DP-HORUS consists of a series of novel designs, including (1) Encrypted hierarchical tree (EHT) structure, which maintains the concept hierarchy in the input data; (2) Random matrix (RM), which reduces communication and computational cost; (3) To further boosted the utility, we propose DP-HORUS+ encompassing two additional modules of histograms structure (HS) and hierarchical consistency (HC), which are respectively introduced to reduce the noise caused by data sparsity and to ensure the hierarchy consistency; (4) To further boost the robust performance, we propose a series of schemes for workload queries based on DP-HORUS. We provide both theoretical analysis and extensive empirical study on both real-world and synthetic datasets, which demonstrates the superior utility of the proposed methods over the state-of-the-art solutions while ensuring strict privacy guarantee. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF