CISPA
Browse

AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy

Download (6.39 MB)
conference contribution
posted on 2023-11-29, 18:17 authored by Linkang Du, Zhikun Zhang, Shaojie Bai, Changchang Liu, Shouling Ji, Peng Cheng, Jiming Chen
For protecting users' private data, local differential privacy (LDP) has been leveraged to provide the privacy-preserving range query, thus supporting further statistical analysis. However, existing LDP-based range query approaches are limited by their properties, i.e., collecting user data according to a pre-defined structure. These static frameworks would incur excessive noise added to the aggregated data especially in the low privacy budget setting. In this work, we propose an Adaptive Hierarchical Decomposition (AHEAD) protocol, which adaptively and dynamically controls the built tree structure, so that the injected noise is well controlled for maintaining high utility. Furthermore, we derive a guideline for properly choosing parameters for AHEAD so that the overall utility can be consistently competitive while rigorously satisfying LDP. Leveraging multiple real and synthetic datasets, we extensively show the effectiveness of AHEAD in both low and high dimensional range query scenarios, as well as its advantages over the state-of-the-art methods. In addition, we provide a series of useful observations for deploying AHEAD in practice.

History

Preferred Citation

Linkang Du, Zhikun Zhang, Shaojie Bai, Changchang Liu, Shouling Ji, Peng Cheng and Jiming Chen. AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy. In: ACM Conference on Computer and Communications Security (CCS). 2021.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM Conference on Computer and Communications Security (CCS)

Legacy Posted Date

2021-10-07

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3491, title = "AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy", author = "Du, Linkang and Zhang, Zhikun and Bai, Shaojie and Liu, Changchang and Ji, Shouling and Cheng, Peng and Chen, Jiming", booktitle="{ACM Conference on Computer and Communications Security (CCS)}", year="2021", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC